1
$\begingroup$

The problem: For all positive integers $a$ and $b$, if $(a, b)=1$, then $(a+b)^{\phi(a)\phi(b)}\equiv(a^{\phi(b)}+b^{\phi(a)}) \pmod{ab}$.

My work thus far. I know that by using Euler's theorem I can show that $(a^{\phi(b)}+b^{\phi(a)})\equiv1 \pmod{ab}$.

I am currently stuck trying to show that $(a+b)^{\phi(a)\phi(b)}\equiv1\pmod{ab}$, and then putting that with my idea above to complete the proof. Can anyone give me any hints or let me know if I am on the right track? Thanks!

$\endgroup$
2
  • 1
    $\begingroup$ Immediate by Euler's little Theorem and CRT. $\endgroup$ May 10 '20 at 1:22
  • $\begingroup$ Could you provide a hint as to how I would apply the CRT? Thank you. $\endgroup$ May 10 '20 at 1:47
2
$\begingroup$

Could you provide a hint as to how I would apply the CRT?

$\!\bmod \color{#c00}a\!:\,\ c:= (\color{#c00}a\!+\!b)^{\phi(b)\phi(a)}\equiv (b^{\phi(b)})^{\phi(a)}\equiv 1\ $ by Euler-phi, by $\,\gcd(b^{\phi(b)},a)=1$

By symmetry, also $\,c\equiv 1\pmod{\!b},\,$ thus $\,c\equiv 1\pmod{\!ab}\,$ by CCRT

Remark $ $ Equivalently, by Euler, $\,\rm LHS-RHS \equiv 1-1\equiv 0\,$ both mod $\,a\,$ & $b,\,$ so it is divisible by $a$ and $b,\,$ so also by their lcm $= ab$, by $\,a,b\,$ coprime, i.e. $\,{\rm LHS\equiv RHS}\pmod{\!ab}$

$\endgroup$
2
  • $\begingroup$ Oh okay, that is much more clear. Thank you. $\endgroup$ May 10 '20 at 2:02
  • 1
    $\begingroup$ @MiltonP. I added another way to view it $\endgroup$ May 10 '20 at 2:07
1
$\begingroup$

First, $(a,b)=1\implies \phi(ab)=\phi(a)\phi(b)$.

Second, $(a,b)=1\implies (ab,a+b)=1$. You can do this by first noting that $(a,a+b)=1=(b,a+b)$. Then apply Proving that $a,n$ and $b, n$ relatively prime implies $ab,n$ relatively prime.

Now you can apply Euler's theorem.

$\endgroup$
1
$\begingroup$

Hint Show that $$(a+b)^{\phi(a)\phi(b)}\equiv(a^{\phi(b)}+b^{\phi(a)})\pmod a$$ and $$(a+b)^{\phi(a)\phi(b)}\equiv(a^{\phi(b)}+b^{\phi(a)})\pmod b$$

$\endgroup$
2
  • $\begingroup$ Ahh I see. So it would be similar to showing that $(a^{\phi(b)}+b^{\phi(a)})\equiv1\,(mod\,ab)$, right? $\endgroup$ May 10 '20 at 1:21
  • $\begingroup$ See my edits to this answer for proper MathJax usage. $\endgroup$ May 10 '20 at 1:54

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.