Maths Olympiad Prep

Library / IRL ABooklet /108 of 191

IRL ABooklet

Number theory Difficulty 6.0 National Olympiad Prove it Ireland

Find all triples (p,q,r)(p, q, r) of prime numbers that satisfy p≤q≤rp \le q \le r and
pqr∣(7p−3p)(7q−3q)(7r−3r). 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:
m∣7n−3nimpliesm=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 3a≡7(modm)3a \equiv 7 \pmod m. The assumption 3n≡7n(modm)3^n \equiv 7^n \pmod m implies an≡1(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 3≡7(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)≤m−1\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 7p−3p7^p - 3^p, because p≤q≤rp \le q \le r. It follows from (5) that this then is only possible if p=2p = 2. Because (72−32)/2=22⋅5(7^2 - 3^2)/2 = 2^2 \cdot 5, we obtain
qr∣22⋅5⋅(7q−3q)(7r−3r). qr \mid 2^2 \cdot 5 \cdot (7^q - 3^q)(7^r - 3^r).
As q≤rq \le r, by (5) we must have q∣2⋅5⋅(7q−3q)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 r∣2⋅5⋅(7r−3r)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 75−357^5 - 3^5. Without a calculator, this can be easily done:
75=49⋅343=50⋅343−343=17150−343=16807. 7^5 = 49 \cdot 343 = 50 \cdot 343 - 343 = 17150 - 343 = 16807.
35=9⋅9⋅3=81⋅3=2433^5 = 9 \cdot 9 \cdot 3 = 81 \cdot 3 = 243 and 75−35=16807−243=165647^5 - 3^5 = 16807 - 243 = 16564.

Finally we factorise easily 16564=4⋅4141=22⋅41⋅10116564 = 4 \cdot 4141 = 2^2 \cdot 41 \cdot 101. This shows that
r∣2⋅41⋅101⋅(7r−3r). 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=q≤r5 = 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.