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.
I'd probably just start walking the dog up $x$:
$$7^2 = 49 \equiv 23 \equiv -3 \text { mod } 26$$ $$7^3 \equiv -3 \cdot 7 \equiv -21 \equiv 5 \text{ mod } 26$$
(See why this is?) Then just keep going until you win ...
$$7^4 \equiv 9 \text{ mod } 26$$ $$7^5 \equiv 11 \text{ mod } 26$$ $$7^6 \equiv 77 \equiv 25 \equiv -1 \text{ mod } 26$$
Hmmmmm! That's an interesting one. Can you take it from here?
Finding $x$ to give $7x\equiv 1 \bmod 26$ means that $x$ is the inverse of $7 \bmod 26$.
For small numbers like this you could just find the value by trial and error, but I usually straddle the modulus:
$7\times 3 =21 \equiv \color{blue}{-5} \bmod 26$ and $7\times 4 = 28\equiv \color{green}{2} \bmod 26$
then $\color{blue}{-5}+3\times \color{green}{2} = 1$
and $7\times (3+3\times 4) = 7\times 15 = 105 \equiv 1 \bmod 26$.
The second part is a matter of finding a cycle in the values of $7^k$ as $k$ increases, and then using that cycling to reduce the $100$ exponent to a less intimidating size. Euler's theorem is useful too.
Since $gcd(7,26)=1$, we have $$7^{12}\equiv 1\mod 26$$ because of $\phi(26)=12$. So, you can reduce the exponent modulo $12$ to calculate $7^{100}$ modulo $26$.
The smallest positive integer $m$ with $a^m\equiv 1\mod n$ is also called the order of $a$ modulo $n$. In this case, it is $12$.
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}$
