# Let $p$, $q$ be primes such that $q \equiv 2 \pmod{5}$ and $p = 4q+1$. Show that $100^{q} \not\equiv 1\pmod{p}$.

Let $p$, $q$ be two primes such that $q \equiv 2 \pmod{5}$ and $p = 4q+1$.

Show that $$100^{q} \not\equiv 1\pmod{p}$$

Here is one way that I tried to tackle this (and failed, obviously...):

Assume by contradiction that $100^{q} \equiv 1\pmod{p}$. By Fermat's little Theorem it follows that: $$100^{q} \equiv 100 \pmod{q}$$ This is where I got stuck. However, I did notice that:
$$p \equiv 1\pmod{q}$$ $$p \equiv -1\pmod{5}$$

But these congruences didn't help me either.

If we negate the conclusion, we have $$100^q\equiv 1 (\textrm{ mod }p),$$ and this is equivalent to the existence $x$ in the following $$100\equiv x^4 (\textrm{ mod }p)$$ This reduces to $10 \equiv x^2 (\textrm{ mod }p)$, or $-10 \equiv x^2 (\textrm{ mod }p)$
Both of them cannot be true since $$\left(\frac{10}{p}\right)=\left(\frac{-10}{p}\right) = -1.$$
• why $100\equiv x^4 (\textrm{ mod }p)$? – Lrrr May 31 '13 at 6:45