Maths Olympiad Prep

Library / /1 of 2

Number theory Difficulty 5.7 AIME, harder Prove it North Macedonia

Find all primes pp and qq such that 3pq13p^{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+17p4(mod8)N=11^p+17^p \equiv 4 \pmod 8, so 83pq1+1>48 \nmid 3p^{q-1}+1 > 4. Consider an odd prime divisor rr of 3pq1+13p^{q-1}+1. Obviously, r{3,11,17}r \notin \{3,11,17\}. There exist bb such that 17b1(modr)17b \equiv 1 \pmod r. Then rbpNap+1(modr)r|b^pN \equiv a^p+1 \pmod r,

where a=11ba=11b. Thus ra2p1r|a^{2p}-1, but rap1r \nmid a^p-1, which means that ordr(a)2p\operatorname{ord}_r(a)|2p and ordr(a)p\operatorname{ord}_r(a) \nmid p, i.e. ordr(a){2,2p}\operatorname{ord}_r(a) \in \{2,2p\}.

Note that if ordr(a)=2\operatorname{ord}_r(a)=2, then ra21(112172)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, ordr(a)=2p\operatorname{ord}_r(a)=2p implies 2pr12p|r-1. Thus, all prime divisors of 3pq1+13p^{q-1}+1 other than 22 or 77 are congruent to 11 modulo 2p2p, i.e.
3pq1+1=2α7βp1γ1p2γ2pkγ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 pi1(mod2p)p_i \equiv 1 \pmod{2p}.

11p+17p28=11p111p217+11p3172+17p1p4p1(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γ2pkγk3p+1=2^{\alpha}7^{\beta}p_1^{\gamma_1}p_2^{\gamma_2}\cdots p_k^{\gamma_k}, but pi2p+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 43pq1+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+16244(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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.