Answer to Question #272609 in Combinatorics | Number Theory for Prathibha Rose

Question

If m,n=1,show that m,φn=1

Answer 1

Since $\operatorname{gcd}(m, n)=1,$ you know from Euler-Fermat that

$m^{\varphi(n)} \equiv 1 \quad(\bmod \ n)$

and, similarly,

$n^{\varphi(m)} \equiv 1 \quad(\bmod \ m)$

Since $n^{\varphi(m)} \equiv 0(\bmod n),$ we also have

$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1+0 \quad(\bmod \ n)$

and, similarly,

$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1+0 \quad(\bmod \ m)$