12
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ a bit messy and hard to follow, with little justification and explanation, but the proof in itself is correct +1 $\endgroup$ – Asier Calbet Jan 24 '15 at 16:00
  • 4
    $\begingroup$ 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$. $\endgroup$ – punctured dusk Jan 24 '15 at 16:30
9
$\begingroup$

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 $$

By Fermat's little theorem

  • $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.

$\endgroup$
  • 1
    $\begingroup$ Excellent proof. Just one question... what is the justification for " As 2a-1 and 2b-1 are prime numbers, (ab) = 1 mod p ? " $\endgroup$ – Asier Calbet Jan 24 '15 at 15:46
  • 1
    $\begingroup$ @barto can you please send a link to that theorem regarding the order please? $\endgroup$ – HeatTheIce Jan 24 '15 at 15:52
  • 3
    $\begingroup$ 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 $\endgroup$ – Asier Calbet Jan 24 '15 at 15:53
  • 1
    $\begingroup$ @Assaultous2 Sorry I fixed my proof $\endgroup$ – Xoff Jan 24 '15 at 16:26
  • 2
    $\begingroup$ 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$. $\endgroup$ – user26486 Jan 24 '15 at 16:58
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Hmmm, looks a lot like Tien Kha Pham's answer. $\endgroup$ – punctured dusk Jan 24 '15 at 16:03
  • $\begingroup$ Why is this true: $a+b\mid a^a+b^a$? $\endgroup$ – HeatTheIce Jan 24 '15 at 16:03
  • 2
    $\begingroup$ 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$. $\endgroup$ – punctured dusk Jan 24 '15 at 16:05
  • $\begingroup$ @ barto it is essentially Tien Kha Pham's answer $\endgroup$ – Asier Calbet Jan 24 '15 at 16:07
  • 1
    $\begingroup$ 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. $\endgroup$ – punctured dusk Jan 24 '15 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.