$3^{15} \mod 17$ I would like using Fermat theorem and doing something like this $\frac{3^{16}}{3} \mod 17$ that is possible?

1,411

Solution 1

This is correct, in some senses.

In modular arithmetic, we can't have fractions, but we can consider $\frac 13$ as the inverse of $3$.

In modular arithmetic, the inverse of a number $a$ in modulo $n$ is a number $b$ such that $$a\times b\equiv 1\mod n$$

That is to say here we want to find a number $b$ such that $$3b\equiv 1\mod 17$$

We can try every number from $1$ to $17$ to find this number:

\begin{align}3\times 1&\equiv 3\mod 17\\ 3\times 2&\equiv 6\mod 17\\ 3\times 3&\equiv 9\mod 17\\ 3\times 4&\equiv 12\mod 17\\ 3\times 5&\equiv 15\mod 17\\ 3\times 6&\equiv 18\mod 17\equiv 1\mod 17\end{align}

Therefore $$\frac 13\mod 17\equiv 6\mod 17$$

If we check using WolframAlpha, we can see that $$3^{15}\mod 17\equiv 6$$

Solution 2

NOte that : $$ac\equiv bc \space (mod \space k) \to \\ a \equiv b \space (mod \space \dfrac{k}{(k,c)})$$ $$3^{16}\equiv 1 \pmod {17}\\ 3^{16}\equiv 1+17 \pmod {17}\\3^{16}\equiv 18 \pmod {17}$$ now divide both sides by $3$

$$3.3^{15}\equiv 18 \pmod {17}\to /3\\ 3^{15}\equiv 6 \pmod {\dfrac{17}{(17,3)}}\\ 3^{15}\equiv 6 \pmod {\dfrac{17}{1}}\\3^{15}\equiv 6 \pmod {17}$$

Share:
1,411

Related videos on Youtube

Walter White
Author by

Walter White

IT student at Białystok University of Technology.

Updated on May 26, 2020

Comments

  • Walter White
    Walter White over 3 years

    $$3^{15} \mod 17$$ $$3^{15} \mod 17 \implies \frac{3^{16}}{3} \mod 17$$

    It seemed to me the correct result would be $\frac{1}{3}$.

    • lulu
      lulu over 6 years
      Writing things like $\frac 13\pmod p$ isn't great. if you mean the solution, $x$, to the congruence $3x\equiv 1 \pmod {17}$ then we just have $x\equiv 6$, which is correct.
    • Walter White
      Walter White over 6 years
      ok, thanks a lot
  • lulu
    lulu over 6 years
    By Little Fermat, we have $3^{16}\equiv 1 \pmod {17}$ .
  • Walter White
    Walter White over 6 years
    Thanks, very helpful
  • Walter White
    Walter White over 6 years
    Thanks for your attention, very helpful