Maths Olympiad Prep

Library / /330 of 520

Number theory Difficulty 6.7 National olympiad Prove it

For a prime pp and a positive integer nn, denote by νp(n)\nu_{p}(n) the exponent of pp in the prime factorization of nn!. Given a positive integer dd and a finite set {p1,,pk}\left\{p_{1}, \ldots, p_{k}\right\} of primes. Show that there are infinitely many positive integers nn such that dνpi(n)d \mid \nu_{p_{i}}(n) for all 1ik1 \leq i \leq k. (India)

Solution

For arbitrary prime pp and positive integer nn, denote by ordp(n)\operatorname{ord}_{p}(n) the exponent of pp in nn. Thus,
νp(n)=ordp(n!)=i=1nordp(i) \nu_{p}(n)=\operatorname{ord}_{p}(n !)=\sum_{i=1}^{n} \operatorname{ord}_{p}(i)
Lemma. Let pp be a prime number, qq be a positive integer, kk and rr be positive integers such that pk>rp^{k}>r. Then νp(qpk+r)=νp(qpk)+νp(r)\nu_{p}\left(q p^{k}+r\right)=\nu_{p}\left(q p^{k}\right)+\nu_{p}(r).
Proof. We claim that ordp(qpk+i)=ordp(i)\operatorname{ord}_{p}\left(q p^{k}+i\right)=\operatorname{ord}_{p}(i) for all 0<ir0 < i \leq r. By the construction of the sequence, pin1p_{i}^{n_{\ell_{1}}} divides n2++nmn_{\ell_{2}}+\ldots+n_{\ell_{m}}; clearly, pin1>n1p_{i}^{n_{\ell_{1}}}>n_{\ell_{1}} for all 1ik1 \leq i \leq k. Therefore the Lemma can be applied for p=pi,k=r=n1p=p_{i}, k=r=n_{\ell_{1}} and qpk=n2++nmq p^{k}=n_{\ell_{2}}+\ldots+n_{\ell_{m}} to obtain
fi(n1+n2++nm)=fi(n1)+fi(n2++nm) for all 1ik f_{i}\left(n_{\ell_{1}}+n_{\ell_{2}}+\ldots+n_{\ell_{m}}\right)=f_{i}\left(n_{\ell_{1}}\right)+f_{i}\left(n_{\ell_{2}}+\ldots+n_{\ell_{m}}\right) \quad \text { for all } 1 \leq i \leq k
and hence
f(n1+n2++nm)=f(n1)+f(n2++nm)=f(n1)+f(n2)++f(nm) f\left(n_{\ell_{1}}+n_{\ell_{2}}+\ldots+n_{\ell_{m}}\right)=f\left(n_{\ell_{1}}\right)+f\left(n_{\ell_{2}}+\ldots+n_{\ell_{m}}\right)=f\left(n_{\ell_{1}}\right)+f\left(n_{\ell_{2}}\right)+\ldots+f\left(n_{\ell_{m}}\right)
by the induction hypothesis.
Now consider the values f(n1),f(n2),f\left(n_{1}\right), f\left(n_{2}\right), \ldots There exist finitely many possible values of ff. Hence, there exists an infinite sequence of indices 1<2<\ell_{1}<\ell_{2}<\ldots such that f(n1)=f(n2)=f\left(n_{\ell_{1}}\right)=f\left(n_{\ell_{2}}\right)=\ldots and thus
f(nm+1+nm+2++nm+d)=f(nm+1)++f(nm+d)=df(n1)=(0,,0) f\left(n_{\ell_{m+1}}+n_{\ell_{m+2}}+\ldots+n_{\ell_{m+d}}\right)=f\left(n_{\ell_{m+1}}\right)+\ldots+f\left(n_{\ell_{m+d}}\right)=d \cdot f\left(n_{\ell_{1}}\right)=(\overline{0}, \ldots, \overline{0})
for all mm. We have found infinitely many suitable numbers.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.