# Math Help - eulers theorem problem

1. ## 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

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

3. how can I prove that a^phi(b) + b^phi(a) is congruent to 1 (mod a (or b))?

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