Maths Olympiad Prep

Library / /12 of 21

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 3n−23^n - 2, but does not divide any integer of the form 2m−32^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 p∣9n−2p \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 p∤2m−3p \nmid 2^m - 3 for any mm, is infinite.

Note that if p∣9n−2p \mid 9^n - 2 for some nn, then 9nm≡2m≡3(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 9n−29^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(pi−1)>1n = \prod_{i=1}^k (p_i - 1) > 1, we have 9n≡1(modpi)9^n \equiv 1 \pmod{p_i} by Fermat's little theorem, which implies pi∤9n−2p_i \nmid 9^n - 2 for each ii. However, 9n−2≡7(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 9n−2≡±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.