6
$\begingroup$

I want to ask for what values of $n$ the congruence $$x^n \equiv 2 \pmod{13}$$ has a solution for $x$.

$\endgroup$
4
$\begingroup$

Hints: Note that $x^{12k+m}\equiv x^m\pmod{13}$. So you will "only" have to examine the cases $m=0$ to $11$.

If $m$ and $12$ are relatively prime, then the congruence $x^m\equiv a\pmod{13}$ always has a solution.

So we are down to $m=0$, $2$, $3$, $4$, $6$, $8$, $9$, $10$.

You can find shortcuts to deal with some of these. For example, once you find that $x^2\equiv 2$ has no solutions, that rules out the even $m$ in the list. (One can use a theorem to rule out $m=2$, or one can square the numbers $1$ to $6$.) There are other theorems one could quote to bypass calculations.

Remark: The following theorem lets us deal quickly with the problem,with minimal calculation.

Theorem: Let $a$ be relatively prime to the prime $p$. Then the congruence $x^k\equiv a\pmod{p}$ has a solution if and only if $a^{(p-1)/d}\equiv 1\pmod{p}$, where $d=\gcd(k,p-1)$.

Let $p=13$ and $a=2$. The possible $d$ are $1,2,3,4,6,12$. Since $2^4\not\equiv 1\pmod{13}$ and $2^6\not\equiv 1\pmod{13}$, it follows that $x^k\equiv 2\pmod{13}$ has a solution if and only if $\gcd(k,12)=1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Among 0,1,2,3,4,6,8,9,10, only possible value is 1. $\endgroup$ – Sungjin Kim Sep 24 '13 at 9:06
3
$\begingroup$

For this question it is assumed that the student is familiar with primitive roots.

Note that $2$ is a primitive root of $13$. In other words, the smallest exponent that when $2$ is raised to it gives $1$ is $12$.

Now you need to know this theorem:

Theorem: If $p$ is a prime number and $a$ is an integer such that $(a,p)=1$ and $g$ is a primitive root of $p$ such that $g^b \equiv a \pmod{p}$ then $x^n \equiv a \pmod{p}$ has a solution if and only if $(n,p-1)|b$

Do you see how you can apply this theorem here?

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.