¿Cuál es el resto cuando [matemáticas] 11 ^ {35} [/ matemáticas] se divide por [matemáticas] 13 [/ matemáticas]?

Answer 1

[matemáticas] 6 [/ matemáticas]

Usa el pequeño teorema de Fermat. Establece que para cualquier primer p,

[matemáticas] a ^ {(p-1)} = 1 [/ matemáticas] mod p

Aquí [matemáticas] 13 [/ matemáticas] es un número primo. Entonces, usando el teorema obtendremos

[matemáticas] 11 ^ {12} = 1 [/ matemáticas] mod [matemáticas] 13 [/ matemáticas]

[matemáticas] => 11 ^ {24} = 1 [/ matemáticas] mod 13

Ahora, [matemáticas] 11 ^ {35} [/ matemáticas] mod 13 [matemáticas] = 11 ^ {24} * 11 ^ {11} [/ matemáticas] mod 13

Entonces, necesitamos encontrar [math] 11 ^ {11} [/ math] mod 13

[matemáticas] 11 = -2 [/ matemáticas] mod 13

[matemáticas] => 11 ^ 2 = 4 [/ matemáticas] mod 13

[matemáticas] => 11 ^ 4 = 4 * 4 [/ matemáticas] mod 13 [matemáticas] = 3 [/ matemáticas] mod 13

[matemáticas] => 11 ^ 8 = 9 [/ matemáticas] mod 13

[matemáticas] 11 ^ 3 [/ matemáticas] mod 13 [matemáticas] = 11 ^ 2 * 11 [/ matemáticas] mod 13

[matemática] => 4 * (-2) [/ matemática] mod 13 [matemática] = -8 [/ matemática] mod 13 [matemática] = 5 [/ matemática] mod 13

[matemáticas] => 11 ^ {11} = 9 * 5 [/ matemáticas] mod 13 [matemáticas] = 45 [/ matemáticas] mod 13

[matemáticas] => 11 ^ {11} = 6 [/ matemáticas] mod 13

Ahora,

[matemáticas] 11 ^ {35} = 1 * 6 [/ matemáticas] mod 13 [matemáticas]. [/matemáticas]

[matemáticas] => 11 ^ {35} = 6 [/ matemáticas] mod 13 [matemáticas] [/ matemáticas]

Espero que ayude. 🙂

Answer 2

¡Emocionado! ¡Me acabo de enseñar la teoría de números recientemente!

Considere el resto de la tormenta,

11 ^ 35 = 11 * 11 ^ 34 = 11 * 121 ^ 17

121 = 4 (mod 13)

121 ^ 17 = 4 ^ 17 (mod 13)

4 ^ 17 = 4 * 4 ^ 16 = 4 * 256 ^ 4

256 = 9 (mod 13)

256 ^ 4 = 9 ^ 4 = 81 ^ 2 (mod 13)

81 = 3 (mod 13)

Por lo tanto 256 ^ 4 = 3 ^ 2 (mod 13)

121 ^ 17 = 4 ^ 17 = 4 * 256 ^ 4 = 4 * 3 ^ 2 = 36 (mod 13) = 10

Por lo tanto, 11 ^ 35 = 11 * 121 ^ 17 = 11 * 10 = 110 (mod 13) = 6

¡Hecho!

Answer 3

Tengo una solución muy fácil para esta difícil pregunta.

Antes de pasar a la pregunta, piense que debería echar un vistazo al teorema de Euler para el resto – Cómo encontrar el resto – 1 – Teorema de Euler

Ahora resolvamos la pregunta

= 11 ^ 35/13

Debido a que 11 y 13 son primos, podemos usar el teorema de Euler en él, por lo tanto, para cada potencia de 13 * (1-1 / 13) = 13 * (12/13) = 12 de cualquier número dividido por 13 producirá el resto 1 así

= (11 ^ 12) ^ 2 * 11 ^ 11/13

= 1 * 11 ^ 11/13

= (11 ^ 2) ^ 5 * 11/13

= (121) ^ 5 * 11/13

= 4 ^ 5 * 11/13

= (4 ^ 2) ^ 2 * 4 * 11/13

= (16) ^ 2 * 44/13

= 3 ^ 2 * 5/13

= 45/13

= 6

por lo tanto, el resto será 6

Answer 4

11 ^ 35 = (13-2) ^ 35

(13-2) ^ 35 = 13 ^ 35 + 35C1 [13 ^ 34 (-2)] +… + 35C34 [13 (-2) ^ 34] + (-2) ^ 35

En la expansión en el lado derecho, solo el último término no es divisible por 13, porque no tiene un factor 13.

(-2) ^ 35 = [(-1) ^ 35] [2 ^ 35]

2 ^ 35/13 = 2643056797 con 7 restantes!

Entonces el resto es 7.

Answer 5

Usando el pequeño teorema de Fermats

[matemáticas] 11 ^ {36} \ mod 13 = 1 [/ matemáticas]

[matemáticas] (11 ^ {35} * 11) \ mod 13 = 1 [/ matemáticas]
[matemáticas] [(11 ^ {35} \ mod 13) * (11 \ mod 13)] \ mod 13 = 1 [/ matemáticas]

Deje [math] x [/ math] = [math] 11 ^ {35} \ mod 13 [/ math]
[matemáticas] [x * (- 2)] \ mod 13 = 1 [/ matemáticas]
[matemáticas] x = -7 [/ matemáticas]

Entonces, [matemáticas] 11 ^ {35} \ mod 13 = -7 [/ matemáticas]
o, [matemáticas] 11 ^ {35} \ mod 13 = 13-7 = 6 [/ matemáticas]

6, la respuesta

Answer 6

No estoy seguro si tengo algo nuevo que agregar a las respuestas existentes [matemáticas] 19 [/ matemáticas] , y sobre un tema ya he respondido varias veces .

Del teorema de Fermat [matemática] “[/ matemática] pequeña [matemática]” [/ matemática], para primo [matemática] p [/ matemática] y cualquier número entero [matemático] a [/ matemático] para el cual [matemático] p \ nmid a [/ math], tenemos [math] p \ mid (a ^ {p-1} -1) [/ math].

Aplicando esto a [matemáticas] p = 13 [/ matemáticas], [matemáticas] a = 11 [/ matemáticas], tenemos [matemáticas] 11 ^ {36} = \ big (11 ^ {12} \ big) ^ 3 \ equiv 1 \ pmod {13} [/ matemáticas]. Multiplicar ambos lados de la congruencia por [matemáticas] 6 [/ matemáticas] da

[matemáticas] 6 \ equiv 6 \ cdot 11 ^ {36} = \ big (6 \ cdot 11 \ big) \ cdot 11 ^ {35} \ equiv 11 ^ {35} \ pmod {13} [/ math]. [matemáticas] \ blacksquare [/ matemáticas]

Answer 7

Todas las respuestas con el resultado 6 son correctas e inteligentes.

Lo siguiente es solo para verificar la respuesta.

---

Se puede verificar rápidamente. Una sola línea de comando en su computadora puede hacerlo para cualquier pregunta como esta. ¿Cuál es el resto de x dividido por y incluso para un número muy grande? Aquí están algunos ejemplos:

$ python -c “print 11 ** 35% 13”

6 6

$ python -c “print 11 ** 3500% 13”

9

$ python -c “print 11 ** 3500000% 13”

9

Hice esto en mi computadora, toma 0.02 segundos para 11 ** 35% 13 (el resto cuando 11 ^ 35 se divide 13), 2 segundos para hacer 11 ** 3500000% 13. Si el número es realmente demasiado grande, necesita una computadora realmente poderosa.

Esto se debe a que Python admite aritmética de precisión arbitraria. Perl, Ruby y Haskell también pueden hacer esto.

Answer 8

= [matemáticas] (- 2) ^ {6 * 5 + 5} [/ matemáticas]

= [matemáticas] (- 1) ^ {5} [/ matemáticas] * [matemáticas] (- 2) ^ {5} [/ matemáticas]

= 32, = 6

Necesito dar más explicaciones, para ser más útil.

Pensando en cómo hacerlo.

El resto cuando [math] A ^ {B} [/ math] se divide por C por Jyoti Charan en jyoticharan

Answer 9

11 mod 13 = -2. Entonces 11 ^ 8 mod 13 = (-2) ^ 8 mod 13 = -4. También del teorema de Fermat obtenemos 11 ^ 24 mod 13 = 1.

Entonces 11 ^ 32 mod 13 = 1 x -4 = -4. También 11 ^ 3 mod 13 = (- 2) ^ 3 mod 13 = 5. Entonces 11 ^ 35 mod 13 = -4 x 5 = -20 mod 13 = 6. Gracias.

Answer 10

Según el pequeño teorema de Fermat

[matemáticas] a ^ {p-1} \ equiv 1 \ mod p [/ matemáticas]

Entonces, podemos escribir

[matemáticas] 11 ^ {12} \ equiv 1 \ mod 13 [/ matemáticas]

[matemáticas] \ implica 11 ^ {24} \ equiv 1 \ mod 13 [/ matemáticas]

Requerimos [matemáticas] 11 ^ {11} \ mod 13 [/ matemáticas]

[matemáticas] 11 \ equiv -2 \ mod 13 [/ matemáticas]

[matemáticas] \ implica 11 ^ 2 \ equiv 4 \ mod 13 [/ matemáticas]

[matemáticas] \ implica 11 ^ 4 \ equiv 3 \ mod 13 [/ matemáticas]

[matemáticas] \ implica 11 ^ 8 \ equiv 9 \ mod 13 [/ matemáticas]

---

[matemáticas] 11 ^ 3 \ equiv -8 \ mod 13 [/ matemáticas]

[matemáticas] \ implica 11 ^ 3 \ equiv 5 \ mod 13 [/ matemáticas]

---

Multiplica los resultados para obtener

[matemáticas] 11 ^ {11} \ equiv 45 \ mod 13 [/ matemáticas]

[matemáticas] \ implica 11 ^ {11} \ equiv 6 \ mod 13 [/ matemáticas]

Ahora multiplique este resultado con el resultado obtenido usando el pequeño teorema de Fermat

[matemáticas] \ en caja {11 ^ {35} \ equiv 6 \ mod 13} \ tag {} [/ matemáticas]

Answer 11

11 ^ 35/13
Euler de 13 es 12
Entonces
(a ^ 12) ^ n / 13 = 1 resto
11 ^ 35/13
Ahora
11 ^ 36/13 = 1
11 ^ 35 * 11/13 = 1
R * 11 = 13k +1
R = 13k +1/11
K sea cualquier valor que divida perfectamente esto
Deje k ser 5
R = 13 (5) +1/11
R = 6
Entonces el resto es 6

Answer 12

11 ^ 35 mod 13 = -2 ^ 35 = 2 ^ 32 * (- 8) = (2 ^ 4) ^ 8 * (- 8) = 3 ^ 8 * (- 8) = 9 ^ 4 * (- 8) = (-4) ^ 4 * (- 8) = 16 ^ 2 * (- 8) = 3 ^ 2 * (- 8) = -72 = 6

Ni siquiera usé un papel.

Answer 13

Así es como se calcula manualmente n ^ a% p. Es un algoritmo log2 (n) que una computadora puede calcular rápidamente incluso para números extremadamente grandes (n ^ 2048 número de bit% 2048 número de bit) es inferior a unos pocos milisegundos)

1 – 11

2 – 11 * 11% 13 = 4

4 – 4 * 4% 13 = 3

8 – 3 * 3% 13 = 9

16-9 * 9% 13 = 3

32 – 3 * 3% 13 = 9

f (32) * f (2) * f (1)% 13 = (9 * 4 * 11)% 13 = 6

Además, debido a que 35 factores son 5, 7, puede restar 24 [(n-1) (m-1) o (7-1) (5-1)] de 35 [35- (5-1) (7- 1)] = [35- (24)] = 11

f (11)% 13 = f (8) * f (2) * f (1)% 13 = (9 * 4 * 11)% 13 = 6

---

Answer 14

Lo más rápido: dado que 13 es primo, cualquier cosa a la potencia 12 es 1 mod 13, y 11 ^ 35 es, por lo tanto, 11 ^ (- 1). Para encontrar la nota recíproca de que 11 es -2 y podemos encontrar fácilmente -1/2 ya que -1 es 12: la respuesta es 6.

Answer 15

Muy simple, lo es. Usa las propiedades normales del módulo de congruencia. Y sí, has terminado tan rápido.

Answer 16

¿Por qué no usas el pequeño teorema de Fermat?