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
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
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
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.
(Assuming $\displaystyle a$ is such that $\displaystyle \gcd(a,1001)=1$).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)$.
(What does oO mean?)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 ).
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
This implication seems odd to me. I don't see with which theorem/property we can say it (although i agree with the result )Thus.
$\displaystyle a^{60}\equiv 1(\bmod 1001)$.
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