# Find all primes that satisfy the congruency $100^p \equiv 1 \mod p$

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?

• Welcome to Math Stack Exchange. If $p$ is prime, then by Fermat's little theorem $100^p\equiv100\pmod p$, right? – J. W. Tanner Apr 18 '19 at 2:11
• I think 3 and 11 satisfy this... – Ryan Shesler Apr 18 '19 at 2:11
• 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$? – David Apr 18 '19 at 2:11
• red herring: $100^{21}\equiv1\pmod {21}$, but $21$ isn't prime – J. W. Tanner Apr 18 '19 at 2:22

## 2 Answers

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): • Your reasoning is not faulty, but my reasoning ($p$ divides $99$) avoids a lot of checking – J. W. Tanner Apr 18 '19 at 2:26
• I just wrote a quick code segment. It's late so a bit of laziness kicks in... @J.W.Tanner – Ryan Shesler Apr 18 '19 at 2:27
• what code language did you use? – J. W. Tanner Apr 18 '19 at 2:28
• @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 – Ryan Shesler Apr 18 '19 at 2:30
• I’d like to see your code – J. W. Tanner Apr 18 '19 at 16:20