Maths Olympiad Prep

Library / /5 of 22

Number theory Difficulty 5.8 AIME, harder Prove it Croatia

Determine all pairs (m,n)(m, n) of positive integers such that
2m=7n2+1.2^m = 7n^2 + 1.

Solution

Note that 2m1(mod7)2^m \equiv 1 \pmod{7}, which means that m=3km = 3k for some positive integer kk. Now we have
23k1=(2k1)(22k+2k+1)=7n2. 2^{3k} - 1 = (2^k - 1)(2^{2k} + 2^k + 1) = 7n^2.
Denote A=2k1A = 2^k - 1 and B=22k+2k+1B = 2^{2k} + 2^k + 1. Let dd be the greatest common divisor of AA and BB, and note that dd is odd. Furthermore, dd divides BA2=2k+2k+1=32kB - A^2 = 2^k + 2^{k+1} = 3 \cdot 2^k, and since dd is odd, it follows that d=1d = 1 or d=3d = 3.
Therefore, we have exactly four possibilities for factorising AA and BB. In all cases we assume that aa and bb are relatively prime positive integers.

Case 1. A=7a2A = 7a^2 and B=b2B = b^2. This is not possible because (2k)2<B<(2k+1)2(2^k)^2 < B < (2^k + 1)^2, i.e. BB cannot be a perfect square.

Case 2. A=a2A = a^2 and B=7b2B = 7b^2. If k2k \ge 2, note that B1(mod4)B \equiv 1 \pmod{4}, i.e. 7b21(mod4)7b^2 \equiv 1 \pmod{4}, which is not possible. Therefore, k=1k = 1 and we get (m,n)=(3,1)(m, n) = (3, 1).

Case 3. A=21a2A = 21a^2 and B=3b2B = 3b^2. Analogously to the previous case we can conclude that k=1k=1 necessarily, but that is not possible in this case, since 21a2=A=211=121a^2 = A = 2^1 - 1 = 1.

Case 4. A=3a2A = 3a^2 and B=21b2B = 21b^2. Therefore, AA is divisible by 33, i.e. 2k1(mod3)2^k \equiv 1 \pmod{3}, from which it follows that k=2lk=2l for some positive integer ll. Now we have
(2l1)(2l+1)=3a2, (2^l - 1)(2^l + 1) = 3a^2,
and since 2l12^l - 1 and 2l+12^l + 1 are relatively prime, we have only two possibilities:
2l1=c22l+1=3d2or2l1=3c22l+1=d2, \begin{aligned} 2^l - 1 &= c^2 \\ 2^l + 1 &= 3d^2 \end{aligned} \quad \text{or} \quad \begin{aligned} 2^l - 1 &= 3c^2 \\ 2^l + 1 &= d^2, \end{aligned}
where cc and dd are relatively prime positive integers.

In the first option, if l2l \ge 2 we have 3d21(mod4)3d^2 \equiv 1 \pmod{4}, which is not possible. Therefore, l=1l=1 and we get another solution (m,n)=(6,3)(m,n) = (6,3).

In the second option, we have 2l=(d1)(d+1)2^l = (d-1)(d+1). Since the greatest common divisor of d1d-1 and d+1d+1 is at most 22 and their product is a power of 22, we can conclude that d1=2d-1=2, i.e. that l=3l=3, but then 3c2=231=73c^2 = 2^3 - 1 = 7, which is not possible.

Finally, all solutions of the given equation are (m,n)=(3,1)(m,n) = (3,1) and (m,n)=(6,3)(m,n) = (6,3).

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.