I have the following maths question, which I would like to solve in preparation for an exam:
"Find the smallest positive integer $x$ such that $7^x \equiv 1 \pmod{26}$. Calculate $7^{100} \bmod{26}$ (give your answer as a positive integer less than $26$)."
Any help would be much appreciated, even if it's just a little hint to the right approach to take, because I'm really stumped on this one.
Answer
As $26=2\cdot13$
we need $7^x\equiv1\pmod{13}$ and $7^x\equiv1\pmod2$
The second statement holds true for all integer $x$
So, the problem boils down to $7^x\equiv1\pmod{13}$
Now $x$ must divide $\phi(13)=12$
$7^2\equiv-3\pmod{13},7^3\equiv-21\equiv5,7^4\equiv(-3)^2\equiv-4,7^6\equiv5^2\equiv-1$
$\implies x\equiv0\pmod{12}$
No comments:
Post a Comment