1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ So basically just trial and error... ! gotcha! $\endgroup$ – Lorenzo Battilocchi Mar 1 '17 at 23:28
  • 1
    $\begingroup$ 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. $\endgroup$ – John Mar 1 '17 at 23:29
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.