Magyar Information Contest Journal Articles

# Problem A. 486. (September 2009)

A. 486. Denote by (n) the exponent of 2 in the prime factorization of n!. Show that for arbitrary positive integers a and m there exists an integer n>1 for which .

(5 pont)

Deadline expired on 12 October 2009.

Solution. We will use the well-known fact that .

If the base-2 form of the number n is , where the digits are all 0 or 1, then

Now we will show that there exists an integer r which is relatively prime to m, and an infinite sequence of positive integers such that

Let m=2tu where u is odd, and consider an arbitrary positive integer it for which (u) divides i-1. By the Euler-Fermat theorem,

 (1)

and, due to it,

 (2)

The relations (1) and (2) determine the residue class of 2i-1 modulo m, and it must be relatively prime to m.

Since m and r are relatively prime, there is a positiv integer u such that . For we achieve

Based on the solution of András Éles

### Statistics:

 13 students sent a solution. 5 points: Ágoston Tamás, Backhausz Tibor, Bodor Bertalan, Éles András, Frankl Nóra, Nagy 235 János, Nagy 648 Donát, Somogyi Ákos, Strenner Péter, Szabó 928 Attila. 4 points: Kalina Kende. 3 points: 1 student. 0 point: 1 student.

 Our web pages are supported by: Morgan Stanley