# Prove that if $(a,b)=1$ then there exist some $m,n$ such that $a^m+b^n\equiv 1 ($mod $ab)$

Prove that if $$(a,b)=1$$ then there exist some $$m,n$$ such that $$a^m+b^n\equiv 1\pmod {ab}$$. Number $$a$$, $$b$$ are nature and positive number.

Since $$(a,b)=1$$ then there some number $$x$$, $$y\in \mathbb Z$$ such that $$ax+by=1$$. Since $$(a,b)=1$$ then I can use Fermath's theorem $$a^{b-1}\equiv 1 \pmod b$$, and $$b^{a-1}\equiv 1 \pmod a$$ so then $$a^b\equiv a \pmod {ab}$$ and $$b^a \equiv b \pmod {ab}$$. So $$a^b+b^a\equiv a+b \pmod {ab}$$. But I am not so sure that I going in right direction. Can you help me?

• raise both sides of $ax+by=1$ to the $ab$ power, or something like that – mathworker21 Nov 24 '18 at 5:08
• How do you mean, you say that I need to use $x+y|x^n+y^n$ or something else? – Marko Škorić Nov 24 '18 at 5:15
• no, just use binomial theorem to expand – mathworker21 Nov 24 '18 at 5:22
• @mathworker21 Hint: $\,\bmod ab\!:\ (a\!+\!b)^{\large n}\equiv a^{\large n} + b^{\large n}.\,$ See my answer for details. – Bill Dubuque Nov 24 '18 at 17:18
• @MarkoŠkorić We can do it directly without CRT - see my answer. – Bill Dubuque Nov 24 '18 at 17:20

By the Chinese remainder theorem, you need to find $$m$$, $$n\in\Bbb N$$ with $$a^m+b^n\equiv1\pmod a$$ and $$a^m+b^n\equiv1\pmod b$$. That is $$b^n\equiv1\pmod a$$ and $$a^m\equiv1\pmod b$$. By the Fermat-Euler theorem, you can take $$n=\varphi(a)$$ etc.
$$\overbrace{(a,b)=1\,\Rightarrow(\color{#c00}{ab},a\!+\!b)=1}^{\Large (\color{#c00}a,a+b)=(a,b)= (\color{#c00}b,a+b)},\$$ so $$\,\bmod \color{#c00}{ab}\!: \overbrace{\exists\, n\!:\ 1 \equiv (a\!+\!b)^{\large n}}^{\Large{\rm e.g.}\,\ n\ =\ {\rm ord}(a+b)}\!\equiv \underbrace{a^{\large n} + b^{\large n}+\overbrace{\color{#c00}{(ab)}(\cdots)}^{\large \equiv\ 0\ }}_{\large \rm Binomial\ Theorem}$$