So I know that 3 is a primitive root of 269.

How can I solve $x^{30} ≡ 81x^6 \pmod{269}$

Even if I substitute $x$ with $3^y$, where $y$ lies between 0 and 267, I can’t get any solutions.


1 Answer 1


We can easily see that $x=0$ is a solution.
Since $3$ is a primite root modulo $269$, let $x \equiv 3^t \pmod{269}$. hence, we get the congruence:

$$3^{30t} \equiv 3^4 \cdot 3^{6t} \pmod{269} $$ We know that if $g$ is a primitive root modulo $n$, then $$ g^r \equiv g^s \pmod{n} \iff r \equiv s \pmod{\phi(n)}$$ Since $269$ is a prime we get that $\phi(269) = 268$, and then we get the congruence: $$ 30t \equiv 4 \cdot 6t \pmod{268} $$ which gives $2$ solutions for $t$, $\space$ $t\equiv 0 \pmod{268} $ or $t\equiv 134 \pmod{268}$.
From the first solution we get that $x\equiv 1 \pmod{269}$ which means that $$ \big\{ x = 1 +269k \mid k\in \mathbb{Z}\big\}$$ is one set of solutions.
From the second solution we get that $x\equiv 268 \pmod{269}$ which means that $$ \big\{ x = 268 +269k \mid k\in \mathbb{Z}\big\}$$ is another set of solutions.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .