Observation on digit in base $2$ for $3^n$

Question

Below table shows, representation in base $2$ for $3^n$

$$ 3^{00}=000000000000000000001\\3^{01}=000000000000000000011\\3^{02}=000000000000000001001\\3^{03}=000000000000000011011\\3^{04}=000000000000001010001\\3^{05}=000000000000011110011\\3^{06}=000000000001011011001\\3^{07}=000000000100010001011\\3^{08}=000000001100110100001\\3^{09}=000000100110011100011\\3^{10}=000001110011010101001\\3^{11}=000101011001111111011\\3^{12}=010000001101111110001\\3^{13}=110000101001111010011$$

Observation on column from right side

First column shows only $\{1\}$ in repeated pattern, May we call 'prefect symmetry'

Second column shows $\{0,1\}$ in repeated pattern

Third column shows $\{0\}$ in repeated pattern

Fourth column shows $\{0,0,1,1\}$ in repeated pattern

But from fifth column don't show repeated pattern

Question

How to show, 5th column and greater than 5th column don't have repeated pattern?

Answer 1

All the columns have a repeated pattern.

• For the fifth column from the right, the repeating pattern is "$0,0,0,1,1,1,1,0$".
• For the sixth column from the right, the repeating pattern is "$0,0,0,0,0,1,0,0,1,1,1,1,1,0,1,1$".
• For the seventh column from the right, the repeating pattern is "$0,0,0,0,1,1,1,0,0,1,0,1,1,1,1,1,1,1,1,1,0,0,0,1,1,0,1,0,0,0,0,0$".

We can prove that every column is periodic. We do this by showing that the last $m$ columns are jointly periodic for every $m \geq 1$. It should be clear that if each of the last $m$ columns is periodic with periods $p_1, p_2, \dots, p_m$, that they are jointly periodic with period $\mathrm{lcm}(p_1,p_2, \dots,p_m)$, where $\mathrm{lcm}$ is the least common multiple. Also, if the last $m$ columns are jointly periodic, each column is periodic (with period dividing the joint period).

The last $m$ columns are the least nonnegative member of the congruence class $3^n$ modulo $2^m$. There are only $2^m$ such congruence classes. Consequently, there are only $2^m$ possible different values in the last $m$ columns and so after $2^m+1$ powers of $3$ there is at least one repetition in the last $m$ columns. If a value in the last $m$ columns is ever repeated, say $3^a$ and $3^b$ have the same last $m$ columns, then the sequence of values between $3^a$ and $3^b$ repeats forever because $3^a\cdot 3$ has the same last $m$ columns as $3^b \cdot 3$, and so on.

This argument allows an initial portion of the powers of $3$ to not be repeated, followed by a forever repeating part. We now show that the initial, not repeated portion is empty. Note that $3$ and $2^m$ share no prime factors. This means $\gcd(3,2^m) = 1$. By the extended Euclidean algorithm, we can find integers $u$ and $v$ such that $3 u + 2^m v = 1$. This also says $3u$ is congruent to $1 = 3^0$ modulo $2^m$. Suppose $3^a$ and $3^b$, $0 < a < b$ are the first pair of powers of $3$ that repeat modulo $2^m$. Then $3^{a-1} = 3^a \cdot u$ modulo $2^m$ is congruent to $3^{b-1} = 3^b \cdot u$ modulo $2^m$ (by contradiction, we're done, but the constructive version is nearly done also...) and we can walk both of these back to $3^0$ congruent to $3^{b-a}$. Thus, $3^0$ is the first member of the first period.

Answer 2

Contrary to your belief, all columns have a repeated pattern. The period can be longer, this is why you don't see it.

For any $a,b,n$ integer,

$$a^{n+1}\bmod b=(a\,a^n)\bmod b=a(a^n\bmod b)\bmod b,$$ which is a simple recurrence between $a^{n+1}\bmod b$ and $a^n\bmod b$. Thus $a^n\bmod b$ must be a periodic sequence of period at most $b$.

In your case, $b=2^m$ and you only look at the first bit.

If we consider the fifth column, $2^m=32$, the period is $1,3,9,27,17,19,25,11$, with length $8$ (check that $3\cdot11\bmod32=1$), with the leading bits $0,0,0,1,1,1,1,0$.

For the sixth column, modulo $64$: $1, 3, 9, 27, 17, 51, 25, 11, 33, 35, 41, 59, 49, 19, 57, 43$, length $16$ (and $3\cdot43\bmod64=1$).

Answer 3

It shouldn't be too difficult to realize that $a^k \pmod n$ will eventually always have a repeating pattern as there are only $n$ values of $\pmod n$ there must be a $a^k\equiv a^r\pmod n $ with $r > k$. And when that occurs $a^{k+i} \equiv a^{r+i}$ for all terms there after.

It's not so obvious (but still true nonetheless) that if $\gcd(a, n) =1$ then if $a^k \equiv a^r$ then $a^{k-1} \equiv a^{r-1}$ so that pattern begins "at the beginning with" $a^0 \equiv a^m \equiv 1$.

So the 5th column has pattern but you just don't have enough samples. We are looking at $a^k \equiv \pmod 2^5$ so the pattern is at most $32$

Eulers theorem says that $\phi(2^k) = 2^{k-1}$ and $3^{2^{k-1}}\equiv 1$ so the last $5$ digits have a repeating pattern of at most $16$. and if you look the last five digits of $3^{0} $ are $00001$ and the last five digits of $3^{16}$ are ... well you didn't go far enough.

$3^{16} = 101001000011010111010\color{blue}{00001}$.

But the pattern doesn't have to be $16$ long. It could be something that divides $16$. ANd in this case $3^{8} = 0000000011001101\color{blue}{00001}$ and the pattern is eight long.

And the pattern is $0,0,0,1,1,1,1,0$