I need to show that $10^k \equiv -100 \bmod 1010 \iff 4\,|\, k$ for all $n \in \mathbb{N} \setminus \{0\}$

elementary-number-theoryinductionsolution-verification

$$
10^k \equiv -100 \bmod1010
\;\iff\;
4\,|\, k \text{ for all } n \in \mathbb{N} \setminus \{0\}
$$

I know that I need to show both directions:
$$
10^k \equiv -100 \bmod 1010
\;\implies\;
4\,|\, k \text{ for all } n \in \mathbb{N} \setminus \{0\}
$$
and
$$
4\,|\, k \text{ for all } n \in \mathbb{N} \setminus \{0\}
\;\implies\;
10^k \equiv -100 \bmod 1010
$$

I also think that I have proven
$$
4\,|\,n \implies
10^k \equiv -100 \bmod1010
$$

via induction (I'll try my best in English):

We can write:
$$
10^{4k} \equiv -100 \bmod1010
$$

Base Case:
$$
10^{4 \cdot 1} \equiv 910 \bmod 1010
$$

true … so far so good.

Let's assume: $10^{4k} \equiv 910 \bmod 1010$

Induction step:
$$
10^{4(k+1)}
\equiv 10^{4 \cdot k} \cdot 10^4
\equiv 910 \cdot 10000
\equiv 910
\mod 1010
$$

Since that is the same rest as $-100 \bmod 1010$ it is proven …. right?

Now I need to show the other direction:

$10^k \equiv -100 \bmod 1010 \implies 4\,|\,k$

The thing is … I don't have any idea on how to show this. Could someone here maybe help me out a bit and push me in the right direction. Thanks so much for taking the time!

Best Answer

Fill in the gaps as needed. If you're stuck, state what you've tried.

Approach 1. Show by induction that

  • $10^{4k+1} \equiv 10 \pmod{1010}$
  • $10^{4k+2} \equiv 100 \pmod{1010}$
  • $10^{4k+3} \equiv -10 \pmod{1010}$
  • $10^{4k+4} \equiv -100 \pmod{1010}$
    Hence, the result follows.

Note: In my comment, I added 100 to the LHS. This presentation is easier to visually verify.

Approach 2. Apply Chinese remainder theorem. We want to find when

  • $10^{k} \equiv 0 \pmod{10}$ -> Show that this is true iff $k \geq 1$.
  • $10^k \equiv 1 \pmod{101}$ -> Show that this is true iff $4 \mid k$.
    Hence, the result follows.
Related Question