Maths Olympiad Prep

Library / /5 of 22

Number theory Difficulty 7.8 National Olympiad, round 2 Prove it Germany

Problem:
Determine all pairs (m,n)(m, n) of non-negative integers satisfying the equation
3m7n=2 3^{m}-7^{n}=2

Solution

Solution:
The pairs (1,0)(1,0) and (2,1)(2,1) are solutions. Let (m,n)(m, n) be a solution with m,n2m, n \geq 2. The solution consists of three steps:

1. We have 7n2mod9n1mod37^{n} \equiv -2 \bmod 9 \Longleftrightarrow n \equiv 1 \bmod 3.
2. We have 3m2mod49m26mod423^{m} \equiv 2 \bmod 49 \Longleftrightarrow m \equiv 26 \bmod 42.
3. The conditions from 1 and 2 yield a contradiction modulo 43.

Step 1: We have 7177^{1} \equiv 7, 7247^{2} \equiv 4 and 731mod97^{3} \equiv 1 \bmod 9, and from then on the residues are periodic with period 3. From the original equation it follows that 7n7mod97^{n} \equiv 7 \bmod 9, hence n1mod3n \equiv 1 \bmod 3.

Step 2: First show m2mod6m \equiv 2 \bmod 6 analogously to Step 1. By the Euler-Fermat theorem 3421mod493^{42} \equiv 1 \bmod 49, so the period is at most 42. Using 366mod493^{6} \equiv -6 \bmod 49 one obtains:

mm281420263238
3mmod493^{m} \bmod 49944301623723

Thus 3m2mod493^{m} \equiv 2 \bmod 49 holds exactly when m26mod42m \equiv 26 \bmod 42.

Step 3: Write m=42m+26m=42 m' + 26 and n=3n+1n=3 n' + 1. Considering the original equation modulo 43, one obtains, using Fermat's little theorem and 731mod437^{3} \equiv -1 \bmod 43,

342m+2673n+1326(1)n715(1)n7≢2mod43 3^{42 m' + 26} - 7^{3 n' + 1} \equiv 3^{26} - (-1)^{n'} \cdot 7 \equiv 15 - (-1)^{n'} \cdot 7 \not\equiv 2 \quad \bmod 43

Hence there are no further solutions.

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 translated into English from de; metadata (topic, difficulty) added by this project.