Maths Olympiad Prep

Library / /285 of 462

Number theory Difficulty 6.0 National Olympiad Prove it Ireland

Find all triples (p,q,r)(p, q, r) of prime numbers that satisfy pqrp \le q \le r and
pqr(7p3p)(7q3q)(7r3r). pqr \mid (7^p - 3^p)(7^q - 3^q)(7^r - 3^r).

Solution

We start with establishing the following statement, which is valid for not necessarily different prime numbers mm and nn:
m7n3nimpliesm=2 or m>n.(5) m \mid 7^n - 3^n \quad \text{implies} \quad m = 2 \text{ or } m > n. \qquad (5)
First note that mm cannot be equal to 33 or 77, hence there exists an integer aa such that 3a7(modm)3a \equiv 7 \pmod m. The assumption 3n7n(modm)3^n \equiv 7^n \pmod m implies an1(modm)a^n \equiv 1 \pmod m, hence ordm(a)n\text{ord}_m(a) \mid n. Because nn is prime, we can only have ordm(a)=1\text{ord}_m(a) = 1 or ordm(a)=n\text{ord}_m(a) = n. When ordm(a)=1\text{ord}_m(a) = 1 we have 37(modm)3 \equiv 7 \pmod m, which is only possible when m=2m = 2. When ordm(a)=n\text{ord}_m(a) = n we recall that we know from Little Fermat that ordm(a)m1\text{ord}_m(a) \le m-1. This gives n<mn < m as desired.

Returning to our problem, we now see that pp must divide 7p3p7^p - 3^p, because pqrp \le q \le r. It follows from (5) that this then is only possible if p=2p = 2. Because (7232)/2=225(7^2 - 3^2)/2 = 2^2 \cdot 5, we obtain
qr225(7q3q)(7r3r). qr \mid 2^2 \cdot 5 \cdot (7^q - 3^q)(7^r - 3^r).
As qrq \le r, by (5) we must have q25(7q3q)q \mid 2 \cdot 5 \cdot (7^q - 3^q) and so q{2,5}q \in \{2, 5\}, by (5) again.

When p=q=2p = q = 2, we have r25(7r3r)r \mid 2 \cdot 5 \cdot (7^r - 3^r) and so r{2,5}r \in \{2, 5\} by (5).

When p=2p = 2 and q=5q = 5, we have to calculate 75357^5 - 3^5. Without a calculator, this can be easily done:
75=49343=50343343=17150343=16807. 7^5 = 49 \cdot 343 = 50 \cdot 343 - 343 = 17150 - 343 = 16807.
35=993=813=2433^5 = 9 \cdot 9 \cdot 3 = 81 \cdot 3 = 243 and 7535=16807243=165647^5 - 3^5 = 16807 - 243 = 16564.

Finally we factorise easily 16564=44141=224110116564 = 4 \cdot 4141 = 2^2 \cdot 41 \cdot 101. This shows that
r241101(7r3r). r | 2 \cdot 41 \cdot 101 \cdot (7^r - 3^r).
From (5) we obtain now that r{2,41,101}r \in \{2, 41, 101\}. But 5=qr5 = q \le r and we are left with r{41,101}r \in \{41, 101\} if p=2p = 2 and q=5q = 5.

This shows that a complete list of solutions (p,q,r)(p, q, r) is
(2,2,2), (2,2,5), (2,5,41), (2,5,101). (2, 2, 2), \ (2, 2, 5), \ (2, 5, 41), \ (2, 5, 101).

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.