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

Question

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

Answer 1

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.

Answer 2

HINT.- It is equivalent to prove $$\frac{10(10^{k-2}+1)}{101}\in\mathbb N\iff 4|k$$

What I wanted to say is that the equivalent I have written has inmediate solution because $101$ is prime.