Let m and n be relatively prime positive integers Prove mphi

Let m and n be relatively prime positive integers. Prove: m^phi(n) + n^phi(m) 1 (mod mn).

Solution

According to Euler\'s Theorem,we know that

m^(n) = 1 (mod n)   and n^(m) = 1 (mod m) ;

But,
m^(n) = 0 (mod m) and   n^(m) = 0 (mod n)

Therefore,

m^(n) + n^(m) = 1 (mod m)    and    m^(n) + n^(m) = 1 (mod n)

Since m and n are relatively prime,

m^(n) + n^(m) = 1 (mod mn)