Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem A. 486. (September 2009)

A. 486. Denote by \nu(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 \nu(n) \equiv a \pmod{m}.

(5 pont)

Deadline expired on October 12, 2009.


Solution. We will use the well-known fact that \nu(n) = \sum_{k=1}^\infty \bigg[\frac{n}{2^k}\bigg].

If the base-2 form of the number n is n=\overline{d_\ell
  d_{\ell-1}\ldots d_1d_0} = \sum\limits_{i=0}^\ell d_i\cdot2^i, where the digits d_0,\ldots,d_\ell are all 0 or 1, then


  \nu(n) =
  \sum_{k=1}^\infty \bigg[\frac{n}{2^k}\bigg] =
  \sum_{k=1}^\ell \Bigg[\frac{\overline{d_\ell d_{\ell-1}\ldots d_1d_0}}{2^k}\Bigg] =
  \sum_{k=1}^\ell \overline{d_\ell d_{\ell-1}\ldots d_k} =


  = \sum_{k=1}^\ell \left(\sum_{i=k}^\ell d_i \cdot 2^{i-k}\right) =
  \sum_{i=1}^\ell d_i \left(\sum_{k=1}^i 2^{i-k}\right) =
  \sum_{i=1}^\ell d_i \cdot (2^i-1).

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


2^{i_1}-1 \equiv 2^{i_2}-1 \equiv 2^{i_3}-1 \equiv 
\ldots \equiv r \pmod{m}.

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


u \,\Big|\, 2^{\varphi (u)}-1 \,\Big|\, 2^{i-1}-1,


2^i-1 = 2(2^{i-1}-1) + 1 \equiv 1 \pmod{u},
(1)

and, due to i\get,


2^i-1 \equiv -1 \pmod{2^t}.
(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 a\equiv ur\pmod{m}. For n=2^{i_1}+\ldots+2^{i_u} we achieve


\nu(n) =
\nu\big( 2^{i_1}+\ldots+2^{i_u} \big) =
(2^{i_1}-1)+\ldots+(2^{i_u}-1) \equiv
u\cdot r \equiv a \pmod{m}.

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