$ \text{\LaTeX}$ed Suppose that the positive integers $ a$ and $ b$ satisfy the equation $ a^b-b^a=1008$ Prove that $ a$ and $ b$ are congruent modulo $ 1008$

It had unique solution $ a=1009,b=1$.

obviously a and b are of the same parity. Let a and b be even.Let a>b IF b is 2 there is no solution, so assume and b to be greater than 2. Then $ a^b/2 + b^a/2$ * $ a^b/2 - b^a/2$ = 1008 But we observe if a and b are even then both $ a^b/2 + b^a/2$ and $ a^b/2 - b^a/2$ are divisible by 4. Let $ a^b/2 + b^a/2$ = 4l and $ a^b/2 - b^a/2$ = 4m Then we get $ 2a^b/2$ is 4(l+m) So $ a^b/2$ = 2(l+m) But l and m can be only one of 1,7,9,63 Checking we get no solutions IF a and b are odd then $ a^b$ is congruent to $ b^a$ mod 1008 So if $ a^b$ is congruent to $ b^a$ mod 1008 then $ a$ is congruent to $ b$ mod 16,7,9 ( i checked all other possibilities by brute force ) So $ a$ is congruent to $ b$ mod 1008

befuddlers u can try for a more elegant soln.

Woohooo! I was the only one who solved it at the contest Easily $ a \equiv b \bmod 2$. If $ 2 \mid a$ then $ \bmod 32$ we know that $ a,b<5$, and so no solutions. So $ a \equiv b \equiv 1 \bmod 2$. Then $ a^b \equiv b^a \bmod 4$ easily follows, since $ \phi(4) = 2$, usw. so $ a \equiv b \bmod 16$. We easily obtain $ a^b \equiv b^a \bmod 3$ since $ a \equiv b \bmod \phi(3) = 2$. And so $ a^b \equiv b^a \bmod 9$ since $ a \equiv b \bmod \phi(9)=6$. Since $ \phi(7) = 6$, we get in the same way $ a^b \equiv b^a \bmod 7$. So $ a^b \equiv b^a \bmod 1008$. QED. Rust wrote: It had unique solution $ a = 1009,b = 1$. I think that it is harder to prove than the original statement...

I didn´t understand anything, Mathias... What is the relation between $ a \equiv b mod \phi(n)$ and $ a^b \equiv b^a mod n$? And what do you mean by "$ a^b \equiv b^a mod 1008$. Q. E. D."? (I don´t know how to copy what you wrote) $ a^b \equiv b^a mod 1008$ is obvious!

feliz wrote: I didn´t understand anything, Mathias... What is the relation between $ a \equiv b mod \phi(n)$ and $ a^b \equiv b^a mod n$? And what do you mean by "$ a^b \equiv b^a mod 1008$. Q. E. D."? (I don´t know how to copy what you wrote) $ a^b \equiv b^a mod 1008$ is obvious! Haha.. Sorry of course it is $ a \equiv b \bmod 1008$. I made that mistake a couple of times, just ignore that If $ (a,n) = 1$, then $ a^{\phi(n)} \equiv 1 \bmod n$. Try searching Eulers phi-function. There's probably a lot of people who can give you a lot better explanation than me ^^

Mathias_DK wrote: Rust wrote: It had unique solution $ a = 1009,b = 1$. I think that it is harder to prove than the original statement... Consider $ b=1$ and get solution $ a=1009$. Consider $ b=2$ $ a^2-2^a=1008$ had not solution. Consider $ a=1$ - had not solution. Consider $ a=2$ $ 2^b-b^2=1008\to 4|b,b\ge 10$, but $ 2^{12}-12^2>1008$, therefore $ a=2$ give not solution. If $ a\ge 3,b\ge 3$, then $ a<b$, because $ a^{1/a}>b^{1/b}$. Consider $ a=3$ $ 3^b-b^3=1008\to 3|b,a=3<b<9$, but $ b=6$ is not solution. Consider $ a=4$ $ 4^b-b^4=1008\to 2|b, a=4<b<6$ give not solution. If $ a\ge 4$, then $ a<b<a+2$. Therefore may be only $ b=a+1$. $ a^{a+1}-(a+1)^a=a^a(a-(1+1/a)^a)>1008$ if $ a\ge 5$.

Rust wrote: Mathias_DK wrote: Rust wrote: It had unique solution $ a = 1009,b = 1$. I think that it is harder to prove than the original statement... Consider $ b = 1$ and get solution $ a = 1009$. Consider $ b = 2$ $ a^2 - 2^a = 1008$ had not solution. Consider $ a = 1$ - had not solution. Consider $ a = 2$ $ 2^b - b^2 = 1008\to 4|b,b\ge 10$, but $ 2^{12} - 12^2 > 1008$, therefore $ a = 2$ give not solution. If $ a\ge 3,b\ge 3$, then $ a < b$, because $ a^{1/a} > b^{1/b}$. Consider $ a = 3$ $ 3^b - b^3 = 1008\to 3|b,a = 3 < b < 9$, but $ b = 6$ is not solution. Consider $ a = 4$ $ 4^b - b^4 = 1008\to 2|b, a = 4 < b < 6$ give not solution. If $ a\ge 4$, then $ a < b < a + 2$. Therefore may be only $ b = a + 1$. $ a^{a + 1} - (a + 1)^a = a^a(a - (1 + 1/a)^a) > 1008$ if $ a\ge 5$. Thanks for your solution on this one

erdugan wrote: Suppose that the positive integers $ a$ and $ b$ satisfy the equation $ a^b - b^a = 1008$ Prove that $ a$ and $ b$ are congruent modulo 1008. Ok. Felix has requested me to clear out my solution, so here it goes: $ a \equiv b \bmod 2$ is obvious. But $ 2 \nmid a,b$. If $ 2 \mid a,b$ then $ a,b \le 5$ (because of $ \bmod 32$) which gives no solution. Then $ a^b \equiv a \bmod 8$, and $ b^a \equiv b \bmod 8$, so $ a \equiv b \bmod 8$. (Notice $ a^4 \equiv 1 \bmod 16$ if $ (a,2) = 1$) Then $ a^b \equiv a^a \bmod 16$ so $ a^a \equiv b^a \bmod 16$. If $ a \equiv 1 \bmod 4$ then $ a \equiv b \bmod 16$. If $ a \equiv 3 \bmod 4$ then $ a^3 \equiv b^3 \bmod 16$ $ \Rightarrow$ $ a \equiv b \bmod 16$. (Multiply with $ ab$ and use that $ a^4 \equiv b^4 \equiv 1 \bmod 16$) Then $ a^b \equiv a \bmod 3$ and $ b^a \equiv b \bmod 3$, because $ a$ and $ b$ are odd. So $ a \equiv b \bmod 3$. We know $ \phi(9) = 6$. If $ a \equiv b \equiv 1 \bmod 6$ then $ a^b \equiv a \bmod 9$ and $ b^a \equiv b \bmod 9$ so $ a \equiv b \bmod 9$. If $ a \equiv b \equiv 5 \bmod 6$. Then $ a^b \equiv a^5 \bmod 9$ and $ b^a \equiv b^5 \bmod 9$. So $ a^5 \equiv b^5 \bmod 9$ $ \Rightarrow$ $ a \equiv b \bmod 9$. (Multiply with $ ab$, and notice $ a^6 \equiv b^6 \equiv 1 \bmod 9$). Since $ \phi(7) = 6$, we get in the same way that $ a \equiv b \bmod 7$. So $ a \equiv b \bmod 16 \cdot 7 \cdot 9 = 1008$.