0
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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}$ $\endgroup$ Oct 4 '19 at 2:49
  • 1
    $\begingroup$ 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$ $\endgroup$
    – Hiten
    Oct 4 '19 at 2:50
  • $\begingroup$ Thought I was going crazy - @BrianMoehring that works out. And I will try it out right now, thanks for the help! $\endgroup$
    – beflyguy
    Oct 4 '19 at 2:53
2
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ 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}$. $\endgroup$
    – Calvin Lin
    Oct 4 '19 at 3:29
  • $\begingroup$ @CalvinLin: you are correct and my second paragraph supports that. Fixed. $\endgroup$ Oct 4 '19 at 3:32

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.