# Checking whether $10^{499} \equiv 1$ modulo $1997$

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.

• If you can't find an ingenious way to do it, repeated squaring is decently fast, even by hand. – Arthur May 6 at 18:18
• Do you know about repeated squaring? – saulspatz May 6 at 18:18
• 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. – Jyrki Lahtonen May 6 at 18:20
• 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$. – J.G. May 6 at 18:35
• @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] – Mark Bennet May 6 at 20:36

## 2 Answers

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

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