Maths Olympiad Prep

Library / /12 of 36

Number theory Difficulty 5.7 AIME, harder Prove it Saudi Arabia

Prove that there are infinitely many primes pp such that each of them divides an integer of the form 3n23^n - 2, but does not divide any integer of the form 2m32^m - 3, where mm and nn are positive integers.

Solution

We show the stronger result that the set of prime p±5(mod12)p \equiv \pm 5 \pmod{12} such that p9n2p \mid 9^n - 2 for some nn (since 9=329 = 3^2, we can work with 99 instead of 33, by restricting to even exponents), but p2m3p \nmid 2^m - 3 for any mm, is infinite.

Note that if p9n2p \mid 9^n - 2 for some nn, then 9nm2m3(modp)9^{nm} \equiv 2^m \equiv 3 \pmod p would imply that 33 is a quadratic residue mod pp, which contradicts p±5(mod12)p \equiv \pm 5 \pmod{12}. (The latter can be easily checked using the law of quadratic reciprocity.)

Thus, it suffices to justify that the set of primes p±5(mod12)p \equiv \pm 5 \pmod{12} that divide 9n29^n - 2 for some nn is infinite. Suppose these primes are finite, say p1,,pkp_1, \dots, p_k (there is at least one such prime, for instance, p=7p = 7 for n=1n = 1). Then, for n=i=1k(pi1)>1n = \prod_{i=1}^k (p_i - 1) > 1, we have 9n1(modpi)9^n \equiv 1 \pmod{p_i} by Fermat's little theorem, which implies pi9n2p_i \nmid 9^n - 2 for each ii. However, 9n27(mod12)9^n - 2 \equiv 7 \pmod{12} must have a prime divisor q±5(mod12)q \equiv \pm 5 \pmod{12} (if all prime factors were ±1(mod12)\pm 1 \pmod{12}, their product with multiplicities yields 9n2±1(mod12)9^n - 2 \equiv \pm 1 \pmod{12}, a contradiction), distinct from each pip_i. The desired result follows. \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 reproduced verbatim; metadata (topic, difficulty) added by this project.