Show that m^φ(n)+n^φ(m) ≡1 mod mn (If m and n are relatively prime pos integers)?
If m and n are relatively prime positive integers, show that
m^φ(n) + n^φ(m) ≡ 1 mod mn
If φ(n) = # of positive integers < = to n that are relatively prime to n
φ(n) = (p^k)-(p^k-1)
More Questions From This User See All
Answers & Comments
Verified answer
Since gcd(m,n) = 1, Euler's theorem gives m^φ(n) = 1 (mod n) and n^φ(m) = 1 (mod m). So we have m^φ(n) - 1 = 0 (mod n) and n^φ(m) - 1 = 0 (mod m). Therefore
(m^φ(n) - 1)(n^φ(m) - 1) = 0 (mod mn),
m^φ(n) n^φ(m) - (m^φ(n) + n^φ(m)) + 1 = 0 (mod mn),
m^φ(n) + n^φ(m) = 1 + m^φ(n) n^φ(m) (mod mn).
Since m^φ(n) n^φ(m) = 0 (mod mn), we deduce
m^φ(n) + n^φ(m) = 1 (mod mn).