Prove that if gcd(m,n)=1 then m^phi(n)+n^phi(m)=congruent 1 (mod mn)
If GCD(a,r) = 1 then
a^phi(r) = 1 mod r,
therefore:
m^phi(n)+n^phi(m) mod n = 1
and
m^phi(n)+n^phi(m) mod m = 1
So, mod(nm) it is 1.
To prove the given statement, we need to show that if the greatest common divisor (gcd) of two positive integers m and n is 1, then m^φ(n) + n^φ(m) ≡ 1 (mod mn), where φ is the Euler's totient function.
First, we can simplify the expression using Euler's theorem. Euler's theorem states that if a and n are coprime positive integers, then a^φ(n) ≡ 1 (mod n).
Since gcd(m, n) = 1, we can apply Euler's theorem for both m and n individually:
m^φ(n) ≡ 1 (mod n) ...(1)
n^φ(m) ≡ 1 (mod m) ...(2)
Now, multiplying equations (1) and (2), we can get:
m^φ(n) * n^φ(m) ≡ 1 (mod mn)
Next, we need to prove that m^φ(n) * n^φ(m) ≡ 1 (mod mn).
We can use the property of Euler's totient function, which states that if m and n are coprime, then φ(mn) = φ(m) * φ(n).
Therefore,
m^φ(n) * n^φ(m) = 1 (mod mn)
Hence, we have proven that if gcd(m, n) = 1, then m^φ(n) + n^φ(m) ≡ 1 (mod mn).