La resolución de una congruencia $x^{17} \equiv 243 \pmod{257}$

Question

Estoy tratando de resolver la siguiente congruencia:

$x^{17} \equiv 243 \pmod{257}$

Yo me imagino que el $\gcd(243,257)=1$ y $243=3^5$

Por lo $x^{17} \equiv 3^5 \pmod{257}$

y yo no entiendo muy bien qué hacer a continuación.

Answer 1

Queremos resolver $x^{17} \equiv 3^5 \pmod{257}$. Elevar ambos lados de la energía $15$ para obtener $$x^{255} \equiv 3^{75} \pmod{257},$$ o, equivalentemente,$x^{-1} \equiv 3^{75} \pmod {257}$. Por lo tanto $x \equiv 3^{-75} \equiv 28 \pmod{257}$.

Answer 2

Desde $257$ es un número primo por Fermat poco teorema $a^{256}\equiv 1\mod 257\ \forall a, 257\not|a$ Ahora, vamos a encontrar si existe una solución de la forma $3^y$. Si no es entonces la ecuación se convertirá en $$3^{17y-5}\equiv 1\mod 257\Rightarrow 256|17y-5$$ $y=181$ is a solution to this. So $x=3^{181}$ is one solution and all the solutions of the form $3^y$ can be obtained by solving the linear Diphontaine equation $$17y-256z=5$$. Ahora, si hay soluciones de la forma $3^ya$ donde $a$ no contiene $3$ como factor principal, a continuación, la ecuación se lee como $$a^{17}3^{17y-5}\equiv 1\mod 257$$ Pero no estoy seguro de cómo resolver esto.

Answer 3

Disponemos de los siguientes hechos: $\gcd(3,257)=1,\,$ $\varphi(257)=256,\,$ y 3 es una raíz primitiva mod 257. De las dos primeras sabemos, véase, por ejemplo, Cuando se $a^n \equiv a^{(n \;\bmod \; \varphi(m))} \pmod m$ válido, $$3^n \equiv 3^{(n \;\bmod \; \varphi(257))} \equiv 3^{(n \;\bmod \; 256)} \pmod {257}$$ Hacer el Ansatz $x=3^y$, luego $$x^{17}\equiv 3^5 \pmod {257} \iff 3^{17y-5}\equiv 1 \equiv 3^0 \pmod {257}$$ Ahora solucione $17y-5\equiv 0 \pmod {256}\,$. El inverso multiplicativo es$17^{-1} \equiv 241 \pmod {256}\,$$y=5\times 241 \equiv 181 \pmod {256}.\,$, por Tanto, una solución es$$x=3^y=3^{181} \equiv 28 \pmod {257}.$$ Ahora se puede comprobar que $28^{17} \equiv 243 \pmod {257}.$