1
$\begingroup$

I need help with the following problem:

Find the smallest positive integer $n$ such that

$$x^n \equiv 1 \pmod{101}$$ for every integer $x$ between $2$ and $40$.

How can I approach this? Using Euclid's? Fermat's?

I know Fermat's says if $p$ is a prime, then $x^{p−1} \equiv 1 (\mod p) $but I don't know how or if I can apply it. As you can probably tell I'm very confused by modular congruences

|cite|improve this question
$\endgroup$
  • $\begingroup$ Do you know primitive roots? $\endgroup$ – Saad Mar 20 '18 at 23:33
  • $\begingroup$ @AlexFrancisco No I do not. $\endgroup$ – Hopper Mar 20 '18 at 23:49
1
$\begingroup$

$101$ is prime. $2^{100} \equiv 1 \mod 101$. Is there any smaller $n$ that works for $x=2$? Note that all the $n$ you really need to try here are $20$ and $50$.

EDIT: This can also be done without much computation. There are $\varphi(100) = 40$ primitive roots mod $101$. Note that since $101 \equiv 1 \mod 4$, $-x$ is a primitive root mod $101$ if and only if $x$ is. Thus if there were no primitive roots from $1$ to $40$, there would also be none from $61$ to $100$. But there are only $20$ integers from $41$ to $60$, so there isn't room for all the primitive roots there.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Your answer is correct, of course, but it does suggest that the problem posed in the question is sort of silly. Why mention $40$ at all? It'd be much more interesting if $101$ had a large least primitive root, larger than $40$, though this is very unlikely for such a small prime. $\endgroup$ – lhf Mar 21 '18 at 0:15
  • $\begingroup$ @robertisrael I understood the problem as I need to find the smallest positive integer for each individual number x from 2-40. $\endgroup$ – Hopper Mar 21 '18 at 0:49
  • $\begingroup$ (continued) In this sense, the interesting primes are $3,7,23,191,409$, whose least primitive root is greater than $\sqrt p$, see oeis.org/A262264. $\endgroup$ – lhf Mar 21 '18 at 13:59
0
$\begingroup$

The multiplicative group $(\mathbf Z/101\mathbf Z)^{\times}$ is cyclic, so we must find a generator? It happens $2$ is such a generator, since its order is a divisor of $100$ and $$2^{50}=-1;\quad2^{25}=10,\quad 2^{20}=-6,\quad 2^{10}=14\mod 101,$$ so the smallest positive exponent is $n=100$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ How does this apply if the x value is 3 or 7? Or any number up to 40 besides 2? Would the smallest positive n value still be 100? $\endgroup$ – Hopper Mar 21 '18 at 1:05
  • $\begingroup$ If the list of numbers contains a generator of the group (called a primitive element), yes, it would be $100$. The difficulty consist in determining the orders of the elements in the list. All is a priori known is that it's a divisor of the order of the group. $\endgroup$ – Bernard Mar 21 '18 at 9:29
0
$\begingroup$

If you need to find one $n$ that works for all the integers from $2$ to $40$ then Fermat/Euler says first that $x^{100} \equiv 1 \pmod{101}$. So $n$ is at most $100$. Then you just need to find one number for which no smaller number works, and as others have shown, $2^n \not\equiv 1 \pmod{101}$ for any $n$ between $1$ and $100$, so the answer is $n= 100.$

If you have to find a different $n$ for each integer, then your work is cut out for you. The problem asks for the "order" of each integer. The lemmas and corollaries around the Fermat/Euler theorems say that the order of an integer divides $\phi(101) = 100$. The divisors of $100$ are $1, 2, 4, 5, 10, 20, 25, 50,$ and $100$. So your $n$ has to be one of these.

For instance, for $x=10$, we have $10^2 = 100 \equiv -1 \pmod{101}$ and so $10^4 \equiv (-1)^2 \equiv 1 \pmod{101}$. Since $2$ doesn't work and $4$ does, $n=4$.

But for $x=16$, you'll have to compute $16^n$ for $n=2, 4, 5, 10, 20,$ and $25$ to discover that $n=25$ for this case.

You may need more than one calculator.

|cite|improve this answer
$\endgroup$

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.