I'm stuck with the following question

Show that for each positive integer b, $\displaystyle b^{61} \equiv b (mod \, 1001)$

Thank you for your help

Printable View

- Mar 29th 2008, 09:44 PMkleenexcongruences
I'm stuck with the following question

Show that for each positive integer b, $\displaystyle b^{61} \equiv b (mod \, 1001)$

Thank you for your help - Mar 30th 2008, 12:58 AMMoo
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 - Mar 30th 2008, 02:45 AMkleenex
- Mar 30th 2008, 02:49 AMMoo
Nope, it won't work :s

Because $\displaystyle \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) - Mar 30th 2008, 05:32 AMPaulRS
Well $\displaystyle 1001=7\cdot{11}\cdot{13}$

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

You can easily see that

$\displaystyle a^{\theta}\equiv{1}(\bmod.7)$

$\displaystyle a^{\theta}\equiv{1}(\bmod.11)$

$\displaystyle a^{\theta}\equiv{1}(\bmod.13)$

whenever a is coprime to 1001

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

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

THus: $\displaystyle a^{60}\equiv{1}(\bmod{1001})$ if a is coprime to 1001 - Mar 30th 2008, 06:01 AMMoo
This is the problem... You have to show it for any integer, not coprime oO

- Mar 30th 2008, 08:12 AMThePerfectHacker
No, you do not need CRT, look at what PaulRS did. If you have $\displaystyle x\equiv a(\bmod n_1)$, $\displaystyle x\equiv a(\bmod n_2)$, .... , $\displaystyle x\equiv a_k(\bmod n_k)$ so that $\displaystyle \gcd(n_i,n_j)=1$ whenever $\displaystyle i\not = j$ then $\displaystyle x\equiv a(\bmod n)$ where $\displaystyle n=n_1\cdot ... \cdot n_k$. This is not CRT, just property of relative primeness. CRT only enters when the $\displaystyle a$'s are different for each modolus.

- Mar 30th 2008, 08:44 AMMoo
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 ! - Mar 30th 2008, 09:01 AMThePerfectHackerQuote:

Originally Posted by**Moo**

Because,

$\displaystyle a^6 \equiv 1(\bmod 7)$

$\displaystyle a^{10}\equiv 1(\bmod 11)$

$\displaystyle a^{12}\equiv 1(\bmod 13)$.

Then,

$\displaystyle (a^6)^{10}\equiv 1^{10}(\bmod 7)$

$\displaystyle (a^{10})^6\equiv 1^6(\bmod 11)$

$\displaystyle (a^{12})^5\equiv 1^5(\bmod 13)$.

Thus.

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

Quote:

Originally Posted by**Moo**

But it will not work for any integer. Say $\displaystyle a=7$ then $\displaystyle 7^{60}\not \equiv 7(\bmod 1001)$ (I just did it on my calculator (Tongueout) ). - Mar 30th 2008, 09:18 AMMoo
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.

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

- Mar 30th 2008, 10:01 AMThePerfectHacker
- Mar 30th 2008, 10:05 AMMoo
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 - Mar 30th 2008, 10:07 AMThePerfectHacker
Let $\displaystyle \gcd(p,q)=1$ for $\displaystyle p,q\in \mathbb{Z}^+$.

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

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

oO - Mar 30th 2008, 10:11 AMMoo
Ok, now it's all clear ! :D

Oo oO O.o o.O