# Smallest positive integer modular congruence problem

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

• Do you know primitive roots? – Saad Mar 20 '18 at 23:33
• @AlexFrancisco No I do not. – Hopper Mar 20 '18 at 23:49

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

• 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. – lhf Mar 21 '18 at 0:15
• @robertisrael I understood the problem as I need to find the smallest positive integer for each individual number x from 2-40. – Hopper Mar 21 '18 at 0:49
• (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. – lhf Mar 21 '18 at 13:59

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

• 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? – Hopper Mar 21 '18 at 1:05
• 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. – Bernard Mar 21 '18 at 9:29

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.