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 October 12, 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.
Problems in Mathematics of KöMaL, September 2009