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?

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


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.