5 votos

¿Cómo resolver la congruencia$x^{59} \equiv 604 \pmod{2013}$?

ps

¿Podría alguien darme alguna pista? No tengo ni idea de cómo empezar.

Veo que$$x^{59} \equiv 604 \pmod{2013}$ es primo.

4voto

Jon Snow Puntos 101

Sea$t$ un entero tal que$t^{59} \equiv 604 \pmod{2013}$; entonces,$t^{59} = 604+2013k$ para un cierto número entero$k$. Dado que$\gcd(604,2013) = 1$, Algoritmo euclidiano nos dice$\gcd(t^{59},2013)=1$ y por lo tanto$\gcd(t,2013)=1$. Así, podemos aplicar el Teorema de Euler.

Tenga en cuenta que$\varphi(2013) = 1200$ y$\gcd(1200,59) = 1$. Por el Lemma de Bézout, existen enteros$n,m$ tales que$1200n+59m = 1$. El teorema de Euler dice$t^{1200} \equiv 1 \pmod{2013}$, así que$t^{1200n} \equiv 1 \pmod{2013}$.

$t^{59} \equiv 604 \pmod{2013}$

$t^{59m} \equiv 604^m \pmod{2013}$

$t^{59m} \equiv t^{59m}t^{1200n} \equiv t^{59m+1200n} \equiv t\equiv 604^m \pmod{2013}$

Todo lo que tienes que hacer es encontrar explícitamente$m$ usando el Algoritmo Euclidiano Extendido.

3voto

Farkhod Gaziev Puntos 6

Como$(604,2013)=1,x$ debe ser co-prime a$2013$

Como$2013=3 \cdot 11 \cdot 61,$ usando la función de Carmichael ,

ps

ps

Así que tenemos$$x^{60}\equiv1\pmod{2013}$ $

¿Puedes encontrar$$x^{59}\equiv604\pmod{2013}\implies x^{60}\equiv604x$ utilizando el Algoritmo de Euclid ?

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X