Smallest positive integer modular congruence problem

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.