Congruence $16^{(x^ 2+x+1)} \equiv 4 \mod 11$

Question

Given the congruence $16^{x^2+x+1}≡ 4 \mod 11$

I'm not necessarily sure how to approach this problem if someone can help me head in the right direction since 16 is not a primitive root of mod 11 I can't reduce the equation $x^2+x+1≡ 0 \mod 10$

since using taking the euler quotient of 11 gives 10.

I would guess to divide by 4 but I know that 4 is not a primitive root of mod 11 either.

Answer 1

But $2$ is a primitive root $\pmod{11}$, so you can consider $2^{4(x^2+x+1)}\equiv2^2\pmod{11}$ same as $4(x^2+x+1)\equiv2\pmod{10}$. Dividing both sides and the modulus by $2$, we get $2(x^2+x+1)\equiv1\pmod{5}$. Then we can multiply by $3$, being the reciprocal of $2$, to get $x^2+x+1\equiv x^2+6x+1\equiv3\pmod{5}$, where we have taken the liberty of adding $5x\equiv0\pmod{5}$. Then we can complete the square to get $(x+3)^2-9+1\equiv3\pmod{5}$, or $(x+3)^2\equiv11\equiv1\pmod{5}$. Thus $x+3\equiv\pm1\pmod{5}$, so the solutions are $x\equiv-2\equiv3\pmod{5}$ or $x\equiv-4\equiv1\pmod{5}$.

Answer 2

Note that since $16 \equiv 5 \text{ mod } 11$, we have $5^{x^2+x+1} \equiv 4 \text{ mod } 11$. Now we know $5^3 \equiv 4 \text{ mod } 11$, so $x^2+x+1 \equiv 3 \text{ mod } 5$ (because the order of 5 is 5 in $\mathbb{Z}_{11}$). A quick calculation shows $x \equiv 1 \text{ mod } 5$ or $x \equiv 3 \text{ mod } 5$. You only have to check for 1, 2 and 3 in $\mathbb{Z}_5$, because a polynomial of degree 2 over a field has at most 2 roots.

Answer 3

Using Property $\#12$ of this, we have $2x^2+2x\equiv-1\pmod5$

$$\iff-2\equiv2(2x^2+2x)=(2x+1)^2-1\iff(2x+1)^2\equiv-1\equiv4$$

$$\iff2x+1\equiv\pm2$$

If $2x+1\equiv2\iff2x\equiv1\equiv6\iff x\equiv3$

If $2x+1\equiv-2\iff2x\equiv-3\equiv2\iff x\equiv1$