5
$\begingroup$

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)

$\endgroup$
3
$\begingroup$
  • 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$.
$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.