Finding powers of 2 and 3 in modular arithmetic

Question

Find all the powers of $2$ and $3$ modulo $17$.

How would you solve this question and explain the steps please!

Answer 1

Recall that:

$$2^m\equiv k \pmod{17} \implies 2^{m+1}\equiv 2k \pmod {17}$$

We can then list, remembering that if our $k$ is greater than $17$, we subtract $17$ from it.

$$1\equiv 1 \pmod {17}$$ $$2\equiv 2 \pmod {17}$$ $$4\equiv 4 \pmod {17}$$ $$8\equiv 8 \pmod {17}$$ $$16\equiv 16 \pmod {17}$$ $$32\equiv 15 \pmod {17}$$ (Because $16\cdot 2= 32$, but $32>17$ so we apply $32-17=15$) $$64\equiv 13 \pmod {17}$$ (Because $15\cdot 2 = 30$, but $30>17$, so we apply $30-17=13$)

$$128\equiv 9 \pmod {17}$$ (same as above) $$256\equiv 1 \pmod {17}$$ And now we have a cycle, so $2^k\equiv 1,2,4,8,9,13,15,16\pmod{17}$

Now do the same for the powers of $3$. As a check, you should get $3^k\not\equiv 0 \pmod{17}$

Answer 2

If you want all the powers explicitly there's no other way but computing them. If you want some beforehand information on about how many computations you have to do you can reason along the following lines.

• You know that $2^4=16\equiv-1\bmod17$. Thus $2^8=(2^4)^2\equiv(-1)^2=1\bmod17$ and so there are just $8$ different powers of $2\bmod17$ to compute.
• $3^2=9\equiv-8=-2^3\bmod17$, so up to a sign the even powers of $3$ are powers of $2$ which you already have computed. In fact $3^8=(3^2)^4\equiv(-2^3)^4=(2^4)^3\equiv-1\bmod17$ because of the previous computation so that the cycle of the powers of $3\bmod 17$ has length $16$ thus including all non-zero classes in $\Bbb Z_{17}$.

Answer 3

Just do it.

As $17$ is prime we know by Fermat's Little Theorem that at most there will be $17-1=16$ of them, but there might be fewer if $a^k \equiv 1\pmod{17}$ and $k\mid 16$.

$2^1 \equiv 2 \pmod {17}$

$2^2 \equiv 2*2\equiv 4 \pmod {17}$

$2^3 \equiv 2*4 \equiv 8 \pmod {17}$

$2^4 \equiv 2*8\equiv 16 \equiv -1 \pmod {17}$. COOL! $2^8\equiv (2^4)^2 \equiv (-1)^2 \equiv 1 \pmod{17}$ so there will only be $8$ of them!

$2^5 \equiv 2*(-1) \equiv -2 \equiv 15 \pmod{17}$

$2^6 \equiv 2*(-2) \equiv -4 \equiv 13 \pmod{17}$

$2^7 \equiv 2*(-4) \equiv -8 \equiv 9 \pmod {17}$

$2^8 \equiv 2*9\equiv 18 \equiv 1 \pmod{17}$

So that's it for $2$s.

....

$3$s.

$3^1 \equiv 3\pmod{17}$

$3^2 \equiv 3*3 \equiv 9 \pmod{17}$

$3^3 \equiv 3*9 \equiv 27 \equiv 10\equiv -7 \pmod {17}$

$3^4 \equiv 3*(-7)\equiv -21\equiv -4 \equiv 13 \pmod {17}$

$3^5 \equiv 3*(-4) \equiv -12\equiv 5 \pmod{17}$.

$3^6 \equiv 3*5 \equiv 15\equiv -2 \pmod {17}$

$3^7 \equiv 3*(-2) \equiv -6 \equiv 11 \pmod {17}$.

$3^8 \equiv 3*(-6) \equiv -18 \equiv -1 \pmod {17}$

As $3^8 \equiv -1$ we can do the rest by taking negatives

$3^9 \equiv -3^1 \equiv -3 \equiv 14 \pmod{17}$.

$3^{10} \equiv -3^2 \equiv -9 \equiv 8 \pmod {17}$

$3^{11} \equiv -3^3 \equiv 7\pmod {17}$

$3^{12} \equiv -3^4 \equiv 4 \pmod {17}$

$3^{13} \equiv - 3^5 \equiv 12 \pmod {17}$

$3^{14} \equiv -3^6 \equiv 2 \pmod {17}$

$3^{15} \equiv -3^7 \equiv 6 \pmod{17}$

$3^{16} \equiv -3^8 \equiv 1 \pmod {17}$.

And that's it for the $3$s.