# Periodic behavior for modulus of powers of two

I'm examining the behavior of the modulus of powers of 2 and I'm confused on how to prove that these observations are true.

1. Consider the sequence $$(a_n)_{n \in \mathbb{N}}$$ defined by the last two digits of powers of 2. Prove that $$a_n + a_{n+100} = 100$$ for every $$n \geq 2$$.

2. Prove that the sequence defined by the last three digits of the powers of 2 (starting with 008) is periodic with period 100.

Using Python, I've calculated these values and graphed them, and the behavior is clearly periodic. For example, for question (1), $$a_3 + a_{103} \neq 100$$, so I'm unsure if there's something broken here. And for (2), I can show through Python code that the function repeats, but I'm not sure how I would show this for all $$n \in \mathbb{N}$$, I'm assuming through induction.

• Part 1 was probably meant to be $$a_n + a_{n+10} = 100$$ for every $n \geq 2,$ which is true and follows from $2^{10} \equiv -1 \pmod{25}$ Oct 4 '19 at 2:49
• I'm pretty sure you can do the first one by induction (haven't tried to verify it though), and the second one is a simple period finding method. You assume a period $t$, and then try to prove that there exists a real value for $t$ such that $2^k \equiv 2^{k+t} \pmod{1000}$ holds for all $k$ Oct 4 '19 at 2:50
• Thought I was going crazy - @BrianMoehring that works out. And I will try it out right now, thanks for the help! Oct 4 '19 at 2:53

For part 2:

Hint: The question is essentially asking for the smallest positive integer $$n$$ such that $$2^n \equiv 1 \pmod {125}$$.

We know from corrected part 1 that $$2^ {10} \equiv -1 \pmod{25}$$. Now verify that this is the smallest $$n$$ for mod 25.

Hint: Hence conclude that $$2^{100} \equiv 1 \pmod{125}$$ is the smallest $$n$$.

So, the period is 100, starting from $$a_3$$.

For part 1, Brian's observation works directly.
Alternatively, you can easily modify the above.

(Sorry, my previous version thought you were still summing the last 3 digits in part 2)

For 2, the sequence must be periodic because there are only finitely many residues $$\bmod 1000$$. Once you hit one that you have hit before you have found the period. Once you get to $$2^3$$ all the powers $$\bmod 1000$$ must be multiples of $$8$$ so the cycle is no longer than $$125$$. In fact it is $$100$$ as you say because the powers also cannot have a multiple of $$5$$ in them, which leaves $$100$$ choices.

More generally, the powers of $$2 \bmod 10$$ repeat with a cycle of $$4-\ 2,4,8,6$$. The powers of $$2 \bmod 10^n$$ repeat with a cycle of $$4\cdot 5^{n-1}$$ because each of the $$n-1$$ digit numbers that has a factor of $$2^{n-1}$$ can be extended in $$5$$ ways to an $$n$$ digit one that has a factor of $$2^n$$.

This means $$1$$ is incorrect. The powers of $$2$$ cycle with period $$20$$, so after $$100$$ your are five times around. For example, $$2^5=32, 2^{105} \equiv 32 \pmod {100}$$, so their sum is $$64$$, not $$0$$

• Actually, the powers of 2 mod 100 cycle with period 20 $=\phi(25)$. Part 1 is incorrect with $a_{n+100}$, since $2^{100} \equiv 1 \pmod{25}$. Oct 4 '19 at 3:29
• @CalvinLin: you are correct and my second paragraph supports that. Fixed. Oct 4 '19 at 3:32