# Show that $(a+b)^{\phi(a)\phi(b)}\equiv(a^{\phi(b)}+b^{\phi(a)})\pmod{ab}$.

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!

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

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

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

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.

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

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