Maths Olympiad Prep

Library / /164 of 397

Number theory Difficulty 5.6 AIME, harder Prove it Taiwan

Let xx and yy be positive integers. Prove that if for all positive integers nn, 2ny+12^n y + 1 divides x2n1x 2^n - 1, then x=1x = 1.

Solution

First we prove that for all positive integers yy, there exist infinitely many primes p3(mod4)p \equiv 3 \pmod 4 such that pp divides some number of the form 2ny+12^n y + 1.

Clearly it suffices to consider the case where yy is odd. Let
2y+1=p1e1prer 2y + 1 = p_1^{e_1} \cdots p_r^{e_r}
be the prime factorization of 2y+12y+1. Suppose there exist finitely many primes pr+1,,pr+s3(mod4)p_{r+1}, \cdots, p_{r+s} \equiv 3 \pmod 4 that divide some number of the form 2ny+12^n y + 1 but do not divide 2y+12y + 1.

We want to find an nn such that piei2ny+1,1irp_i^{e_i} \mid 2^n y + 1, 1 \le i \le r and pi2ny+1,r+1ir+sp_i \nmid 2^n y + 1, r+1 \le i \le r+s. For this it suffices to take
n=1+φ(p1e1+1prer+1pr+11pr+s1), n = 1 + \varphi(p_1^{e_1+1} \cdots p_r^{e_r+1} p_{r+1}^1 \cdots p_{r+s}^1),
since then we would have
2ny+12y+1(modp1e1+1prer+1pr+11pr+s1). 2^n y + 1 \equiv 2y + 1 \pmod{p_1^{e_1+1} \cdots p_r^{e_r+1} p_{r+1}^1 \cdots p_{r+s}^1}.

The last congruence means that p1e1,,prerp_1^{e_1}, \cdots, p_r^{e_r} exactly divide 2ny+12^n y + 1 and that pr+1,,pr+sp_{r+1}, \cdots, p_{r+s} all do not divide 2ny+12^n y + 1. Hence the prime factorization of 2ny+12^n y + 1 contains p1e1,,prerp_1^{e_1}, \cdots, p_r^{e_r} and powers of primes congruent to 1(mod4)1 \pmod 4. Since yy is odd, we obtain
2ny+1p1e1prer2y+13(mod4). 2^n y + 1 \equiv p_1^{e_1} \cdots p_r^{e_r} \equiv 2y + 1 \equiv 3 \pmod 4.
Since n>1n > 1, this is a contradiction. Hence we obtain 2ny+11(mod4)2^n y + 1 \equiv 1 \pmod 4.

If pp is a prime factor of 2ny+12^n y + 1, then for d=2nd = 2^n, we have xd1(mod4)x^d \equiv 1 \pmod 4. By Fermat's little theorem, the same congruence holds for d=p1d = p-1, so it also holds for d=(2n,p1)d = (2^n, p - 1). For p3(mod4)p \equiv 3 \pmod 4 we have (2n,p1)=2(2^n, p - 1) = 2, hence in this case x21(modp)x^2 \equiv 1 \pmod p.

In summary, we have shown that every p3(mod4)p \equiv 3 \pmod 4 that divides some number of the form 2ny+12^n y + 1 also divides x21x^2-1. This is only possible when x=1x=1, otherwise the positive integer x21x^2-1 would have infinitely many prime factors.

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 translated into English from the original; metadata (topic, difficulty) added by this project.