$a^m + b^n \equiv 1 \mod ab$ for some $m,n$ If $a$ and $b$ are relatively prime integers, then there exist integers $m$ and $n$ such that $a^m + b^n \equiv 1 \mod ab$ .  How do I show this to be true?  (Artin's Algebra problem 11.1.16)
 A: Since $a$ and $b$ are coprime, the Chinese Remainder Theorem gives that $$\mathbb Z/ab\mathbb Z \simeq \mathbb Z/a\mathbb Z \times \mathbb Z/b\mathbb Z$$ via the homomorphism $[x]_{ab} \mapsto ([x]_a,[x]_b)$, were $[x]_k$ denotes the equivalence class of $x$ in $\mathbb Z/k \mathbb Z$.
Hence $$[a^m+b^n]_{ab}=[1]_{ab} \iff ([b^n]_a,[a^m]_b)=([1]_a,[1]_b).\,\,\,\, (*)$$
Since $\gcd(a,b)=1$, $[b]_a$ is a generator for $\mathbb Z/a\mathbb Z$; similarly, $[a]_b$ is a generator for $\mathbb Z/b\mathbb Z$. From this, we can choose $n$ and $m$ so that the right hand side of $(*)$ is satisfied.
This also shows that, to prove that $n=a-1$, $m=b-1$ are solutions, it suffices show that $a^{b-1}\equiv 1 \pmod{b}$ and $b^{a-1}\equiv 1 \pmod{a}$. This is true if $a$ and $b$ are primes, since the groups of units in $\mathbb Z/a \mathbb Z$ and $\mathbb Z/b \mathbb Z$ have orders $\phi(a)=a-1$ and $\phi(b)=b-1$, respectively (here, $\phi$ is Euler's totient function). But this need not hold if $a$ or $b$ is composite: take $a=6$, $b=5$. Then 
$$6^4+5^5=4421,$$ which is not congruent to $1 \pmod{30}$.
A: *

*My answer is 
$$a^{\phi(b)}+b^{\phi(a)}\equiv1\mod ab$$

*Because
$$a^m+b^n\equiv1\mod ab$$
$$\Longleftrightarrow a^m+b^n\equiv1\mod a \text{ and } a^m+b^n\equiv1\mod b$$
$$\Longleftrightarrow b^n\equiv1\mod a \text{ and } a^m\equiv1\mod b \text{ ,}$$
then from Euler's theorem, we just need $n=\phi(a)$ and $m=\phi(b)$.


*

*When is your assumption right? Firstly, we denote $\sigma_m(x)=\min\{d:x^d\equiv1\mod m\}$. Then get the conclusion that your assumption is right if and only if $\sigma_a(b)|a-1$ and $\sigma_b(a)|b-1$.

A: Hint. 
Set $m=\phi(b), n=\phi(a)$ and use Eulers theorem. 
A: Since $a$ and $b$ are coprime, there exist $m,n > 0$ such that
$$a^m \equiv 1 \pmod b \quad \text{and} \quad b^n \equiv 1 \pmod a$$
Now we have
$$\begin{cases} a^m + b^n \equiv 0 + 1 \equiv 1 \pmod a \\ a^m + b^n \equiv 1 + 0 \equiv 1 \pmod b \end{cases}$$
so you can apply the Chinese remainder theorem to get
$$a^m + b^n \equiv 1 \pmod{ab}$$
as required.
