# Prove that $a+b$ can't divide $a^a+b^b$ nor $a^b+b^a$

Let a and b be natural numbers so that $2a-1,2b-1$ and $a+b$ are prime numbers. Prove that $a+b$ can't divide $a^a+b^b$ nor $a^b+b^a$.

I get that $gcd(a,b)=1$. I haven't got anything special for now but if I do I will update the question.

Since $2a-1, 2b-1$ are primes, then $a,b\neq 1$. Since $a+b$ is a prime, then we can suppose $a$ is even and $b$ is odd.

Suppose $p=a+b|a^a+b^b$. We have: $$a^a+b^b\equiv a^a-a^b=a^b(a^{a-b}-1) \pmod {a+b}$$

Since $\gcd(a^b,a+b)=1$, then $p|a^{a-b}-1$. Let $h=ord_p(a)$, then $h|p-1,h|a-b$, then $h|p-1-(a-b)=2b-1$, thus $h=1$ or $h=2b-1$.

If $h=1$, then $a+b|a-1$, but this is impossible since $a+b>a-1$.

Then $h=2b-1$, which means $p|a^{2b-1}-1$. Hence $p|a^{2a-1}(a^{2b-1}-1)=a^{2a+2b-2}-2^{2a-1}$, then $p|2^{2a-1}-1$. Thus $2b-1|2a-1$, or $2a-1=2b-1$ (since they are both primes), or $a=b$, which is impossible.

Proving $a+b \not|a^b+b^a$ is similar.

• a bit messy and hard to follow, with little justification and explanation, but the proof in itself is correct +1 – Asier Calbet Jan 24 '15 at 16:00
• Something needs to be fixed, since you can't assume wlog that $a$ is even and $a<b$ throughout the proof. One way is to take absolute values when you start considering $a-b$. – punctured dusk Jan 24 '15 at 16:30

Let $p=a+b$, and suppose that $p$ divides at least one of $a^a+b^b$ or $a^b+b^a$.

Then $p$ divides the product $$(a^a+b^b)(a^b+b^a)=a^p+b^p+(ab)^a+(ab)^b$$

• $a^p= a\mod p$
• $b^p= b\mod p$
• $a^p+b^p= a+b = 0 \mod p$

So (remember we suppose that $p$ divides the product) we have : $$(ab)^a+(ab)^b=0\mod p$$

But $b=-a\mod p$.

$$(-a^2)^a+(-a^2)^b=0 \mod p$$

As $a+b$ is odd, one of $a$ and $b$ is odd and the other is even. So

$$a^{2a}=a^{2b} \mod p$$

it means that $2b-2a$ is multiple of the order $r$ of $a$, and that order $r$ divides $p-1=a+b-1$. But if $r$ divides $(2b-1)-(2a-1)$ and $2(a+b-1)=(2a-1)+(2b-1)$, then either $r=2$ or it divides $2a-1$ and $2b-1$ (they are both different prime numbers) so $r=1$.

So $a=1\mod p$ or $a=-1\mod p$. But $a+b=p$. So $a<p$, so $a=1$ (but then $2a-1$ is not prime) or $a=p-1$ (but then $2b-1$ is not prime), this is not possible.

A contradiction. So, our first hypothesis that $p$ divides the product is false.

• Excellent proof. Just one question... what is the justification for " As 2a-1 and 2b-1 are prime numbers, (ab) = 1 mod p ? " – Asier Calbet Jan 24 '15 at 15:46
• @barto can you please send a link to that theorem regarding the order please? – HeatTheIce Jan 24 '15 at 15:52
• sorry, there is a flaw in this proof.... both 3 and 5 are primes, and 2^5 = 2^3 mod 3, but 2=1 mod 3 is false.... so the argument is invalid – Asier Calbet Jan 24 '15 at 15:53
• @Assaultous2 Sorry I fixed my proof – Xoff Jan 24 '15 at 16:26
• If $r$ divides $(2b-1)-(2a-1)$ and $(2b-1)+(2a-1)$, then $r\mid \gcd(2(2a-1),2(2b-1))=2$ and $r$ could be $2$. You haven't checked the case $r=2$. – user26486 Jan 24 '15 at 16:58

Case $a+b\mid a^a+b^b$
Suppose $a$ is odd. Because $a+b\mid a^a+b^a$ we have $a+b\mid b^b-b^a$, hence $a+b\mid b^{|b-a|}-1$ because $\gcd(a,b)=1$, hence $a-b\mid a+b-1$ by Fermat. By symmetry, we get the same if $b$ is odd.
Case $a+b\mid a^b+b^a$
Suppose $a$ is odd. Because $a+b\mid a^a+b^a$ we have $a+b\mid a^b-a^a$. As before we get $a-b\mid a+b-1$. The same if $b$ is odd.

Either way, we have $a-b\mid a+b-1$ from which $a-b\mid a+b-1+(a-b)=2b-1$ and $a-b\mid 2a-1$, hence $a-b=\pm\,1$, that is, $2a-1$ and $2b-1$ are twin primes.
Wlog suppose $b=a+1$. Let $q=a+b=2b-1$. Modulo $q$, $$a^a+b^b\equiv\left(\frac{-1}2\right)^{\frac{q-1}2}+\left(\frac{1}2\right)^{\frac{q+1}2}\equiv\pm\,1\pm\,\frac12\not\equiv0\pmod q$$ and $$a^b+b^a\equiv\left(\frac{-1}2\right)^{\frac{q+1}2}+\left(\frac{1}2\right)^{\frac{q-1}2}\equiv\pm\,\frac12\pm\,1\not\equiv0\pmod q$$ since $q>3$, a contradiction.

• Hmmm, looks a lot like Tien Kha Pham's answer. – punctured dusk Jan 24 '15 at 16:03
• Why is this true: $a+b\mid a^a+b^a$? – HeatTheIce Jan 24 '15 at 16:03
• In general for $n$ odd, $a+b\mid(a+b)(a^{n-1}-a^{n+2}ba^n+\cdots +(-b)^{n-1})=a^n+b^n$. Alternatively, modulo $a+b$, $a^n+b^n\equiv a^n+(-a)^n\equiv0$. – punctured dusk Jan 24 '15 at 16:05
• @ barto it is essentially Tien Kha Pham's answer – Asier Calbet Jan 24 '15 at 16:07
• I know, this mobile device is so slow at processing mathjax that it took me way too much time to write it down. The ending is a bit different though. – punctured dusk Jan 24 '15 at 16:07