# congruences

• March 29th 2008, 09:44 PM
kleenex
congruences
I'm stuck with the following question
Show that for each positive integer b, $b^{61} \equiv b (mod \, 1001)$

• March 30th 2008, 12:58 AM
Moo
Hello,

You can take a look at the Chinese remainder theorem , as far as i see your problem, this is the only way i've found to get only elements of solution...

If you were asked to show that it had a congruence with 1 mod 1001, i would have given you Euler's theorem
• March 30th 2008, 02:45 AM
kleenex
Quote:

Originally Posted by Moo
, i would have given you Euler's theorem

Oh yes, use Euler's Theorem for 2 times, thank you Moo
• March 30th 2008, 02:49 AM
Moo
Nope, it won't work :s

Because $\varphi(1001)=6*10*12$, which is not 61 o.O

Perhaps you can see what to do, if so that's good for you (Rofl)
• March 30th 2008, 05:32 AM
PaulRS
Well $1001=7\cdot{11}\cdot{13}$

Let $\theta=\text{lcm}\left(\phi(7),\phi(11),\phi(13)\r ight)$

You can easily see that
$a^{\theta}\equiv{1}(\bmod.7)$
$a^{\theta}\equiv{1}(\bmod.11)$
$a^{\theta}\equiv{1}(\bmod.13)$

whenever a is coprime to 1001

THen it follows (it is easy to prove) that $a^{\theta}\equiv{1}(\bmod{1001})$

But: $\theta=\text{lcm}\left(6,10,12\right)=60$

THus: $a^{60}\equiv{1}(\bmod{1001})$ if a is coprime to 1001
• March 30th 2008, 06:01 AM
Moo
This is the problem... You have to show it for any integer, not coprime oO
• March 30th 2008, 08:12 AM
ThePerfectHacker
Quote:

Originally Posted by Moo
You can take a look at the Chinese remainder theorem , as far as i see your problem, this is the only way

No, you do not need CRT, look at what PaulRS did. If you have $x\equiv a(\bmod n_1)$, $x\equiv a(\bmod n_2)$, .... , $x\equiv a_k(\bmod n_k)$ so that $\gcd(n_i,n_j)=1$ whenever $i\not = j$ then $x\equiv a(\bmod n)$ where $n=n_1\cdot ... \cdot n_k$. This is not CRT, just property of relative primeness. CRT only enters when the $a$'s are different for each modolus.
• March 30th 2008, 08:44 AM
Moo
Oh, i didn't know this thing :-) d'you have a wiki link ?

Why that :
Quote:

THus: a^{60}\equiv{1}(\bmod{1001}) if a is coprime to 1001
?

Thanks !
• March 30th 2008, 09:01 AM
ThePerfectHacker
Quote:

Originally Posted by Moo
Oh, i didn't know this thing :-) d'you have a wiki link ?

Why that :
Quote:

Originally Posted by Paul
THus: a^{60}\equiv{1}(\bmod{1001}) if a is coprime to 1001

?

Thanks !

(Assuming $a$ is such that $\gcd(a,1001)=1$).

Because,
$a^6 \equiv 1(\bmod 7)$
$a^{10}\equiv 1(\bmod 11)$
$a^{12}\equiv 1(\bmod 13)$.

Then,
$(a^6)^{10}\equiv 1^{10}(\bmod 7)$
$(a^{10})^6\equiv 1^6(\bmod 11)$
$(a^{12})^5\equiv 1^5(\bmod 13)$.

Thus.
$a^{60}\equiv 1(\bmod 1001)$.

Quote:

Originally Posted by Moo
This is the problem... You have to show it for any integer, not coprime oO

(What does oO mean?)

But it will not work for any integer. Say $a=7$ then $7^{60}\not \equiv 7(\bmod 1001)$ (I just did it on my calculator (Tongueout) ).
• March 30th 2008, 09:18 AM
Moo
oO is a smiley :D

That's the problem, the initial text said that it was for any integer... I couldn't verify with my calculator, thanks

Quote:

Thus.
$a^{60}\equiv 1(\bmod 1001)$.
This implication seems odd to me. I don't see with which theorem/property we can say it (although i agree with the result :p)
• March 30th 2008, 10:01 AM
ThePerfectHacker
Quote:

Originally Posted by Moo
This implication seems odd to me. I don't see with which theorem/property we can say it (although i agree with the result :p)

What is so strange? I showed you exactly what happens.
• March 30th 2008, 10:05 AM
Moo
Well,

If p & q are coprime, and x = 1 mod p and 1 mod q, why should x be = 1 mod pq ?

aaah i see, perhaps Bézout's identity could help... need to see it later
• March 30th 2008, 10:07 AM
ThePerfectHacker
Quote:

Originally Posted by Moo
Well,

If p & q are coprime, and x = 1 mod p and 1 mod q, why should x be = 1 mod pq ?

aaah i see, perhaps Bézout's identity could help... need to see it later

Let $\gcd(p,q)=1$ for $p,q\in \mathbb{Z}^+$.

If $p|a$ and $q|a$ then $pq|a$.

Thus if $x\equiv 1(\bmod p)$ and $x\equiv 1(\bmod q)$ it means $p|(x-1)$ and $q|(x-1)$ so $pq|(x-1)$ thus $x\equiv 1(\bmod pq)$.

oO
• March 30th 2008, 10:11 AM
Moo
Ok, now it's all clear ! :D

Oo oO O.o o.O