The last eight digits of the binary development of $27^{1986}$

Question

Find the last eight digits of the binary development of $27^{1986}$.

We define $v_p(x)$ such that if $v_p(x) = n$, then $p^n \mid x$ but $p^{n+1} \nmid x$. Now we see that if $n \geq 2$ is an integer and $r$ is even, if $v_2(3^r-1) = n$, then $v_2(3^{2r}-1) = n+1$. Otherwise if $n$ is odd then if $v_2(3^r-1) = n$, then $v_2(3^{2r}-1) = n+2$.

How do I continue from here?

Answer 1

The crucial facts for the solution are:

• You want to compute $27^{1986} \bmod{256}$

• $3^{64} \equiv 1 \bmod{256}$

• $3\cdot1986 \equiv 6 \bmod 64$

These imply that $27^{1986} = 3^{3\cdot1986} \equiv 3^6 = 729 \equiv 217\bmod{256}$.

Answer 2

The last $8$ binary digits represent the residue class of the number $\pmod {100000000_2}$ which in decimal is written $\pmod {256}$.

From the Carmichael function we know that $\lambda(256) = 64$ is the maximum order of any number (and the order of every number will divide this), and since $27$ is coprime to $256$, $27^{64}\equiv 1 \bmod 256$. We also see that $1986 = 2 \bmod 64$. So the answer in decimal is

$$27^{1986}\equiv 27^2 \equiv 729\equiv 217\bmod 256 $$

which converts to binary as

$$217_{10} = 11011001_2$$