# eulers theorem problem

• June 29th 2009, 01:20 PM
silentbob
eulers theorem problem
show that a^phi(b) + b^phi(a) is congruent to 1 (mod ab), if a and b are relatively prime positive integers
• June 29th 2009, 01:40 PM
Bruno J.
Hint

Use Euler's theorem to show :

$a^{\phi(b)}+b^{\phi(a)} \equiv 1 \mod a$
$a^{\phi(b)}+b^{\phi(a)} \equiv 1 \mod b$

and conclude that $a^{\phi(b)}+b^{\phi(a)} \equiv 1 \mod ab$.
• June 29th 2009, 08:55 PM
silentbob
how can I prove that a^phi(b) + b^phi(a) is congruent to 1 (mod a (or b))?
• June 29th 2009, 09:13 PM
o_O
Euler's theorem: $(a,b) = 1 \ \Rightarrow \ a^{\phi (b)} \equiv 1 \ (\text{mod } b)$

Clearly: $b \mid b^{\phi (a)} \ \Leftrightarrow \ b^{\phi (a)} \equiv 0 \ (\text{mod } b)$

So: $a^{\phi (b)} + b^{\phi (a)} \equiv 1 + 0 \equiv 1 \ (\text{mod } b)$
• June 30th 2009, 12:34 AM
Moo