congruences

**kleenex** · March 29th 2008, 09:44 PM

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

**Moo** · March 30th 2008, 12:58 AM

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

**kleenex** · March 30th 2008, 02:45 AM

Originally Posted by Moo

, i would have given you Euler's theorem

Oh yes, use Euler's Theorem for 2 times, thank you Moo

**Moo** · March 30th 2008, 02:49 AM

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

**PaulRS** · March 30th 2008, 05:32 AM

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

**Moo** · March 30th 2008, 06:01 AM

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

**ThePerfectHacker** · March 30th 2008, 08:12 AM

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.

**Moo** · March 30th 2008, 08:44 AM

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

Why that :

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

?

Thanks !

**ThePerfectHacker** · March 30th 2008, 09:01 AM

Originally Posted by Moo

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

Why that :

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

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

).

**Moo** · March 30th 2008, 09:18 AM

oO is a smiley

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

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

)

**ThePerfectHacker** · March 30th 2008, 10:01 AM

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

)

What is so strange? I showed you exactly what happens.

**Moo** · March 30th 2008, 10:05 AM

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

**ThePerfectHacker** · March 30th 2008, 10:07 AM

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

**Moo** · March 30th 2008, 10:11 AM

Ok, now it's all clear !

Oo oO O.o o.O

Thread: congruences

LinkBack

Thread Tools

Display

congruences

Similar Math Help Forum Discussions

Congruences

Congruences

Congruences

More congruences

Congruences

Search Tags