Congruence $x^n\equiv2 \pmod{13}$ (Multiple Choice)

Question

I was trying to solve the following problem.Please help.

Consider the $x^n\equiv2 \pmod{13}$. It has a solution for $x$ if

1. $n=5$
2. $n=6$
3. $n=7$
4. $n=8$

It may have more than one correct options.

Thnx in advance.

Answer 1

We have $6^5\equiv 2$ mod $13$ and $11^7\equiv 2$ mod $13$. So for $n=5$ and $n=7$ there is a solution. It is easy to see that there is no solution for $n=6$ and $n=8$.

Answer 2

First, compute the powers of $2$ mod $13$:

$$\begin{align} 2^0&=1\\2^1&=2\\ &\vdots\\2^{12}&=1\end{align}$$

Note that $\{2^n:n\in\Bbb N\}$ spans the whole set of unities of $\Bbb Z_{13}$, that is, $2$ is a primitive root of $\Bbb Z_{13}$.

For each unity $x$ of $\Bbb Z_{13}$ there exists $j$ such that $x=2^j$. So the equation $x^n=2$ implies that $$(2^j)^n=2^{jn}=2=2^{12k+1}$$ or $jn-12k=1$. This equation has solutions for $n$ and $k$ iff $\gcd(12,j)=1$.

Answer 3

While one can use brute force, it is more instructive (and almost as quick) as follows.

First, notice $\,\ 2\,\not\equiv\, x^n\pmod{13}\,$ if $\ \overbrace{n = \color{#c00}3j\ \ {\rm or}\ \ \color{#0a0}2j}^{\large \iff (n,12)\,>\, 1}$ since, by little Fermat $ =\color{#c0d}{\rm\ell \,F}$

$\qquad\ \ \ \,\begin{eqnarray} &&\ 2 &\equiv&\! x^{\large \color{#c00}3j} &\qquad\ \ & && \ 2 &\equiv&\! x^{\large \color{#0a0}2j}\\ \overset{(\ \ )^{\Large 4}}\Rightarrow && 2^4 &\equiv&\! x^{12j}\overset{\color{#c0d}{\rm\ell \,F}}\equiv 1\,\Rightarrow\!\Leftarrow &\quad& \overset{(\ \ )^{\Large 6}}\Rightarrow\!\! &&2^6 &\equiv&\! x^{12j}\overset{\color{#c0d}{\rm\ell \,F}}\equiv 1\,\Rightarrow\!\Leftarrow \end{eqnarray}$

Conversely $\ (n,12)=1\,\overset{\exists k}\Rightarrow\, nk\equiv 1\pmod{12}\,\Rightarrow\, x^{nk}\equiv 1\pmod{13}\ $ if $\ 13\nmid x.\ $ Therefore $\,x\mapsto x^n\,$ has inverse $\ x\mapsto x^k\,$ and reversely. Hence $\smash[b]{\ y \equiv x^{\large n}\underset{ (\ \ )^{\Large n}}\Leftarrow\overset{(\ \ )^{\Large k}}{\!\!\!\!\!\!\Rightarrow}\!\! y^{\large k}\equiv x\pmod{13}.\,}$

Therefore $\,2 \equiv x^n\!\pmod{13}\,$ is solvable $\iff (n,12) = 1,\,$ i.e. $\,n\,$ is coprime to $12.$

Remark $\ $ If you know about primitive roots (or cyclic groups) then you will find it instructive to reformulate the above in that language. The first half of the above proof shows $\,2\,$ has order $\color{#c00}{\,12\,}$ since $\,2^{\large 12/p}\not\equiv 1\,$ for all primes $\,p\mid 12.\,$ So, by pigeonholing, every remainder $\not\equiv 0\,$ is congruent to a power of $\,2.\,$ So $\,x \equiv 2^a,\,$ so $\,\exists x\!:\, 2\equiv x^n\equiv 2^{an}\!\iff\! \exists a\!:2^{an-1}\equiv 1\iff \exists a\!:\,\color{#c00}{12}\mid an-1,\,$ or equivalently $\iff\,n\,$ is invertible $\smash[b]{\!\!\pmod{12}\!\!\underset{\rm Bezout}\iff (n,12) = 1.\,}$ Now it is straightforward to translate into the language of cyclic groups.