8
$\begingroup$

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.

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

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,...$

$\endgroup$
2
$\begingroup$

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)<p$ 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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$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}$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I couldn't understand Why $ny\equiv 1\pmod{12}$ ? $\endgroup$ – Empty Oct 5 '15 at 7:51
  • $\begingroup$ @@Aravind) Please response.... $\endgroup$ – Empty Oct 7 '15 at 3:08
  • $\begingroup$ $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$. $\endgroup$ – Aravind Oct 7 '15 at 7:11
  • $\begingroup$ I am unable to understand how $2^A\equiv 1\pmod{13}$ implies $12$ divides $A$.. $\endgroup$ – Empty Oct 7 '15 at 7:21
  • $\begingroup$ 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$. $\endgroup$ – Aravind Oct 7 '15 at 10:58
0
$\begingroup$

$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$.

$\endgroup$
0
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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