$3^{15} \mod 17$ I would like using Fermat theorem and doing something like this $\frac{3^{16}}{3} \mod 17$ that is possible?
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}$$
Related videos on Youtube
Comments
-
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 over 6 yearsWriting 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 over 6 yearsok, thanks a lot
-
-
lulu over 6 yearsBy Little Fermat, we have $3^{16}\equiv 1 \pmod {17}$ .
-
Walter White over 6 yearsThanks, very helpful
-
Walter White over 6 yearsThanks for your attention, very helpful