2
$\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

$\endgroup$
2
  • $\begingroup$ Do you know primitive roots? $\endgroup$
    – Ѕааԁ
    Mar 20, 2018 at 23:33
  • $\begingroup$ @AlexFrancisco No I do not. $\endgroup$
    – Hopper
    Mar 20, 2018 at 23:49

3 Answers 3

Reset to default
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.

$\endgroup$
3
  • $\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, 2018 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, 2018 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, 2018 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$.

$\endgroup$
2
  • $\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, 2018 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, 2018 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.

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