2
$\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$ – J. W. Tanner Apr 18 '19 at 2:11
  • 1
    $\begingroup$ I think 3 and 11 satisfy this... $\endgroup$ – Ryan Shesler Apr 18 '19 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 '19 at 2:11
  • $\begingroup$ red herring: $100^{21}\equiv1\pmod {21}$, but $21$ isn't prime $\endgroup$ – J. W. Tanner Apr 18 '19 at 2:22
4
$\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$ – J. W. Tanner Apr 18 '19 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$ – Ryan Shesler Apr 18 '19 at 2:27
  • $\begingroup$ what code language did you use? $\endgroup$ – J. W. Tanner Apr 18 '19 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$ – Ryan Shesler Apr 18 '19 at 2:30
  • $\begingroup$ I’d like to see your code $\endgroup$ – J. W. Tanner Apr 18 '19 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.