Encontrar el entero x: $x \equiv 8^{38} \pmod {210}$

Question

Encontrar el entero x: $x \equiv 8^{38} \pmod {210}$

Se me rompió la parte superior en el primer mods:

$$x \equiv 8^{38} \pmod 3$$

$$x \equiv 8^{38} \pmod {70}$$

Pero $x \equiv 8^{38} \pmod {70}$ puede ser roto más:

$$x \equiv 8^{38} \pmod 7$$

$$x \equiv 8^{38} \pmod {10}$$

Pero $x \equiv 8^{38} \pmod {10}$ puede ser roto más:

$$x \equiv 8^{38} \pmod 5$$

$$x \equiv 8^{38} \pmod 2$$

Al final,me quedo con:

$$x \equiv 8^{38} \pmod 5$$

$$x \equiv 8^{38} \pmod 2$$

$$x \equiv 8^{38} \pmod 7$$

$$x \equiv 8^{38} \pmod 3$$

La resolución de cada una de ellas utilizando el teorema de fermat:

1. $x \equiv 8^{38}\equiv8^{4(9)}8^2\equiv64 \equiv 4 \pmod 5$

2. $x \equiv 8^{38} \equiv 8^{1(38)}\equiv 1 \pmod 2$

3. $x \equiv 8^{38} \equiv 8^{6(6)}8^2\equiv 64 \equiv 1 \pmod 7$

4. $x \equiv 8^{38} \equiv 8^{2(19)}\equiv 1 \pmod 3$

Así que ahora, tengo cuatro congruencias. ¿Cómo puedo solucionarlos?

Answer 1

La solución rápida para el Teorema del Resto Chino ejercicio es encontrar enteros $w,x,y,z$ tal que $105w + 70x+42y + 30z=1$. Entonces:

$$x\equiv 0\cdot 105w + 1\cdot 70x + 4\cdot 42y + 1\cdot 30z\pmod {210}$$

Answer 2

Se hizo un pequeño desliz cuando se trabaja $\bmod 2$, esto es debido a que $0^n$ es siempre congruente a $0$ no importa lo que la congruencia que está trabajando . Me repita este paso una vez más.

$8^{38}\equiv 3^{38}\equiv3^{9\cdot4}3^{2}\equiv(3^{4})^{9}3^2\equiv1^9\cdot3^2\equiv9\equiv 4\bmod 5$

$8^{38}\equiv0 \bmod 2$ ya que es claramente aún.

$8^{38}\equiv(1)^{38}\equiv 1\bmod 7$

$8^{38}\equiv(-1)^{38}\equiv 1 \bmod 3$

Así que usted tiene el siguiente sistema de ecuaciones:

$x\equiv4 \bmod 5$

$x\equiv 0 \bmod 2$

$x\equiv 1 \bmod 7$

$x\equiv 1 \bmod 3$

Hay maneras de resolver esto, pero es posible resolver paso a paso el uso básico de las sustituciones.

Empezamos por escribir $x=2k$ desde $x\equiv 0 \bmod 2$

Ahora tenemos $2k\equiv 1 \bmod 3$. Multiplicar por dos conseguimos $4k\equiv 2\bmod 3$ desde $4\equiv 1$ tenemos $k\equiv 2 \bmod 3$ $k=3j+2$ $x=2(3j+2)=6j+4$

Tenemos $6j+4\equiv 1 \bmod 7$$6j\equiv-3\equiv 4 \bmod 7$. Multiplicando por $6$ obtenemos $36j\equiv 24\equiv 3 \bmod 7$ Desde $36\equiv 1 \bmod 7$ tenemos $j\equiv 3 \bmod 7$. Por lo $x=6(7l+3)+4=42l+22$

Tenemos $42l+22\equiv 4 \bmod 5$ de aquí a $42l\equiv -18\equiv2 \bmod 5$ Desde $42\equiv 2 \bmod 5$ tenemos $2l\equiv 2 \bmod 5$$l\equiv 1 \bmod 5$. Por lo $l=5s+1$$x=42(5s+1)+22=210s+64$. Por lo $8^{38}\equiv 64\bmod 210$

---

Segunda solución: en Lugar de utilizar el teorema de Fermat uso Carmichael del teorema que dice que si $a$ $n$ son relativamente primos, a continuación,$a^{\lambda(n)}\equiv 1 \bmod n$. Usando esto y el hecho de que $\lambda(105)=12$

llegamos $8^{38}\equiv 8^{36}a^2\equiv (8^{12})^8a^2\equiv 1^38^2\equiv 8^2\equiv64\bmod 105$

Usando esto y el hecho de que $8^{38}$ es incluso llegamos $8^{38}\equiv 64\bmod 210$

---

Nota: El teorema que nos dice que podemos separar congruencias en congruencias mod el poder de los números primos dividiendo el número es llamado el teorema del Resto Chino. Este método nos asegura que la solución existe y es única.

Answer 3

Por Fermat: $\,\color{#0a0}{2,4,6}\mid\color{#c00}{12}\,\Rightarrow {\rm mod}\ \color{#0a0}{3,5,7}\!:\ 8^{\color{#c00}{12}}\equiv 1,\,$ $\, 8^{38}\equiv 8^2(8^{\color{#c00}{12}})^3\equiv 8^2\,$ e $ $ mod $\,2$

---

Comentario $\ $ Se generaliza. Por encima de es caso especial $\,\varphi = 36,\,k=2\,$ de la siguiente generalización de Fermat y el teorema de Euler $\rm\color{blue}{(E)},\,$ , lo que claramente se extiende a cualquier número de números primos.

Teorema $\ \ \, n^{\large \varphi+k}\equiv n^{\large k}\pmod{p^i q^j}\ \ $ si $\ p\ne q\,$ primer, $ \ \color{#0a0}{\varphi(p^i),\varphi(q^j)\mid \varphi},\ $ $\, i,j \le k $

${\bf Proof}\,\ \ p\nmid n\,\Rightarrow\, {\rm mod\ }p^i\!:\ n^{ \varphi}\equiv 1\,\Rightarrow\, n^{\varphi+k}\equiv n^k,\ $ $\,\ n^{\large \color{#0a0}\varphi} = (n^{\color{#0a0}{\large \varphi(p^{ i})}})^{\large \color{#0a0}\ell}\overset{\color{blue}{\rm (E)}}\equiv 1^{\large \ell}\equiv 1$

$\qquad\quad\ \ \color{#c00}{p\mid n}\,\Rightarrow\, {\rm mod\ }p^i\!:\ n^k\equiv 0\,\equiv\, n^{\varphi+k}\ $ $\ n^k = n^{k-i} \color{#c00}n^i = n^{k-i} (\color{#c00}{mp})^i$ $\,k\ge i$

Por lo $\ p^i\!\mid n^{\varphi+k}\!-n^k.\,$ Por simetría $\,q^j$ divide demasiado, por lo que su lcm $ = p^iq^j\,$ divide demasiado. $\ $ QED

Véase también Carmichael de la función Lambda, una generalización de Euler del phi de la función.

Answer 4

Una solución alternativa, utilizando el Teorema del Resto Chino.

En primer lugar, $2, 3, 5$ y 7 pares de primos relativos por lo tanto sabemos que el siguiente sistema de congruencias tiene una única solución modulo $2\times3\times5\times7=210$.

\begin{cases} x \equiv 4 \pmod {5} \\ x \equiv 0 \pmod {2} \\ x \equiv 1 \pmod {7} \\ x \equiv 1 \pmod {3} \end{casos}

Comience con la primera congruencia y convertirla en una ecuación

$x\equiv 4 \pmod 5$ $\iff x = 5k + 4$ (por la definición de congruencia)

Conectando en la segunda congruencia:

$5k+4 \equiv 0\pmod {2}$ $\iff$ $5k \equiv 0 \pmod {2}$

Para deshacerse de las 5 en el lado izquierdo, se multiplican ambos lados de la congruencia por el inverso de 5 mod 2 a 1 por el algoritmo de euclides extendido. Por lo tanto:

$k \equiv 0 \pmod {2}$ $\iff$ $k = 2k'$

Lo que significa que $x = 5k + 4 = 5(2k') + 4 = 10k' + 4$

Ahora reemplazando en la tercera ecuación:

$10k' + 4 \equiv 1 \pmod {7}$ $\iff$ $10k' \equiv 4 \pmod {7}$

Multiplicar ambos lados por 5, la inversa de 10 mod 7.

$k' \equiv 6 \pmod {7}$ $\iff$ $k' = 7k'' + 6$

Lo que significa que $x = 10k' +4 = 10(7k'' + 6) + 4 = 70k'' + 64$

Finalmente, sustituyendo en la última ecuación:

$70k'' + 64 \equiv 1 \pmod {3}$ $\iff$ $70k' \equiv 0 \pmod {3}$

Multiplicar ambos lados por 1, la inversa de los 70 mod 3.

$k' \equiv 0 \pmod {3}$ $\iff$ $k'' = 3k'''$

Así

$x = 70k'' + 64 = 70(3k''') + 64 = 210k''' + 64$ $\iff$ $x \equiv 64 \pmod {210}$

Answer 5

Aquí es una solución que no hacen uso de Fermat Poco Teorema.

---

El Algoritmo:

• Entrada: $x=8,e=38,n=210$

• Salida: $y=1$

• Repita hasta que $e=0$:

  • Si $e\equiv1\pmod2$, a continuación, establezca $y=yx\bmod{n}$

  • Set $x=x^2\bmod{n}$

  • Set $e=\left\lfloor\frac{e}{2}\right\rfloor$

Implementación En C:

int PowMod(int x,int e,int n)
{
    int y = 1;
    while (e > 0)
    {
        if (e & 1)
            y = (y*x)%n;
        x = (x*x)%n;
        e >>= 1;
    }
    return y;
}

int result = PowMod(8,38,210); // 64

Intermedio De Salida:

   x   |   e   |   y
-------|-------|-------
    8  |   38  |    1
   64  |   19  |    1
  106  |    9  |   64
  106  |    4  |   64
  106  |    2  |   64
  106  |    1  |   64
  106  |    0  |   64

---

Por favor, tenga en cuenta que la complejidad es $O(\log_2e)$, lo que resulta en $\lceil\log_238\rceil=6$ iteraciones.