Problems & Puzzles: Puzzles

Puzzle 198. 2^a - 3^b = c

A few days ago Eric Brier sent the following "funny puzzle":

Prove that the equation 2^a - 3^b = 103 has no solutions with a and b integers.

Note: Eric claims to have a proof of it


Formal and complete solution for this puzzle came from Johann Wiesenbauer, Ken Wike and  Santi Spadaro, basically using the same approach:

2^a-3^b = 103 --> 2^a = 103+3^b --> 2^a == 1 (mod 3) Then a must be even: put a=2c.

4^c-3^b = 103 --> 3^b=4^c-103 --> 3^b == -3 == 1(mod 4) Then b must be even: put b=2d.

So we have 2^(2c)-3^(2d) = 103 --> (2^c-3^d)(2^c+3^d) = 103. Since 103 is prime this can only be if:

2^c-3^d = 1

2^c+3^d = 103

Adding the two equations we get 2^(c+1)=104 which can't be since 104 is not a power of two. Then 2^a-3^b = 103 has no solutions in integers.

Another (theoretical-exhaustive) approach came form Joseph L. Pe, based on the analysis of the finite & exhaustive 3 digits endings of 2^a & 3^b.

Proof. The key to the proof is in the following two facts:

Fact A. The sequence of the last three digits of 2^n is eventually periodic with period = 100, that is, 2, 4, 8, ..., 504, 008, ..., 504, 008, ..., 504, .... where 008, ..., 504 is a repeating list of 100 terms. This sequence can be generated by, say, the Mathematica command Table[Mod[2^n, 1000], {n, 1, 200}].

Fact B. The sequence of the last three digits of 3^n is  eventually periodic with period = 100, that is, 3, 9, 27, ..., 001, 003, ..., 001, 003, ..., 001, .... where 003, ..., 001 is a repeating list of 100 terms. This sequence can be generated by, say, the Mathematica command Table[Mod[3^n, 1000], {n, 1, 200}].

Let X be the last three digits of 2^a and Y be the last three digits of 3^b. In the subtraction of 3^b from 2^a, Y will be subtracted from X. This subtraction determines the last three digits of 2^a - 3^b, which are required to be 1, 0, 3.

But there are less than 200 choices for X and less than 200 choices for Y. It is not hard to check exhaustively (say, by a simple computer program) that no choice of X and Y will make 2^a - 3^b end with the digits 1, 0, 3. Therefore, 2^a - 3^b = 103 has no integer solutions.

For example, X can be 648 and Y can be 427, in which case X - Y = 221, and so 2^a - 3^b ends with the digits 221, and cannot equal 103. For a case with borrowing in the subtraction, consider X as 016 and Y as 923. Then the "0" in X must borrow from its left neighbor in 2^a, so that 2^a - 3^b ends with the digits 093 (= 1016 - 923), hence cannot equal 103.

One more approach ("empirical") came for Felice Russo:

I don't have a theoretical proof but an empirical one. The differences 2^n-3^m are the sequences 2^n-3^0, 2^n-3^1, 2^n-3^2, 2^n-3^3............. for n=1,2,3,4,5...... By looking at those sequences (please see the attached file) we can see very easily that for n>8 and m>5 the difference 2^n-3^m is always greater than 103. So the only values that must be checked are very few: 27. None of them is equal to 103 and then the equality 2^n-3^m=103 is never satisfied.

In particular Johann Wiesenbauer could prove a more general statement than the asked by Brier:

... (here) it is proved that 2^a+3^b=c has no integer solutions a,b, whenever c is a prime, but not a Mersenne prime, and c=7 mod 12.

Let's assume that a and b are integer solutions. Viewing this equation mod 3, it becomes (-1)^a=1 mod 3, which proves that a must be even. In particular, since a must be clearly positive, 2^a=0 mod 4 and hence (-1)^b=1 mod 4 proving that b is even as well. As a consequence we have the factorization

c = (2^(a/2)-3^(b/2))(2^(a/2)+3^(b/2))

and a fortiori



since c is a prime and the first factor is clearly smaller than the second one. By adding these two equations we see that c+1 is a power of 2 contradicting our assumption that c is not a Mersenne prime.

c=7 mod 12 is according to the Chinese Remainder Theorem equivalent to the two conditions:

c=1 mod 3 and c=-1 mod 4

and this is exactly what I substituted for c when viewing the equation 2^a-3^b=c mod 3 and mod 4, respectively.


Solutions are still coming! one more from L. T. Pebody and another very close to the first given above from J.C. Rosa:

There are no solutions to 2^a-3^b=103. Look modulo 39. The powers of 2 are 1,2,4,8,16,32,25,11,22,5,10,20. The powers of 3 are 1,3,9,27. 103 is equivalent to 25. Therefore 3^b+103 must be equivalent to 26,28,34 or 13 modulo 39. No solutions exist. (Pebody)

103=52^2-51^2=16*(13^2)-9*(17^2). So the equation 2^a-3^b=103 becomes: 16*(2^(a-4)-169)=9*(3^(b-2)-289) From where 2^(a-4)-169=0 mod 9 and 3^(b-2)-289=0 mod 16 consequently a and b are even.

Let a=2*p ; b=2*q . The equation 2^a-3^b=103 becomes: (2^p)^2-(3^q)^2=103 , but 103 is prime and consequently 2^p=52 and 3^q=51. Impossible . Therefore the equation 2^a-3^b=103 has no solution (Rosa)



Records   |  Conjectures  |  Problems  |  Puzzles