Closed form for CRT solution using Euler $\phi\,$ (totient)

Question

Can anyone show some hints to this? If $\gcd(a,b)=1$, then $a^{\phi(b)}+b^{\phi(a)}=1 \pmod{ab}$. I know that $a^{\phi(b)}=1 \pmod{b}$, and similarly, $b^{\phi(a)}=1 \pmod{a}$, but then how do I combine the work so that I get the result I need? Thanks!

Answer 1

It's $\,(0,1) + (1,0) = (1,1)\,$ in $\,\mathbb Z/a \times \mathbb Z/b\,,\,$ i.e. $\,a^{\phi(b)}\to (0,1)\,$ being $\,0\bmod a\,$ & $\,1\bmod b$

This is the special case $\,\alpha = \beta = 1\,$ in the following form of the Chinese Remainder Theorem:

Theorem (CRT, via Euler $\phi$) $\,\,$ If $\,a,\,b\,$ are coprime integers then

$$x\equiv \alpha\!\!\!\pmod{\!a},\,\ x\equiv\beta\!\!\!\pmod{\!b}\iff x\,\equiv\,\alpha\,b^{\phi(a)}+ \beta\,a^{\phi(b)}\!\!\! \pmod{\!ab}\qquad$$

Proof $\,(\Leftarrow)\,\,$ Immediate from $\,b^{\phi(a)}\equiv 1\pmod{\!a},\,$ $a^{\phi(b)}\equiv 1\pmod{\!b},\,$ $\,\phi(n)\ge 1$.

$\,(\Rightarrow)\,\,$ The solution is unique $\!\bmod ab\,$ since if $\,x',\,x\,$ are solutions then $\,x'\equiv x\,$ mod $\,a,b\,$ therefore $\,a,\,b\,|\,x'-x\,\Rightarrow\,ab\,|\,x'-x\,\,$ since $\,\,a,\,b\,$ coprime $\,\Rightarrow\,{\rm lcm}(a,b) = ab\,.\ \ $ QED

Answer 2

Verify the congruence holds modulo $a$ and modulo $b$. Then use the fact that if $a|k$, $b|k$, and $\gcd(a,b)=1$, then $ab|k$.