# 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.

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, 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 ? " Commented Jan 24, 2015 at 15:46
• @barto can you please send a link to that theorem regarding the order please? Commented Jan 24, 2015 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 Commented Jan 24, 2015 at 15:53
• @Assaultous2 Sorry I fixed my proof
– Xoff
Commented Jan 24, 2015 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$. Commented Jan 24, 2015 at 16:58

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 Commented Jan 24, 2015 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$. Commented Jan 24, 2015 at 16:30

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. Commented Jan 24, 2015 at 16:03
• Why is this true: $a+b\mid a^a+b^a$? Commented Jan 24, 2015 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$. Commented Jan 24, 2015 at 16:05
• @ barto it is essentially Tien Kha Pham's answer Commented Jan 24, 2015 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. Commented Jan 24, 2015 at 16:07