# Solve the congruence relation $x^n\equiv 2\pmod {13}$.

Consider the congruence $x^n\equiv 2\pmod {13}$. This congruence has a solution for $x$ if

(A) $n=5$.

(B) $n=6$.

(C) $n=7$.

(D) $n=8$.

I apply Chinese remainder theorem to solve it but I am fail. Can anyone help me please ?

Update :(18th Nov)

In the given answer I am unable to understand the step $2^A\equiv 1 \pmod{13}$ implies $12$ divides $A$. It's justification in comment is computational. I want an analytical answer.

• $2$ is a primitive root modulo $13$. Does that help? – Rijul Saini Oct 4 '15 at 7:56
• @ Rijul Saini ) I did not solve it from this info...Please extend your hint.. – Empty Oct 4 '15 at 15:20
• @S.Panja-1729 Are you following lecture notes? – Did Oct 19 '15 at 6:57
• @ Did) I can't understand what do you mean? – Empty Oct 19 '15 at 7:11

## 8 Answers

Result: Let $p$ be a prime and $(a,p)=1$. Then the congruence $x^k\equiv a(\text{mod} ~p)$ has a solution iff $a^{(p-1)/d}\equiv 1(\text{mod}~p)$ where $d=(k,p-1)$

In your question $p=13$, $d=1,2,3,4,6$ Check for which $d$ the congruence $$2^{12/d}\equiv 1(\text{mod}~ 13)$$ has a solution.

You'll get $d=1$ so $(k,12)=1$ implies $k=5,7,11,...$

You can't do much better than the computional approach in the comment, but here is an approach that only requires two computations.

First, a lemma:

Lemma. If $$2^{x} \equiv 1 \mod n$$ and $$2^{y} \equiv 1 \mod n$$, then $$2^{\gcd(x,y)} \equiv 1 \mod n$$.

Proof. By Bezout's theorem, there exist $$a,b$$ such that $$ax+by=\gcd(x,y)$$. We clearly have $$2^{ax} \equiv 1 \mod n$$ and $$2^{by} \equiv 1 \mod n$$. Therefore $$2^{ax}\cdot2^{by} = 2^{\gcd(x,y)} \equiv 1 \mod n$$.

Note: one of $$a,b$$ is negative, but then we just take multiplicative inverse of it. But the multiplicative inverse of 1 is 1, so that doesn't give a problem.

We know by Fermat's Little Theorem that $$2^{12} \equiv 1 \mod 13$$. Now let $$p$$ be the smallest $$n$$ such that $$2^{n} \equiv 1 \mod 13$$. Then $$p\mid12$$. Otherwise, $$\gcd(p,12) and by the lemma $$p$$ wasn't the smallest such $$n$$.

Now we calculate $$2^{6}=64 \equiv -1 \not \equiv 1 \mod 13$$. Therefore divisiors of 6 are not possible. Since $$2^{4}=16 \equiv 3 \not \equiv 1 \mod 13$$, we have checked all divisiors of 12. Therefore 12 is really the smallest possible.

The order of $a$ mod $p$ (where $a$ and $p$ are coprime) is the least positive integer $m$ such that $a^m \equiv 1 \mod p$. Every $n$ such that $a^n \equiv 1 \mod p$ is then a multiple of $m$. This is because for any integer $n$ we can write $n = q m + r$ where $q$ is an integer and $0 \le r < m$, and if both $a^n$ and $a^m \equiv 1 \mod p$, $a^r \equiv a^n (a^m)^{-q} \equiv 1 \mod p$, but by assumption $m$ is the least positive integer such that $a^m \equiv 1 \mod p$ so we must have $r = 0$.

In your case, by Fermat's theorem $2^{12} \equiv 1 \mod 13$, so the order of $2$ mod $13$ must be a divisor of $12$. But $2^6 = 64 \equiv 12 \mod 13$,so the order can't be $6$ or one of its divisors, and $2^4 = 16 \equiv 3 \mod 13$, so the order can't be $4$. The only other possibility is that the order is $12$. Thus every $A$ such that $2^A \equiv 1 \mod 13$ is a multiple of $12$.

Since $(2,13)=1$, we can restrict the search to $U(13)$, the set of all $x$ with $(x,13)=1$.

Consider the map $\pi_n: x \mapsto x^n$ on $U(13)$. We want to know when $2$ is in the image of $\pi_n$.

Clearly, this happens when $\pi_n$ is surjective. By Fermat's theorem, $\pi_n$ is injective when $(n,12)=1$, and so is surjective in this case. Hence, $n=5$ and $n=7$ work.

We still may have that $2$ is in the image of $\pi_n$ when $(n,12)>1$. However, if we know that $2$ is a primitive root mod $13$, then this cannot happen because if $2$ were in the image, $\pi_n$ would be surjective, which it is not when $(n,12)>1$ because it is not injective.

$2$ is primitive in $\mathbb{Z}_{13}^\ast$ (the multiplicative group mod $13$) and $\phi(13)=12$. Therefore $$2^k\equiv1\pmod{13}\implies12\mid k$$ Subsequently, if $x^n\equiv2\pmod{13}$, then since $$2^{12/(n,12)}\equiv x^{n(12/(n,12))}\equiv x^{(n/(n,12))12}\equiv1\pmod{13}$$ we must have $(n,12)=1$.

For $n=5$, we have $x^5\equiv2\implies x\equiv x^{25}\equiv2^5\equiv6\pmod{13}$.

For $n=7$, we have $x^7\equiv2\implies x\equiv x^{49}\equiv2^7\equiv11\pmod{13}$.

As $2$ is a primitive root $\pmod{13},$

taking discrete logarithm on $$x^n\equiv2\pmod{13}\ \ \ \ (1)$$

$n$ind$_2x\equiv1\pmod{12}\ \ \ \ (2)$ as $\phi(13)=12$

Using Linear Congruence Theorem the solution will exist for $(1),$ hence for $(2)$ $$\iff(n,12)|1\iff(n,12)=1$$

Following Rijul Saini's hint above, write $x=2^y$ and solve the equations $ny= 1$ (mod 12).

• I couldn't understand Why $ny\equiv 1\pmod{12}$ ? – Empty Oct 5 '15 at 7:51
• @@Aravind) Please response.... – Empty Oct 7 '15 at 3:08
• $2^{ny}=2$ (mod 13), i.e. $2^{ny-1}=1$ (mod 13); Now $2^A=1$ (mod 13) implies 12 divides $A$, hence 12 divides $ny-1$. – Aravind Oct 7 '15 at 7:11
• I am unable to understand how $2^A\equiv 1\pmod{13}$ implies $12$ divides $A$.. – Empty Oct 7 '15 at 7:21
• Suppose that $A=12q+r$, where $0<r<12$. Then since $2^{12}=1(mod 13)$, we get $2^A=2^r$ (mod 13). Now calculate the powers $2^1,2^2,\ldots, 2^{11}$ and check that none of them are equal to 1 mod 13, which means $r=0$. – Aravind Oct 7 '15 at 10:58

$2$ is a non-residue mod $13$, which rules out the even powers $n=6$ and $n=8$. By happenstance, $x=2^5$ is a solution for $n=5$ and $x=2^7$ is a solution for $n=7$, since $5\cdot5\equiv7\cdot7\equiv1$ mod $12$.