Existence of Integers

• Mar 6th 2009, 09:00 AM
Chandru1
Existence of Integers
Suppose that $a,b$ are two integers with gcd(m, n) = 1. Prove that there exist integers $m, n$
such that $a^{m} + b^{n} \equiv 1 \: mod \: ab.$
• Mar 6th 2009, 09:34 AM
Opalg
You can split this into two easier problems: find m such that $a^m\equiv1\!\!\!\pmod b$, and find n such that $b^n\equiv1\!\!\!\pmod a$.
• Mar 6th 2009, 04:07 PM
Chandru1
Not getting
Hi--

I am not getting it. I can only think of the group Z/bZ ....(Wait)
• Mar 7th 2009, 03:50 AM
Opalg
Quote:

Originally Posted by Chandru1
Suppose that $a,b$ are two integers with gcd(m, n) = 1. When I saw the question before, I read this as gcd(a,b)=1. Presumably that what is meant?
Prove that there exist integers $m, n$
such that $a^{m} + b^{n} \equiv 1 \: mod \: ab.$

Quote:

Originally Posted by Chandru1
I am not getting it. I can only think of the group Z/bZ ....(Wait)

As an illustration, here's what happens when a=5 and b=7. The equation $5^m\equiv1\!\!\!\pmod7$ has the solution m=6, and the equation $7^n\equiv1\!\!\!\pmod5$ has the solution n=4. Then the number $5^6+7^4$ will be congruent to 1 (mod 5) and also (mod 7), and therefore also (mod 35).

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