Suppose that $\displaystyle a,b$ are two integers with gcd(m, n) = 1. Prove that there exist integers $\displaystyle m, n$

such that $\displaystyle a^{m} + b^{n} \equiv 1 \: mod \: ab.$

Printable View

- Mar 6th 2009, 08:00 AMChandru1Existence of Integers
Suppose that $\displaystyle a,b$ are two integers with gcd(m, n) = 1. Prove that there exist integers $\displaystyle m, n$

such that $\displaystyle a^{m} + b^{n} \equiv 1 \: mod \: ab.$ - Mar 6th 2009, 08:34 AMOpalg
You can split this into two easier problems: find m such that $\displaystyle a^m\equiv1\!\!\!\pmod b$, and find n such that $\displaystyle b^n\equiv1\!\!\!\pmod a$.

- Mar 6th 2009, 03:07 PMChandru1Not getting
Hi--

I am not getting it. I can only think of the group Z/bZ ....(Wait) - Mar 7th 2009, 02:50 AMOpalg
As an illustration, here's what happens when a=5 and b=7. The equation $\displaystyle 5^m\equiv1\!\!\!\pmod7$ has the solution m=6, and the equation $\displaystyle 7^n\equiv1\!\!\!\pmod5$ has the solution n=4. Then the number $\displaystyle 5^6+7^4$ will be congruent to 1 (mod 5) and also (mod 7), and therefore also (mod 35).

[Check: $\displaystyle 5^6+7^4 = 18026 = 515\times35+1$.]