Determine all the solutions of the congruence
$x^{85} ≡ 25 \pmod{31}$
using index function in base $3$ module $31$.
It is clear to me that $3$ is primitive root module $31$, but how do I use this information in the solution?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Can you solve $3^n\equiv 25\pmod {31}$? That seems like a good start. $\endgroup$– luluNov 30, 2020 at 15:34
-
1$\begingroup$ Let $x=3^y$.... $\endgroup$– J. W. TannerNov 30, 2020 at 15:42
-
1$\begingroup$ @J.W.Tanner I managed to reach the resolution below with this tip ... thanks! $\endgroup$– gmn_1450Nov 30, 2020 at 15:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
$3^22^2\equiv5 $ and $2^2\equiv(-3)^3$, so $3^5\equiv -5$, and $3^{10}\equiv25\pmod{31}$.
Let $x=3^y$, so you're asking for $(3^y)^{85}\equiv3^{10}\pmod{31},$ which means $85y\equiv10\pmod{30}$
$\iff 17y\equiv2\bmod6\iff y\equiv4\bmod6\iff y\equiv 4, 10, 16, 22, $ or $28\pmod{30}$.
Now do you see how $x^{85}\equiv25\pmod{31}$ can be solved using indices with base $3$?
answered Nov 30, 2020 at 15:48
-
1$\begingroup$ Or square $\,3^5\equiv -5,\,$ Btw, "or" is not a good substtitute for $\!\iff\ \ $ $\endgroup$ Nov 30, 2020 at 15:59
-
$\begingroup$ $x\equiv 7, 13, 19, 25, $ or $28\pmod{31}$ ? $\endgroup$– gmn_1450Nov 30, 2020 at 16:06
-
$\begingroup$ $x≡7,1\color{red}4,19,25,$ or$ 28 \pmod{31}$ $\endgroup$ Nov 30, 2020 at 16:29
-
$\begingroup$ @BillDubuque: I did square $3^5\equiv-5$. By "or" I meant "in other words", not "alternatively", but I think I see what you meant, so I changed my wording $\endgroup$ Nov 30, 2020 at 16:31
-
$\begingroup$ What I meant is that if you simply compute the sequence of powers $3^n$ then you find $\,3^5\equiv -5\,$ very quickly, so there is not really any need to attempt to optimize here. $\endgroup$ Nov 30, 2020 at 17:00
$\begingroup$
$\endgroup$
Using Discrete logarithm with respect to base $3$,
$85\cdot$ind$_3x\equiv2\cdot$ind$_35\pmod{30}$
As $85\equiv-5\pmod{30},$
$-5\cdot$ind$_3x\equiv2\cdot$ind$_35\pmod{30}\ \ \ \ (1)$
$3^3\equiv-4,3^5\equiv9\cdot(-4)\equiv-5\pmod{31}$
As $3$ is a primitive root $\pmod{31}, -1\equiv3^{30/2}\pmod{31}$
$\implies5\equiv3^{15}\cdot3^5\pmod{31}$
By $(1), -5\cdot$ind$_3x\equiv2\cdot20\pmod{30}\equiv-20$
Dividing through out by $-5$
ind$_3x\equiv4\pmod6$
$\implies x\equiv3^{4+6k}\pmod{31}$ where $0\le4+6k\le30\iff0\le k\le4$
