Fermat's/Euler Problem: Proving Equivalence Modulo pq and ab

[pacdude9]

I've got a pair of (related) problems that are keeping me stumped. The two problems they are asking me to prove are:

$$p^{(q-1)} + q^{(p - 1)} \equiv 1 \; (\!\!\!\!\!\! \mod \, pq)$$

$$a^{\phi(b)} + b^{\phi(a)} \equiv 1<br /> \; (\!\!\!\!\!\! \mod \, ab)$$

Where $$\phi(n)$$ is Euler's Totient Function.

I know that these are similar, as the second problem is using Euler's Theorem, a generalization of Fermat's Little Theorem, I just can't seem to figure them out.

 

[happyg1]

for the first one, see if this helps...

By Fermat's Theorem (assuming that p and p are relatively prime...) we have
$$q^p=q$$mod $$p$$. We can cancel q from both sides since gcd(q,p) = 1, so $$q^{(p-1)} = 1 (mod p)$$. Also $$p^{(q-1)} = 0 (mod p)$$ we get

$$p^{(q-1)} + q^{(p-1)} = 1 (mod p)$$

can you go from there?