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 .
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,
and, due to it,
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