# Congruence with powers and primitive roots

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?

• Can you solve $3^n\equiv 25\pmod {31}$? That seems like a good start.
– lulu
Nov 30, 2020 at 15:34
• Let $x=3^y$.... Nov 30, 2020 at 15:42
• @J.W.Tanner I managed to reach the resolution below with this tip ... thanks! Nov 30, 2020 at 15:52

$$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$$?

• Or square $\,3^5\equiv -5,\,$ Btw, "or" is not a good substtitute for $\!\iff\ \$ Nov 30, 2020 at 15:59
• $x\equiv 7, 13, 19, 25,$ or $28\pmod{31}$ ? Nov 30, 2020 at 16:06
• $x≡7,1\color{red}4,19,25,$ or$28 \pmod{31}$ Nov 30, 2020 at 16:29
• @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 Nov 30, 2020 at 16:31
• 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. Nov 30, 2020 at 17:00

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$$