# Modular arithmetic problem: $7^x \equiv 1 \pmod{26}$

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.

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}$

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?

• So basically just trial and error... ! gotcha! – Lorenzo Battilocchi Mar 1 '17 at 23:28
• That's one way to do it. I suspect there are even better ways to do it, but this problem has small enough numbers that brute force works. – John Mar 1 '17 at 23:29

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