I was working on a problem for Project Euler and I made an assumption that led to me solving the problem. My assumption was that if we take mods of successive powers with a constant modulo, they will follow a pattern. For example: $$3^1\equiv 3 \mod 4$$ $$3^2\equiv 1 \mod 4$$ $$3^3\equiv 3 \mod 4$$ $$3^4\equiv 1 \mod 4$$ etc...
My question is, does a cyclic sequence of remainders appear for all consecutive powers of integers?
Well spotted. There are only so many different answers you can get, and once you get a repeat, the pattern repeats from then on. For example, the powers of $2\pmod5$ are $1,2,4,3,1,2,4,3,1,...$
If the two numbers have a common factor, there might be a first few numbers, before it repeats. For example, the powers of $15\pmod{100}$ are $1,15,25,75,25,75,25,...$ The first two numbers are different because they are the only ones that are not multiples of 25, as 100 is.
Yes this is always true . Here's a proof :
Let $a$ be the base of the power and $n$ the modulo . Also let $p_1,p_2,\ldots,p_k$ their common prime factors , $S=gcd(a,n)$ , $\frac{n}{S}=m$ and $$l=\max_{i} v_{p_i} (n)$$ (basically the largest of the exponents of theose primes in $n$ ).
It's easy to see that $a^{l} \equiv 0 \pmod{S}$ and so $a^y \equiv 0 \pmod{S}$ for every $y \geq l$
Because $S=gcd(a,n)$ it follows that $gcd(a,m)=1$
Now consider the powers $a,a^2,\ldots $ modulo $m$ .None of them is divisible with $m$ and they can have a finite number of possible residues .
So from pigeon-hole principle there are some $i$ and $j$ with $i>j$ such that :
$$a^i \equiv a^j \pmod{m}$$
$$a^{i-j} \equiv 1 \pmod{m}$$
This means that the powers are cyclic modulo $m$ with period at most $i-j$ .
But after some point (after $l$ steps ) all the number will be divisible with $S$ .
Now you can finnish the proof using chinese remainder theorem to combine the results modulo $S$ and $m$ (because $gcd(S,m)=1$ ).
So the sequence of powers will be periodic after those $l$ first powers .