3
$\begingroup$

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?

$\endgroup$
4
  • $\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

5
$\begingroup$

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$}.

$\endgroup$
0
$\begingroup$

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):

$\endgroup$
7
  • $\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
  • 1
    $\begingroup$ I’d like to see your code $\endgroup$ Apr 18, 2019 at 16:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .