Find all primes that satisfy congruency $100^p\equiv1\mod p$

I've tried reducing it to the fact that $100^p=(10^p)^2$ so then $10^p \equiv 1 \mod p$ or $-1 \mod p$.

I've also attempted writing this as $100^p-np=1$, so that leads me to $\gcd(100^p,n)=1$ but I don't see where to go from here.

Would appreciate some help with this! I only know a little bit about number theory so preferably an answer using more basic stuff (Like Fermat's little theorem, linear diophantine equations, gcd's)

Edit after reading comments: Following from Fermat's little theorem, since we know $100^p\equiv100\mod p$ for all prime p, but $100^p\equiv1\mod p$ only if $100-np=1$ so $np=99$ so $p=11,3$ are the only solutions? Is this correct?

  • $\begingroup$ Welcome to Math Stack Exchange. If $p$ is prime, then by Fermat's little theorem $100^p\equiv100\pmod p$, right? $\endgroup$ Apr 18, 2019 at 2:11
  • 1
    $\begingroup$ I think 3 and 11 satisfy this... $\endgroup$ Apr 18, 2019 at 2:11
  • $\begingroup$ Fermat's Little Theorem - got it in one. How do you simplify $100^p$ modulo $p$ by using this theorem? Does it work for all $p$? $\endgroup$
    – David
    Apr 18, 2019 at 2:11
  • $\begingroup$ red herring: $100^{21}\equiv1\pmod {21}$, but $21$ isn't prime $\endgroup$ Apr 18, 2019 at 2:22

2 Answers 2


You are correct that $3$ and $11$ are the only solutions.

If $p$ is prime then $100^p\equiv 100\pmod p$ by Fermat's little theorem. So $100^p\equiv1\pmod p$ would mean $100\equiv1\pmod p$, i.e., $p$ divides $100-1=99$. The prime factorization of $99$ is $3^2\times11$; i.e., the prime factors of $99$ are $3$ and $11$. So if $100^p\equiv1\pmod p$ then $p\in${$3,11$}.


By Fermat's little theorem, $100^p \equiv 100 \mod p$. So, one must determine the solutions of $p$ for $100 \equiv 1 \mod p$. First, $p$ can't divide $100$ and must be less than it, so that eliminates $5$ and $2$ and all primes over $100$.

From there you can just check all primes less than $100$. The only two that satisfy this are $3$ and $11$.

Here's the code (Wolfram):

  • $\begingroup$ Your reasoning is not faulty, but my reasoning ($p$ divides $99$) avoids a lot of checking $\endgroup$ Apr 18, 2019 at 2:26
  • $\begingroup$ I just wrote a quick code segment. It's late so a bit of laziness kicks in... @J.W.Tanner $\endgroup$ Apr 18, 2019 at 2:27
  • $\begingroup$ what code language did you use? $\endgroup$ Apr 18, 2019 at 2:28
  • $\begingroup$ @J.W.Tanner I had a wolfram tab open so I used that. I just set up a while loop and had it run for like .2 seconds $\endgroup$ Apr 18, 2019 at 2:30
  • $\begingroup$ I’d like to see your code $\endgroup$ Apr 18, 2019 at 16:20

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.