Find $7^{100} \pmod{167}$ using Fermat's Little Theorem

Question

I understand how to use Fermat's Little theorem but only on exponents that are larger than the mod, therefore, I do not know how to do this question please help, thank you!

Answer 1

Fermat's theorem tells us that $a^{p - 1} \equiv 1 \pmod p$, provided $p$ is an odd prime (or a Fermat pseudoprime to $a$) and $\gcd(a, p) = 1$. But you already knew that.

The bit crucial to your question that is hardly ever mentioned is that $$a^{\frac{p - 1}{2}} = \pm 1 \pmod p.$$ A little reflection upon the basic properties of exponentiation will show why it must be one of those two values.

But which one? I wish I had a clever answer to this part. It still helps you narrow it down to two possible answers.

If $7^{83} \equiv -1 \pmod{167}$, then $7^{100} = -(7^{17} \pmod{167})$. If instead $7^{83} \equiv 1 \pmod{167}$, then $7^{100} \equiv 7^{17} \pmod{167}$.

Computing $7^{17} \pmod{167}$ is more manageable: 7, 49, 9, 63, 107, 81, 66, 128, 61, 93, 150, 48, 2, 14, 98, 18, 126. So maybe $7^{100} \equiv 126 \pmod{167}$.

The other possible solution is $-126 \equiv 41 \pmod{167}$.

Answer 2

I'm not sure how you can use Fermat's little theorem. The standard method for computing powers is to write $100$ in base $2$: $100=\mathtt{1100100}_2$. Next (all congruences modulo $167$) \begin{align} 7^2&\equiv 49 \\ 7^4&\equiv 49^2\equiv 63 \\ 7^8&\equiv 63^2\equiv 128 \\ 7^{16}&\equiv 128^2\equiv 18 \\ 7^{32}&\equiv 18^2\equiv 157 \\ 7^{64}&\equiv 157^2\equiv 100 \end{align} and so $$ 7^{100}\equiv 7^{64}\cdot 7^{32}\cdot 7^4 \equiv 100\cdot 157\cdot 63\equiv 126 $$

One could note that $7^{100}\cdot 7^{66}\equiv 1$, and \begin{align} 167&=7\cdot23+6\\ 7&=6\cdot 1+1 \end{align} so $1=7-(167-7\cdot 23)=7\cdot24-167$. Thus $$ 7^{100}=24^{66} $$ But one still has to compute $24^{64}$.

Answer 3

Since $\phi(167) = 166 = 2\cdot 83$, the possible orders of $7$ mod $167$ are $2$, $83$ and $166$. Clearly, the order is not $2$. If we compute the Legendre symbol

$$\left(\frac{7}{167}\right) = - \left(\frac{167}{7}\right) = -\left(\frac{-1}{7}\right) = 1,$$

we see that $7$ is a quadratic residue mod $167$, and so the order can't be $166.$ (A primitive root can't be a quadratic residue.) Thus, the order of $7$ mod $167$ is $83.$ So we have

$$7^{100} \equiv 7^{17} \pmod{167}.$$

Next, notice that $7^3 = 343$ is pretty close to $2\cdot 167 = 334$, so we have $7^3 \equiv 9 \pmod{167}.$ Also, $2\cdot 9^2 = 162 \equiv -5 \pmod{167}$. Then we calculate:

$$7^{17} \equiv (7^3)^5\cdot 49 \equiv 9^2\cdot 9^2 \cdot 9 \cdot 49 \equiv (80\cdot 9^2 +1\cdot 9^2)\cdot 9 \cdot 49 \equiv (40(-5)+81)\cdot 9 \cdot 49 $$

$$\equiv (-119)\cdot 9 \cdot 49 \equiv -119\cdot 441 \equiv 48 \cdot (-60) \equiv -2880 \equiv 126 \pmod{167}.$$