Hola, queria preguntar si alguien podria explicarme como obtener el resto de una division sin hacerla
Por ejemplo tengo 12^145 dividido 11 obtener el resto o 1599 dividido 39
Me gustaria que alguien me explicara con alguno de los dos ejemplos como hacerlo ya que vi algunos resueltos pero no logro encontrarle la logica.
hacé restas sucesivas =P
#include <stdio.h>
int main (){
int a = (12^145);
while (a > 11 ) a -= 11;
printf("%d", a);
return a;
}
muy gracioso, haciendolo bien xD y valido para matematica discreta...
Tenes que usar el "pequeño teorema de Fermat"
dice: si p es un numero primo, entonces \[a^p \equiv p(n)\]
o su otra version equivalente: \[a^{p-1} \equiv 1(n)\]
Hagamos el primer ejemplo usando la primera forma de la propiedad:
\[12^{145}\] dividido 11:
\[12^{145}\] es lo mismo que poner \[12^{143} * 12^{2}\] (por producto de potencias de igual base)
Ahora: el \[12^{143}\] lo podemos escribir como \[12^{13^{11}}\] porque potencia de potencia se multiplican. (fijate que lo descompuse en 143 y 2, porque 143 es multiplo de 11, y asi puedo formar el teorema del comienzo).
Por lo que la expresion nos quedaria:
\[12^{13^{11}} * 12^{2}\]
Usando el teorema, \[12^{13^{11}}\equiv 12^{13}(11)\]
Así que ahora nos quedaría:
\[12^{13} * 12^{2}\] que es igual a \[12^{15}\]
Pero a nosotros, que tenemos que buscar el 11 de exponente, nos va a convenir escribirlo como
\[12^{11} * 12^{4}\] que, por la propiedad, nos queda \[12 * 12^{4}\] que seria \[12^{5}\]
Ya no podemos aplicar más el metodo, porque el exponente es menor que 11, por lo que ese numero ya lo podes obtener con la calculadora y fijarte a qué clase residual módulo 11 pertenece, dividiendo por 11 y fijandote el resto. El numero que nos queda es 248832, que dividido 11 te queda de resto 1, esa es la respuesta.
Intentá hacerlo con la formula de abajo (la version equivalente), vas a llegar tambien y en general más rapido.
Te aclaresco un toque lo que dijo joni , que esta bien pero lo veo medio complicado.
Vos lo que tenes que buscar..es que
\[12^{145}\]\[\equiv 1\left ( 11 \right )\]
como vos ves tenes
\[12^{145}\]
tenes que buscar que te quede
\[12^{10 .por. algo. y./.o. .más .algo}\]
debido a que tenes que dividirlo por (11) y como dijo jony , el teorema de fermat dice p - 1
siendo P = (11) en este caso.
\[a^{P-1}\equiv 1(p)\]
en este caso podes hacerlo de la siguiente manera:
\[12^{10 . 14 + 5}\] que esto es igual a = \[12^{10.14} + 12^{5}\]
por el teorema de fermat tenemos que \[12^{10}\] es = 1
entonces queda
\[1^{14} + 12^{5}\] que esto es = \[12^{5}\]
entonces tenemos que el resto de \[12^{145}\] dividido por 11 es igual = al resto de \[12^{5}\] dividido por 11
\[R\left ( 12^{145},11 \right ) = R (12^{5},11)\]
entonces hacemos la division de \[12^{5}\] dividido 11 , y el resto que te de , es el resto de ambas.
en sintesis, siempre buscamos llegar a que el exponente se pueda expresar como N - 1 , siendo N el divisor, asi con el teorema de fermat, lo transformamos en un 1.
espero que se alla entendido! saludos.
Muchas gracias por ambas respuestas, en especial la de
Arkh les agradesco mucho!
claramente no vi ese tema en matemática discreta jajajajaj
(16-07-2012 23:07)Arkh escribió: [ -> ]Te aclaresco un toque lo que dijo joni , que esta bien pero lo veo medio complicado.
Vos lo que tenes que buscar..es que
\[12^{145}\]\[\equiv 1\left ( 11 \right )\]
como vos ves tenes
\[12^{145}\]
tenes que buscar que te quede
\[12^{10 .por. algo. y./.o. .más .algo}\]
debido a que tenes que dividirlo por (11) y como dijo jony , el teorema de fermat dice p - 1
siendo P = (11) en este caso.
\[a^{P-1}\equiv 1(p)\]
en este caso podes hacerlo de la siguiente manera:
\[12^{10 . 14 + 5}\] que esto es igual a = \[12^{10.14} + 12^{5}\]
por el teorema de fermat tenemos que \[12^{10}\] es = 1
entonces queda
\[1^{14} + 12^{5}\] que esto es = \[12^{5}\]
entonces tenemos que el resto de \[12^{145}\] dividido por 11 es igual = al resto de \[12^{5}\] dividido por 11
\[R\left ( 12^{145},11 \right ) = R (12^{5},11)\]
entonces hacemos la division de \[12^{5}\] dividido 11 , y el resto que te de , es el resto de ambas.
en sintesis, siempre buscamos llegar a que el exponente se pueda expresar como N - 1 , siendo N el divisor, asi con el teorema de fermat, lo transformamos en un 1.
espero que se alla entendido! saludos.
cuando pones esto....
\[12^{10 . 14 + 5}\] que esto es igual a = \[{\color{Red} 12^{10.14}{\color{Blue} +}12^{5}} \]
Estas aplicando alguna propiedad del teorema de fermat (no conozco bien) o es un error q se te paso, ya tendria q ser asi.....
\[12^{10 . 14 + 5}\] que esto es igual a = \[{\color{Red} 12^{10.14}{\color{Blue} . }12^{5}} \]
se me paso , es como vos decis , no es SUMA es multiplicacion , gracias por la correción!
chicos me darian una mano con este ejercicio a. Sin hacer la operación , calcular el resto en la división de 8^138 por 11. Lo hago como lo hacen ustedes pero me queda cosas rarisimas.
8^10.13 + 8
(1)^13 x 8^8
8^8 dividido 11 , y ahi tenes el resto.
\[8^{10.13+8}\]
aplicamos fermat
\[(1)^{13}+ 8^{8}\]
\[R(8^{138},11) = R(8^{8},11)\]
Una pregunta, no entiendo esta propiedad:
12^10 = 1. De dónde sale eso?
lee mi primer comentario , ahi esta explicado , es el teorema de fermat.
Jajaja, por eso, la duda la tengo desde tu comentario.
Escribiste el 10 como 11-1 no?
exacto (porque el teorema de fermat es lo de: a^(P-1) = 1(P)
en ese caso P era 11 , entonces
a^(11-1) = 1