Cómo utilizar tanto el pequeño teorema de Fermat como el teorema del resto chino para encontrar 3 ^ 302 mod 35

Answer 1

Así es como va.

Primero, observe que [matemáticas] 35 = 5 \ cdot 7 [/ matemáticas], con 5 y 7 como factores primos diferentes.

Digamos que [math] 3 ^ {302} [/ math] es [math] a [/ math] mod 5 y [math] b [/ math] mod 7.

Entonces podemos determinar una única [matemática] m [/ matemática] tal que [matemática] 3 ^ {302} [/ matemática] es [matemática] m [/ matemática] mod 35, y [matemática] 0 \ le m <35 [/matemáticas]. Entonces, encontremos que [matemáticas] m [/ matemáticas].

El pequeño teorema de Fermat establece que para entero [matemáticas] n [/ matemáticas] y primo [matemáticas] p [/ matemáticas], [matemáticas] n ^ {p – 1} [/ matemáticas] es 1 mod [matemáticas] p [/ matemáticas ]

Según el pequeño teorema de Fermat, podemos decir que [matemáticas] 3 ^ {5 – 1} = 3 ^ 4 [/ matemáticas] es 1 mod 5.
Entonces, cuando elevamos [matemáticas] 3 ^ 4 [/ matemáticas] a la potencia 75, obtenemos que [matemáticas] 3 ^ {300} [/ matemáticas] es 1 mod 5.
Multiplicando por [matemáticas] 3 ^ 2 [/ matemáticas], tenemos que [matemáticas] 3 ^ {302} [/ matemáticas] es [matemáticas] 3 ^ 2 = 9 [/ matemáticas] mod 5.

De manera similar, procedemos a calcular el mod 7:
Según el pequeño teorema de Fermat, podemos decir que [matemáticas] 3 ^ {7 – 1} = 3 ^ 6 [/ matemáticas] es 1 mod 7.
Entonces, cuando elevamos [matemáticas] 3 ^ 6 [/ matemáticas] a la potencia número 50, obtenemos que [matemáticas] 3 ^ {300} [/ matemáticas] es 1 mod 7.
Multiplicando por [matemáticas] 3 ^ 2 [/ matemáticas], tenemos que [matemáticas] 3 ^ {302} [/ matemáticas] es [matemáticas] 3 ^ 2 = 9 [/ matemáticas] mod 7.

Entonces, [math] 3 ^ {302} [/ math] es un número que es 9 mod 5 y 9 mod 7.
Según el teorema del resto chino, hay un residuo único de [math] 3 ^ {302} [/ math] mod 35. Dado que es 9 mod 5 y 9 mod 7, obviamente debe ser 9 mod 35.

Answer 2

No podemos usar el Teorema de Fermat aquí ya que el d ivisor no es un número primo . Sin embargo, podemos aplicar su teorema principal, es decir, el teorema de Euler .

Método 1: teorema de Euler

TEOREMA DE EULER por Sarthak Dash en RESTANTES

Ahora, ø (35) = 35 * (1 – 1/5) * (1 – 1/7) = 4 * 6 = 24

Entonces, usando el teorema de Euler,

• [matemáticas] R [\ dfrac {3 ^ {24}} {35}] = 1 [/ matemáticas].
• Además, [matemáticas] R [\ dfrac {3 ^ {24k}} {35}] = 1 [/ matemáticas]

Entonces, [matemáticas] R [\ dfrac {3 ^ {302}} {35}] = R [\ dfrac {3 ^ {14} \ veces 3 ^ {288}} {35}] [/ matemáticas]

[matemáticas] = R [\ dfrac {3 ^ {14}} {35}] \ veces 1 [/ matemáticas]

[matemáticas] = R [\ dfrac {3 ^ 6 \ veces 3 ^ 6 \ veces 3 ^ 2} {35}] [/ matemáticas]

[matemáticas] = R [\ dfrac {729 \ veces 729 \ veces 9} {35}] [/ matemáticas]

[matemáticas] = R [\ dfrac {(-1) \ veces (-1) \ veces 9} {35}] [/ matemáticas]

[matemáticas] = R [\ dfrac {9} {35}] [/ matemáticas]

= 9 ( respuesta )

Método 2: Teorema del resto chino

TEOREMA CHINO DEL RESTANTE por Sarthak Dash en RESTANTES

Paso 1: [matemáticas] N = 35 = 5 \ veces 7 [/ matemáticas]

Paso 2: [matemáticas] R [\ dfrac {3 ^ {302}} {5}] = R [\ dfrac {3 ^ 2 \ times 3 ^ {300}} {5}] = R [\ dfrac {3 ^ 2} {5}] \ times R [\ dfrac {3 ^ {4 \ times 75}} {5}] = 4 \ times 1 [/ math] = 4

Paso 3: [matemáticas] R [\ dfrac {3 ^ {302}} {7}] = R [\ dfrac {3 ^ 2 \ times 3 ^ {300}} {7}] = R [\ dfrac {3 ^ 2} {7}] \ veces R [\ dfrac {3 ^ {6 \ veces 50}} {7}] = 2 \ veces 1 [/ matemáticas] = 2

Paso 4: [matemáticas] R [\ dfrac {3 ^ {302}} {35}] = 5 \ veces 2 \ veces X + 7 \ veces 4 \ veces Y = 10X + 28Y [/ matemáticas]

Paso 5: [matemática] 5X + 7Y = 1, [/ matemática] O [matemática] X = 3 [/ matemática] y [matemática] Y = (-2) [/ matemática]

Entonces, [matemáticas] R [\ dfrac {3 ^ {302}} {35}] = 10 \ veces 3 + 28 \ veces (-2) = ([/ matemáticas] – 26) o 9 ( Respuesta )