$a^m + b^n \equiv 1 \mod ab$ for some $m,n$

Question

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)

Answer 1

• 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$.

Answer 2

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}$.

Answer 3

Hint. Set $m=\phi(b), n=\phi(a)$ and use Eulers theorem.

Answer 4

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.