congruences

Printable View

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)$

Thank you for your help
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