Maths Olympiad Prep

Library / /19 of 94

Number theory Difficulty 5.2 AIME, harder Prove it Hong Kong

Find all prime numbers pp and qq such that (7p2p)(7q2q)pq\frac{(7^p - 2^p)(7^q - 2^q)}{pq} is an integer.

Solution

The solutions are (p,q)=(5,5),(5,11),(5,61)(p, q) = (5, 5), (5, 11), (5, 61) and their permutations.
If p7p2pp \mid 7^p - 2^p, then p72=5p \mid 7 - 2 = 5 by the Fermat little theorem. This implies p=5p = 5. If we further have q7q2qq \mid 7^q - 2^q, then q=5q = 5 for the same reason. So p=q=5p = q = 5 is a solution. If q5q \ne 5, then q7p2p=16775=52×11×61q \mid 7^p - 2^p = 16775 = 5^2 \times 11 \times 61. Therefore, q=11,61q = 11, 61. By symmetry (p,q)=(11,5),(61,5)(p, q) = (11, 5), (61, 5) are also solutions.

Now we may assume p,q5p, q \ne 5. Then we must have p7q2qp \mid 7^q - 2^q and q7p2pq \mid 7^p - 2^p. WLOG assume qpq \ge p. Consider p7q2qp \mid 7^q - 2^q. Note that (q,p1)=1(q, p - 1) = 1 since qq is a prime and q>p1q > p - 1. Thus, there exists aZ+a \in \mathbb{Z}^+ such that aq1(modp1)aq \equiv 1 \pmod{p-1}. By the Fermat little theorem, we have
77aq=(7q)a(2q)a=2aq2(modp). 7 \equiv 7^{aq} = (7^q)^a \equiv (2^q)^a = 2^{aq} \equiv 2 \pmod{p}.
This forces p=5p = 5, which is a contradiction.

Therefore, the only solutions are (p,q)=(5,5),(5,11),(5,61)(p, q) = (5, 5), (5, 11), (5, 61) and their permutations.

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.