Maths Olympiad Prep

Library / /7 of 155

Number theory Difficulty 4.8 AIME Prove it Saudi Arabia

Prove that there are infinitely many positive integers nn such that nn divides 20172017n112017^{2017^{n}-1}-1 but nn does not divide 2017n12017^{n}-1.

Solution

We will prove that if a>1a>1 is a positive integer such that a1a-1 is not a power of 22, then there are infinitely many positive integers nn such that nn divides aan11a^{a^{n}-1}-1 but nn does not divide an1a^{n}-1. Therefore, the given problem follows directly as an application with a=2017a=2017.

In fact, there is an odd prime divisor pp of a1a-1. Put s=vp(a1)1s=v_{p}(a-1) \geq 1, for any positive integer kk, by LTE we have vp(apk1)=vp(a1)+kv_{p}\left(a^{p^{k}}-1\right)=v_{p}(a-1)+k, this means that n=apk1ps+1n=\frac{a^{p^{k}}-1}{p^{s+1}} is a positive integer. By LTE again,
vp(an1)=vp(a1)+vp(n)=s+vp(a1)+k(s+1)=s+k1k. v_{p}\left(a^{n}-1\right)=v_{p}(a-1)+v_{p}(n)=s+v_{p}(a-1)+k-(s+1)=s+k-1 \geq k.
Thus, pkan1p^{k} \mid a^{n}-1, we get napk1aan11n\mid a^{p^{k}}-1 \mid a^{a^{n}-1}-1. It remains to show that nan1n \nmid a^{n}-1. By above, we can write an1=ps+k1Aa^{n}-1=p^{s+k-1} A and n=pk1Bn=p^{k-1} B for some positive integers A,BA, B coprime to pp. This gives
(n,an1)=(pk1A,pk1B)=1ps(ps+k1A,ps+k1B)=1ps(apk1p,an1) \left(n, a^{n}-1\right)=\left(p^{k-1} A, p^{k-1} B\right)=\frac{1}{p^{s}}\left(p^{s+k-1} A, p^{s+k-1} B\right)=\frac{1}{p^{s}}\left(\frac{a^{p^{k}}-1}{p}, a^{n}-1\right)
which is clearly a divisor of
1ps(apk1,an1)=1ps(a(pk,n)1)=1ps(apk11)<apk1ps+1=n. \frac{1}{p^{s}}\left(a^{p^{k}}-1, a^{n}-1\right)=\frac{1}{p^{s}}\left(a^{\left(p^{k}, n\right)}-1\right)=\frac{1}{p^{s}}\left(a^{p^{k-1}}-1\right)<\frac{a^{p^{k}}-1}{p^{s+1}}=n.
This shows that nn cannot divide an1a^{n}-1. The proof is done. \square

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.