Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
13  
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. –  Arturo Magidin Feb 17 '11 at 20:31
    
Thanks for advice! –  kira Feb 17 '11 at 20:32
2  
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. –  Arturo Magidin Feb 18 '11 at 4:54
    
@Arturo Magidin: Thank you a lot for guiding me within this wonderful math forum. –  kira Feb 18 '11 at 5:06
add comment

2 Answers 2

up vote 5 down vote accepted

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

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

THEOREM (CRT) $\rm\ \ $ If $\rm\ a,\:b\:$ are coprime integers then

$\rm\displaystyle\quad\quad\quad\quad\quad x\equiv \alpha\ (mod\ a),\ \ x\equiv \beta\ (mod\ b)\ \ \iff\ \ x\ \equiv\ \alpha\ b^{\phi(a)}+ \beta\ a^{\phi(b)} \ \ (mod\ a\:b)$

Proof $\rm\ (\Leftarrow)\ \ $ Immediate from $\rm\ b^{\phi(a)}\equiv 1\ (mod\ a),\ \ a^{\phi(b)}\equiv 1\ (mod\ b)\:$.

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

share|improve this answer
    
Thanks a lot! –  kira Feb 18 '11 at 5:10
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.