Resolver la congruencia relación $x^n\equiv 2\pmod {13}$.

Question

Considerar la congruencia $x^n\equiv 2\pmod {13}$. Esta congruencia tiene una solución para $x$ si

(Un) $n=5$.

(B) $n=6$.

(C) $n=7$.

(D) $n=8$.

Puedo aplicar el teorema del resto Chino para solucionar eso pero me da error. Alguien me puede ayudar por favor ?

Actualización :(18 de Noviembre)

En la respuesta, soy incapaz de entender el paso de $2^A\equiv 1 \pmod{13}$ implica $12$ divide $A$. Es la justificación en el comentario es computacional. Quiero una respuesta analítica.

Answer 1

Resultado: % Let $p$ser un prime y $(a,p)=1$. Entonces el % de congruencia $x^k\equiv a(\text{mod} ~p)$tiene una solución iff $a^{(p-1)/d}\equiv 1(\text{mod}~p)$ donde $d=(k,p-1)$

En tu pregunta $p=13$, $d=1,2,3,4,6$ compruebe que $d$ la congruencia $$2^{12/d}\equiv 1(\text{mod}~ 13)$ $ tiene una solución.

Usted conseguirá $d=1$ por lo que implica de $(k,12)=1$ $k=5,7,11,...$

Answer 2

No se puede hacer mucho mejor que la computional enfoque en el comentario, pero aquí es un enfoque que sólo requiere de dos cálculos.

En primer lugar, un lexema:

Lema. Si $2^{x} \equiv 1 \mod n$$2^{y} \equiv 1 \mod n$,$2^{\gcd(x,y)} \equiv 1 \mod n$.

Prueba. Por el teorema de Bezout, no existe $a,b$ tal que $ax+by=\gcd(x,y)$. Claramente tenemos $2^{ax} \equiv 1 \mod n$$2^{by} \equiv 1 \mod n$. Por lo tanto,$2^{ax}\cdot2^{by} = 2^{\gcd(x,y)} \equiv 1 \mod n$.

Nota: uno de $a,b$ es negativo, pero luego nos acaba de tomar el inverso multiplicativo de la misma. Pero el inverso multiplicativo de 1 es 1, por lo que no da un problema.

Sabemos por Fermat Poco Teorema que $2^{12} \equiv 1 \mod 13$. Ahora vamos a $p$ ser el más pequeño $n$ tal que $2^{n} \equiv 1 \mod 13$. A continuación,$p\mid12$. De lo contrario, $\gcd(p,12)<p$ y por el lema $p$ no era el más pequeño de tales $n$.

Ahora calculamos $2^{6}=64 \equiv -1 \not \equiv 1 \mod 13$. Por lo tanto divisiors de 6 no son posibles. Desde $2^{4}=16 \equiv 3 \not \equiv 1 \mod 13$, hemos comprobado todos los divisiors de 12. Por lo tanto 12 es realmente el más pequeño posible.

Answer 3

El orden de $a$ mod $p$ (donde $a$ $p$ son coprime) es el menor entero positivo $m$ tal que $a^m \equiv 1 \mod p$. Cada $n$ tal que $a^n \equiv 1 \mod p$, entonces es un múltiplo de a $m$. Esto es debido a que para cualquier entero $n$ podemos escribir $n = q m + r$ donde $q$ es un número entero y $0 \le r < m$, y si tanto $a^n$ y $a^m \equiv 1 \mod p$, $a^r \equiv a^n (a^m)^{-q} \equiv 1 \mod p$, pero por supuesto, $m$ es el menor entero positivo tal que $a^m \equiv 1 \mod p$, por lo que debemos tener $r = 0$.

En su caso, por el teorema de Fermat $2^{12} \equiv 1 \mod 13$, por lo que el orden de $2$ mod $13$ debe ser un divisor de a $12$. Pero $2^6 = 64 \equiv 12 \mod 13$,por lo que el orden no puede ser $6$ o de uno de sus divisores, y $2^4 = 16 \equiv 3 \mod 13$, por lo que el orden no puede ser $4$. La única otra posibilidad es que el orden es $12$. Por lo tanto todos los $A$ tal que $2^A \equiv 1 \mod 13$ es un múltiplo de a $12$.

Answer 4

Desde $(2,13)=1$, podemos restringir la búsqueda a $U(13)$, el conjunto de todos los $x$$(x,13)=1$.

Considerar el mapa de $\pi_n: x \mapsto x^n$$U(13)$. Queremos saber cuándo $2$ es en la imagen de $\pi_n$.

Claramente, esto sucede cuando $\pi_n$ es surjective. Por el teorema de Fermat, $\pi_n$ es inyectiva cuando $(n,12)=1$, y así es surjective en este caso. Por lo tanto, $n=5$ $n=7$ trabajo.

Aún podemos tener ese $2$ es en la imagen de $\pi_n$ al $(n,12)>1$. Sin embargo, si sabemos que $2$ es una raíz primitiva de mod $13$, entonces esto no puede suceder, porque si $2$ fueron en la imagen, $\pi_n$ sería surjective, que no es al $(n,12)>1$ porque no es inyectiva.

Answer 5

es primitivo en $2$ $\mathbb{Z}_{13}^\ast$ (el multiplicative grupo mod $13$) y $\phi(13)=12$. Por lo tanto $$ 2 ^ {13} \implies12\mid de k\equiv1\pmod k $$ posteriormente, if $x^n\equiv2\pmod{13}$, luego desde $$ 2^{12/(n,12)} \equiv x^{n(12/(n,12))} \equiv x^{(n/(n,12)) 12} \equiv1\pmod {13} $$ debemos tener $(n,12)=1$.

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

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