Hola, Gulgo. Perdona que sólo te dijera eso, tengo la sensación de haberte dejado un poco como colgado; es que ando en otras cosas y, ahora mirando, he visto que si uno busca por “inverso multiplicativo” salen muchos problemas de fracciones y aspectos así; poco sobre esta cuestión. Busca mejor por recíproco modular o inverso modular.
Te pongo yo algunos enlaces relacionados:
http://rinconmatematico.com/foros/index.php?topic=26742.0http://rinconmatematico.com/foros/index.php?topic=7039.0 por qué se halla como se halla.
Aquí he supuesto que te refieres a entender el algoritmo de Euclides, porque imagino que no habrás visto aún la phi de Euler y, por otro lado, haciéndolo por tanteo supongo que sí lo entiendes; es algo evidente:
Si tienes la congruencia, por ejemplo, \( 3k\equiv1\,(mod\:13) \), simplemente se trata de buscar un valor para “k” tal que multiplicado por 3 sobrepase en una unidad a un múltiplo de 13; entonces piensas en los números que hay justo “detrás” de los múltiplos de 3 mirando a ver cuál es múltiplo de 13. Así, tienes que el anterior a 27 es 26, \( 2\cdot 13 \) y 27 es múltiplo de 3, es \( 3\cdot 9 \), luego con “k=9” tenemos resuelta la congruencia.
Lo podemos representar como un ecuación:
\( 3k-13m=1 \)
Así que k=9 y m=2 es una solución.
Como también es bastante claro, si los números no son coprimos, el resto no puede ser 1; por ejemplo, no puede haber dos pares a distancia de una unidad; y, en general, no puede haber dos múltiplos de un primo “p” separados por una distancia menor que “p” (luego el resto no puede ser menor en ese caso y así no puede ser 1).
…
En cuanto al algoritmo de Euclides, pese a que parezca una tanda de divisiones donde nadie sabe por qué se hace eso, no es así, es verdaderamente fácil de entender y visualizar:
Si tienes una regla pequeña y quieres medir un tablero, vas poniendo la regla sobre la mesa; una, dos, tres veces... hasta que ves que falta un trozo y no va a caber entera, sólo va a caber una parte de ella ¿Podremos medir la mesa con números naturales? De antemano no, primero tiene que darse una circunstancia, que tanto la regla como la mesa se puedan medir de forma exacta con una pieza más pequeña a la que llamamos unidad. Si no, a la mesa le podría sobrar siempre un resto no entero respecto de la regla; y eso no es un resto a tenor de su definición. Dicho más matemáticamente, significa que el mcd tiene que existir siempre y no puede ser menor que 1 (los números naturales son naturales porque al menos existen unos seres naturales llamados humanos que definen la unidad).
Una vez que tenemos unidad, medimos; y supongamos que falta un trozo de regla o, lo que es decir lo mismo, sobra un resto de mesa (si no falta, el resto es cero y ya está).
Lo que falta será siempre menor que la regla; es obvio, no necesita más demostración.
Si después de haber medido la primera vez, volvemos a medir con el trozo de regla que ha faltado (con esa medida) quizá pueda volvernos a faltar algo, pero siempre será menor que el trozo con que estamos midiendo; una vez más, no necesita mayor demostración para ser aceptado.
Así, si hubiera faltado un trozo, podemos repetir lo mismo midiendo con ese nuevo trozo más pequeño; y, si vuelve a faltar, tendrá que ser más pequeño que antes.
Finalmente, encontraremos un trozo que medirá con exactitud la mesa (y medirá también la regla exactamente, puesto que tomamos porciones de regla, claro) como poco será 1, puesto que ambas cosas, regla y mesa, se pueden medir en unidades (bueno, como poco será cero, pero con cero no se puede medir).
Si no es 1, es otro divisor común de la mesa y la regla; y será el divisor mayor, el trozo de regla más grande capaz de medir con exactitud la ambas cosas, puesto que es el primero que encontramos en ese proceso donde tomamos cada vez trozos más pequeños.
Una vez más, quede claro que esos trozos de regla que faltan según se van haciendo las mediciones, son, análogamente, los trozos de mesa (
o regla) que sobran respecto de la regla; los restos, literalmente hablando.
Se me ha olvidado señalar que la segunda, tercera vez, etc (si existieran) que se mide, no sería la mesa, sino la otra parte que ha quedado de regla, el divisorY esto es el algoritmo de Euclides.
*He intentado no equivocarme al decir las cosas, no obstante, si ves que digo algo que te extraña, dímelo por si fuera un despiste.
Saludos.
