Maths Olympiad Prep

Library / Balkan Mathematical Olympiad /2 of 6

Balkan Mathematical Olympiad

Number theory Difficulty 5.7 AIME, harder Prove it North Macedonia

Find all primes pp and qq such that 3pq−13p^{q-1} divides 11p+17p11^p+17^p.

Solution

For p=2p=2 it is directly checked that there are no solutions. Assume that p>2p>2. Observe that N=11p+17p≡4(mod8)N=11^p+17^p \equiv 4 \pmod 8, so 8∤3pq−1+1>48 \nmid 3p^{q-1}+1 > 4. Consider an odd prime divisor rr of 3pq−1+13p^{q-1}+1. Obviously, r∉{3,11,17}r \notin \{3,11,17\}. There exist bb such that 17b≡1(modr)17b \equiv 1 \pmod r. Then r∣bpN≡ap+1(modr)r|b^pN \equiv a^p+1 \pmod r,

where a=11ba=11b. Thus r∣a2p−1r|a^{2p}-1, but r∤ap−1r \nmid a^p-1, which means that ord⁡r(a)∣2p\operatorname{ord}_r(a)|2p and ord⁡r(a)∤p\operatorname{ord}_r(a) \nmid p, i.e. ord⁡r(a)∈{2,2p}\operatorname{ord}_r(a) \in \{2,2p\}.

Note that if ord⁡r(a)=2\operatorname{ord}_r(a)=2, then r∣a2−1≡(112−172)b2(modr)r|a^2-1 \equiv (11^2-17^2)b^2 \pmod r, which gives r=7r=7 as the only possibility. On the other hand, ord⁡r(a)=2p\operatorname{ord}_r(a)=2p implies 2p∣r−12p|r-1. Thus, all prime divisors of 3pq−1+13p^{q-1}+1 other than 22 or 77 are congruent to 11 modulo 2p2p, i.e.
3pq−1+1=2α7βp1γ1p2γ2⋯pkγk,(∗) 3p^{q-1}+1=2^{\alpha}7^{\beta}p_1^{\gamma_1}p_2^{\gamma_2}\cdots p_k^{\gamma_k}, \quad (*)
where pi∉{2,7}p_i \notin \{2,7\} are prime divisors with pi≡1(mod2p)p_i \equiv 1 \pmod{2p}.

11p+17p28=11p−1−11p−217+11p−3172−⋯+17p−1≡p4p−1(mod7), \frac{11^p+17^p}{28}=11^{p-1}-11^{p-2}17+11^{p-3}17^2-\dots+17^{p-1} \equiv p4^{p-1} \pmod 7,
so 11p+17p11^p+17^p is not divisible by 727^2 and hence β≤1\beta \le 1.
If q=2q=2, then (∗)(*) becomes 3p+1=2α7βp1γ1p2γ2⋯pkγk3p+1=2^{\alpha}7^{\beta}p_1^{\gamma_1}p_2^{\gamma_2}\cdots p_k^{\gamma_k}, but pi≥2p+1p_i \ge 2p+1, which is only possible if γi=0\gamma_i=0 for all ii, i.e. 3p+1=2α7β∈{2,4,14,28}3p+1=2^{\alpha}7^{\beta} \in \{2,4,14,28\}, which gives us no solutions.
Thus q>2q>2, which implies 4∣3pq−1+14|3p^{q-1}+1, i.e. α=2\alpha=2. Now the right hand side of (∗)(*) is congruent to 44 or 2828 modulo pp, which gives us p=3p=3. Consequently 3q+1≡6244(mod3)3^q+1 \equiv 6244 \pmod{3} which is only possible for q=3q=3. The pair (p,q)=(3,3)(p,q)=(3,3) is indeed a solution.

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.