Wednesday, March 1, 2006

Solve it. Topic: Number Theory. Level: Olympiad.

Problem: (WOOT Test 7 - #3) Find all ordered pairs $ (x,y) $ of positive integers such that $ 2^x = 3^y+7 $.

Solution: We claim that $ (x,y) = (4,2) $ is the only solution.

Clearly $ x = 1 $ does not work, so assume $ x>1 $.

Taking the equation $ \pmod{4} $, we have

$ 0 \equiv 3^y+3 \pmod{4} \Rightarrow y \equiv 0 \pmod{2} $.

Taking it $ \pmod{3} $, we have

$ 2^x \equiv 1 \pmod{3} \Rightarrow x \equiv 0 \pmod{2} $.

Let $ x = 2a, y = 2b $. Then

$ 2^{2a} = 3^{2b}+7 $, or

$ (2^a-3^b)(2^a+3^b) = 7 $.

Since $ 2^a+3^b > 0 $, we must have $ 2^a-3^b > 0 $ as well. But if $ a > 2 $ or $ b > 1 $, we have $ 2^a+3^b > 7 $, a contradiction. Checking $ a = 1,2 $; $ b = 1 $ we find $ (a,b) = (2,1) $ is the only solution.

Hence $ (x,y) = (2a, 2b) = (4,2) $ is the only solution, as claimed. QED.

--------------------

Comment: It's usually a good idea to work with mods in diophantine equations to reduce your possible answers. In this case, it worked out nicely because they were both even and we could factor the difference of two squares.

--------------------

Practice Problem: Go take the 2006 Mock AIME 5 below.

2 comments:

  1. Why did you use mod 4?

    ReplyDelete
  2. Well I tried mod 2 but that obviously doesn't give you anything helpful, so I went to mod 4 and it worked...

    ReplyDelete