2
$\begingroup$

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!

$\endgroup$
3
  • 13
    $\begingroup$ You have posted 8 questions so far, accepted none of them, and been posting for a week. Could you please write your posts as questions rather than orders? And if you find that your previous questions have been satisfactorily answered, then please consider accepting the answer you find most helpful. See the FAQ on accepting answers. $\endgroup$ Feb 17, 2011 at 20:31
  • 2
    $\begingroup$ Thanks for going through your old posts, and thank you for editing the question. Instead of looking at each summand separately, consider the entire sum $a^{\phi(b)}+b^{\phi(a)}$ modulo $a$ and modulo $b$, as Bill and I both suggested below. $\endgroup$ Feb 18, 2011 at 4:54
  • $\begingroup$ @Arturo Magidin: Thank you a lot for guiding me within this wonderful math forum. $\endgroup$
    – kira
    Feb 18, 2011 at 5:06

2 Answers 2

13
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Can you think of another formula given some other known multiplicative arithmetic function such as $\omega(n)$? $\endgroup$ Jun 13, 2021 at 5:13

You must log in to answer this question.

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