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$

3 Answers 3

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$
6
  • 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$ Commented Jan 24, 2015 at 15:46
  • 1
    $\begingroup$ @barto can you please send a link to that theorem regarding the order please? $\endgroup$
    – arunoruto
    Commented Jan 24, 2015 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$ Commented Jan 24, 2015 at 15:53
  • 1
    $\begingroup$ @Assaultous2 Sorry I fixed my proof $\endgroup$
    – Xoff
    Commented Jan 24, 2015 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
    Commented Jan 24, 2015 at 16:58
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$
2
  • 1
    $\begingroup$ a bit messy and hard to follow, with little justification and explanation, but the proof in itself is correct +1 $\endgroup$ Commented Jan 24, 2015 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$ Commented Jan 24, 2015 at 16:30
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$
5
  • 1
    $\begingroup$ Hmmm, looks a lot like Tien Kha Pham's answer. $\endgroup$ Commented Jan 24, 2015 at 16:03
  • $\begingroup$ Why is this true: $a+b\mid a^a+b^a$? $\endgroup$
    – arunoruto
    Commented Jan 24, 2015 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$ Commented Jan 24, 2015 at 16:05
  • $\begingroup$ @ barto it is essentially Tien Kha Pham's answer $\endgroup$ Commented Jan 24, 2015 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$ Commented Jan 24, 2015 at 16:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .