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