# If $m$ and $n$ are relatively prime positive integers, prove that $m^{\phi(n)}+n^{\phi(m)}\equiv1\pmod{mn}$ [duplicate]

I have found this question answered before but I am stuck going from

$$m^{\phi(n)}+n^{\phi(m)}\equiv1 \pmod{n}\\ n^{\phi(m)}+m^{\phi(n)}\equiv1 \pmod{m}$$ to $$m^{\phi(n)}+n^{\phi(m)}\equiv1 \pmod{mn}$$

Why can we combine $$\pmod{m}$$ and $$(\pmod{n}$$ into $$\pmod{mn}$$? I know it's overall because $$\gcd(m,n)=1$$, but I don't understand why it is so. Is there a theorem for this specifically? I found this, but this seems to not multiply what is in the modulus together.

Here is the beginning of my proof:

$$\gcd(m,n)=1\implies m^{\phi(n)}\equiv1 \pmod{n}$$ and $$n^{\phi(m)}\equiv1 \pmod{m}$$ by Euler's theorem.

$$m^{\phi(n)}\equiv1 \pmod{n} \equiv m^{\phi(n)}+n^{\phi(m)}\equiv1+n^{\phi(m)}\pmod{n}$$ and $$n^{\phi(m)}\equiv1 \pmod{m}\equiv n^{\phi(m)}+m^{\phi(n)}\equiv1+m^{\phi(n)} \pmod{m}$$.

But $$m^{\phi(n)} \equiv 0\pmod{m}$$ and $$n^{\phi(m)}\equiv 0\pmod{n}$$.

So we have $$m^{\phi(n)}+n^{\phi(m)}\equiv1\pmod{n}$$ and $$n^{\phi(m)}+m^{\phi(n)}\equiv1 \pmod{m}$$...

... which implies $$m^{\phi(n)}+n^{\phi(m)}\equiv1\pmod{mn}$$.

From $$m^{\phi(n)}+n^{\phi(m)}\equiv1 \pmod{n}\\ n^{\phi(m)}+m^{\phi(n)}\equiv1 \pmod{m}$$ we have $$A=m^{\phi(n)}+n^{\phi(m)}-1= n\cdot q_1\\ A=n^{\phi(m)}+m^{\phi(n)}-1=m\cdot q_2$$ Effectively, same number $$A$$ is divisible by $$m$$ and $$n$$, where $$\gcd(m,n)=1$$. Thus $$m\cdot n \mid A$$ or $$m^{\phi(n)}+n^{\phi(m)}-1= n\cdot m \cdot q_3 \Rightarrow m^{\phi(n)}+n^{\phi(m)} \equiv 1 \pmod{mn}$$
Proposition. If $$\gcd(m,n)=1$$, $$m \mid A$$ and $$n \mid A$$ then $$n\cdot m \mid A$$.
Indeed $$A=m\cdot q_1=\color{red}{n\cdot q_2} \tag{1}$$ and from Bezout's lemma $$\exists x,y\in\mathbb{Z}: x\cdot m+y\cdot n=\gcd(m,n)=1$$ Altogether $$x\cdot m\color{blue}{\cdot q_1}+y\cdot n\color{blue}{\cdot q_1}=\color{blue}{q_1} \overset{(1)}{\Rightarrow} \\ x\cdot \color{red}{n\cdot q_2}+y\cdot n\cdot q_1=q_1 \Rightarrow \\ n \mid q_1$$ or $$A=m\cdot q_1=m\cdot n\cdot q_3$$.