Find $7^{100} \pmod{167}$ using Fermat's Little Theorem 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!
 A: 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}$.
A: 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}$.
A: 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}.$$
