# Thread: congruences

1. ## 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

2. 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

3. Originally Posted by Moo
, i would have given you Euler's theorem
Oh yes, use Euler's Theorem for 2 times, thank you Moo

4. 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

5. 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

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

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

8. 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 !

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

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

11. 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.

12. 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

13. 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

14. Ok, now it's all clear !

Oo oO O.o o.O