3
$\begingroup$

I need to find the smallest number $x$ such that $10^x\equiv 1 \pmod{1997}$,

By Euler function we know $\phi(1997)=1996=4\times499$, so $x$ must be a divisor of $1996$, so I have to check whether $10^{499}\equiv 1 \pmod{1997}$, but I do not find a nice way to calculate it.

$\endgroup$
9
  • 4
    $\begingroup$ If you can't find an ingenious way to do it, repeated squaring is decently fast, even by hand. $\endgroup$ – Arthur May 6 at 18:18
  • 1
    $\begingroup$ Do you know about repeated squaring? $\endgroup$ – saulspatz May 6 at 18:18
  • $\begingroup$ Quadratic reciprocity tells that neither $2$ nor $5$ is a QR, so $10$ is. Therefore the answer will be $\pm1$, but we need a bit more to decide. $\endgroup$ – Jyrki Lahtonen May 6 at 18:20
  • 1
    $\begingroup$ While computing e.g. $225^2$ modulo $1997$ without a calculator is tedious, I agree with several commenters that repeated squaring or something similar is likely vital. I've checked in Python that $10^{499}=-1$, so $x=998$. $\endgroup$ – J.G. May 6 at 18:35
  • 1
    $\begingroup$ @JyrkiLahtonen In fact if I can find a square root of $10$ in some efficient way, I can check whether that square root is a quadratic residue. [I get $783=27 \cdot 29$ by inefficient methods] $\endgroup$ – Mark Bennet May 6 at 20:36
3
$\begingroup$

You want to find the order of $10\bmod 1997$ with pen and paper.

You begin by factoring $1997$ and realize it is a prime by checking it is not divisible by any prime under $\sqrt{1997} < 50$ ( so you only check $2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47$), which is a bit of work, but not too much.

We now know the multiplicative group $\bmod 1997$ is isomorphic to $\mathbb Z_{1996}$.

We factor $1996$ and get $1996 = 2^2 \cdot 499$, in order to find that $499$ is prime we only need to check it is not divisible by $2,3,5,7,11,13,17,19,23$.

In order to find what the order of $10\bmod 1997$ is we can find $v_2$ and $v_{499}$ of the order.

In order to find $v_{499}$ of the order we must check if $10^{1996/499} \equiv 1 \bmod 1997$. This part is easy because $10^4 = 10000$ is not $1\bmod 1997$. It follows $v_{499}$ of the order is $1$.

In order to find $v_2$ of the order we must check if $10^{1996/4}\equiv 1$ and if $10^{1996/2}\equiv 1 \bmod 1997$. First we check if $10^{499} \equiv 1 \bmod 1997$.

We use exponentiation by squaring. First we write $499$ in binary, it is $111110011$. Next we obtain the first $9$ residues for $10^{2^k}$ starting with $k=0$.

$10,100,15,225,700,735,1035,833,930$.

It follows $2^{449} \equiv 930 \cdot 833 \cdot 1035 \cdot 735 \cdot 700 \cdot 100 \cdot 10 \bmod 1997$.

This number turns out to be $1996\bmod 1997$.

Now in order to check $10^{1996/2}$ we just need to square the previous number, which happens to be $1$. It follows $v_2$ of the order is $1$.

Hence the order is $998$.

If $1997-1$ was of the form $p_1^{a_1}\dots p_k^{a_k}$ it might have been convenient to first calculate all of the $10^{p_i^{a_i}}$ and use these to calculate the values $10^{(1996)/p_i^{a_i}}$.

$\endgroup$
1
$\begingroup$

Just a set a reusable and simple calculations $$10^3\equiv -997\pmod{1997}$$ $$10^4\equiv -9970\equiv 15\pmod{1997}$$ $$10^7\equiv -997\cdot15\equiv 1021\pmod{1997}$$ $$10^{14}\equiv 1021^2 \equiv 7\pmod{1997}$$ $$10^{42}\equiv 7^3 \equiv 343\pmod{1997}$$ $$10^{46}\equiv 343\cdot 15\equiv 1151\pmod{1997}$$ $$10^{49}\equiv 1151 \cdot (-997) \equiv 728\pmod{1997}$$ $$10^{490}\equiv 728^{10}\equiv 779^{5} \equiv 1750\cdot 1750\cdot779 \equiv 1099\cdot 779 \equiv 1405 \pmod{1997}$$ $$10^{498}\equiv 1405\cdot (15)^2 \equiv 599\pmod{1997}$$ $$10^{499}\equiv 5990 \equiv -1\pmod{1997}\tag{1}$$


It is worth noting that $$ord_n(a) \mid \varphi(n)$$ So $$ord_{1997}(10) \mid \varphi(1997)=2^2\cdot 449$$ considering $(1)$ and checking various combinations of $2,2,449$ we conclude that $x=ord_{1997}(10)=2\cdot 499$ $$10^{2\cdot499} \equiv (-1)^2\equiv 1\pmod{1997}$$

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