Maths Olympiad Prep

Library / /12 of 16

Number theory Difficulty 6.1 National olympiad Prove it Thailand

Denote by ν(n)\nu(n) the exponent of 22 in the prime factorization of n!n!. Show that for arbitrary positive integers aa and mm there exists an integer n>1n > 1 for which ν(n)amodm\nu(n) \equiv a \mod m.

Solution

We will use the well-known fact that ν(n)=k=1n2k\nu(n) = \sum_{k=1}^{\infty} \lfloor \frac{n}{2^k} \rfloor. If the base-2 form of the number nn is n=dldl1d1d0=i=0di2in = \overline{d_l d_{l-1} \dots d_1 d_0} = \sum_{i=0}^{\infty} d_i \cdot 2^i, where the digits d0,,dld_0, \dots, d_l are all 00 or 11, then
ν(n)=k=1n2k=k=1ldldl1d1d02k=k=1ldldl1dk=k=1l(i=kldi2ik)=i=1ldi(k=1i2ik)=i=1ldi(2i1). \begin{aligned} \nu(n) &= \sum_{k=1}^{\infty} \lfloor \frac{n}{2^k} \rfloor = \sum_{k=1}^{l} \lfloor \frac{\overline{d_l d_{l-1} \dots d_1 d_0}}{2^k} \rfloor = \sum_{k=1}^{l} \overline{d_l d_{l-1} \dots d_k} \\ &= \sum_{k=1}^{l} \left( \sum_{i=k}^{l} d_i \cdot 2^{i-k} \right) = \sum_{i=1}^{l} d_i \left( \sum_{k=1}^{i} 2^{i-k} \right) = \sum_{i=1}^{l} d_i \cdot (2^i - 1). \end{aligned}
Now we will show that there exists an integer rr which is relatively prime to mm, and an infinite sequence i1<i2<i3<i_1 < i_2 < i_3 < \dots of positive integers such that
2i112i212i31rmodm. 2^{i_1} - 1 \equiv 2^{i_2} - 1 \equiv 2^{i_3} - 1 \equiv \dots \equiv r \mod m.
Let m=2tum = 2^t u where uu is odd, and consider an arbitrary positive integer iti \ge t for which φ(u)\varphi(u) divides i1i-1. By the Euler-Fermat theorem,
u2φ(u)12i11,u \mid 2^{\varphi(u)} - 1 \mid 2^{i-1} - 1,
2i1=2(2i11)+11mod u,2^i - 1 = 2(2^{i-1} - 1) + 1 \equiv 1 \quad \text{mod } u,
and, due to iti \ge t,
2i11mod 2t. 2^i - 1 \equiv -1 \quad \text{mod } 2^t.
The relations (1) and (2) determine the residue class of 2i12^i - 1 modulo mm, and it must be relatively prime to mm.
Since mm and rr are relatively prime, there is a positive integer uu such that aurmodma \equiv u r \mod m. For n=2i1++2iun = 2^{i_1} + \cdots + 2^{i_u} we achieve
ν(n)=ν(2i1++2iu)=(2i11)++(2iu1)uramod m. \nu(n) = \nu(2^{i_1} + \cdots + 2^{i_u}) = (2^{i_1} - 1) + \cdots + (2^{i_u} - 1) \equiv u \cdot r \equiv a \quad \text{mod } m.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.