1r ciclo Problema Aritmetica

[zhazzu]

Necesito ayuda con este ejercicio:
En clase nos han explicado toda la teoria y es extremadamente abstracta. El hecho es que al intentar hacer ejercicios con numeros me pierdo. Tengo una lista de ejercicios para practicar. Alguien podria indicarme como resolver este ejercicio de la lista

'' Calcula 3⁶⁴ mod 67 usando el pequeño Teorema de Fermat. ''

La idea es que una vez sepa hacer este intentaré hacer los otros de la lista ya que son similares.

Luego, también me pasa lo mismo pero con ejercicios del siguiente tipo:

'' Encuentra todos los numeros naturales acabados en 4 tales que su doble sea congruente con 1 modulo 3 i su triple congruente con 2 modulo 7. Y comprueba que la respuesta es correcta. ''

Gracias de antemano !!

[Weip]

Re: Problema Aritmetica

'' Calcula 3⁶⁴ mod 67 usando el pequeño Teorema de Fermat. ''

El pequeño teorema de Fermat te dice que si $a$ entero positivo y $p$ primo que no divide a $a$ entonces $a^{p-1} \equiv 1 (\text{mod} p)$. Si lo aplicas a tu problema tienes que $3^{66} \equiv 1 (\text{mod} 67)$ (comprueba las hipótesis). ¿Sabrías acabarlo? La respuesta es $15$. La clave de todo esto es pensar los enteros módulo $n$ como un reloj o como los días de la semana. Cuando llegues al final, sigue contando desde el principio. Por ejemplo en los enteros módulo $4$ pues $2+2\equiv 0$, $1+5\equiv 2$, etc.

[zhazzu]

Re: Problema Aritmetica

El ultimo ejemplo que me has dado si lo entiendo(lo del reloj). Pero no se como aplicarlo al problema para solucionarlo. No sabria muy bien como resolverlo. Es decir, tendria que aplicar lo del reloj a 3^66 = 1 (siendo el modulo 67) ? Si es asi, no se como resolverlo

Y a que te refieres con comprobar la hipotesis ?

[Weip]

Re: Problema Aritmetica

Y a que te refieres con completar la hipotesis ?

El pequeño teorema de Fermat tiene dos hipótesis: $p$ primo y que $p$ no divide a $a$. En tu caso $p=67$ y $a=3$. Es una pequeña comprobación, pero hazla. Sino te quitarán puntos.

Respecto al problema, siguiendo el anterior razonamiento, $3^{66}=3^2 3^{64} \equiv 1 (\text{mod}67)$. Llama $x=3^{64}$ (es lo que quieres encontrar). Por definición de congruencia, existe un $k$ entero tal que $9x-67k=1$. Y para $k=2$, $x=$...

El ultimo ejemplo que me has dado si lo entiendo(lo del reloj). Pero no se como aplicarlo al problema para solucionarlo. No sabria muy bien como resolverlo. Es decir, tendria que aplicar lo del reloj a 1 mod 67 ?

Lo del reloj era para que visualizaras todo lo que te están contando, como decías que era muy abstracto pues se me ha ocurrido ese símil.

[zhazzu]

Re: Problema Aritmetica

Lo que me sigue quedando dudoso es lo de la comprobacion. Que debo de hacer ? Sustituir p=67 y a=3 en la hipotesis y luego...? Y en la parte final, porque k=2 ?

Estoy seguro de que al final todo esto es una tonteria pero ahora no acabo de verlo. Tipico momento que cuanto mas quieres entender mas te lias.

- - - Actualizado - - -

A ver, esta solucion estaria bien ?

-Por el pequeño teorema de Fermat sabemos que 3^66 congruente con 1(mod 67).
Entonces 3^66 = 3^64*3^2. Ya que 3^66 es 1 mod 67, entonces 3^64 y 3^2 deben de ser inversos uno del otro mod 67. Asi que para buscar la clase de 3^64 mod 67, necesitamos buscar la clase que es la inversa de 3 mod 67 y elevarla al cuadrado. Para encontrar la inversa de 3 mod 67, necesitamos resolver la ecuacion siguiente: 3x + 67y = 1 (resolvemos por el algoritmo de euclides y nos da y = -22). Asi que -22 es inverso de 3 mod 67 y -22 mod 67 es lo mismo que -22 mod 45.
De nuestros calculos anteriores, sabemos que el cuadrado de 45 mod 67 será congruente con 3^64 mod 67. Asi que el ultimo paso es elevar al cuadrado 45 y determinar su clase mod 67.
Finalmente tenemos 45^2 = 2025 y esto es congruente con 15 mod 67. Por tanto 2^64 = 15 mod 67.
El resultado que buscabamos es 15

Bueno, veis algun error o algo que pueda mejorarse o escribirse mejor ?

[Weip]

Re: Problema Aritmetica

Lo que me sigue quedando dudoso es lo de la comprobacion. Que debo de hacer ? Sustituir p=67 y a=3 en la hipotesis y luego...?

Empieza el texto diciendo "observamos que 67 es primo y que no divide a 3, por lo tanto podemos aplicar el pequeño teorema de Fermat" porque si pones "por el pequeño teorema de Fermat" directamente estás aplicando un teorema sin saber si las hipótesis son ciertas en tu caso particular.

Y en la parte final, porque k=2 ?

Si coges otro $k$ fíjate que o bien el resultado no es entero o bien el resultado es congruente con 15. Pongo ejemplos concretos. $k=3$ te da $x=202/9$ con lo que no es solución. $k=11$ te da $x=82$, congruente con 15 modulo 67.

-Por el pequeño teorema de Fermat sabemos que 3^66 congruente con 1(mod 67).

Lo dicho, di primero que 67 es primo y que no divide a 3. Luego aplica el teorema.

(resolvemos por el algoritmo de euclides y nos da y = -22). Asi que -22 es inverso de 3 mod 67 y -22 mod 67 es lo mismo que -22 mod 45.

No digas -22 porque los elementos de $\mathbb{Z}/67 \mathbb{Z}$ son clases de equivalencia. Di a qué número es congruente: usando la analogía del reloj, 67-22=45. Por otro lado -22 es 23 modulo 45 así que $-22 (\text{mod }67)$ es diferente a $-22 (\text{mod} 45)$.

De nuestros calculos anteriores, sabemos que el cuadrado de 45 mod 67 será congruente con 3^64 mod 67.

Esto no acabo de entender de donde sale. Según has descrito anteriormente el procedimiento sería hacer $22^2$, que es 15 modulo 67.

Por tanto 2^64 = 15 mod 67.

Ahí va un 3. Es un lapsus pero lo digo por si lo has escrito en el papel.

Por lo demás lo veo bien. En el otro ejercicio no me atrevo a dar detalles porque tengo esto muy oxidado pero prueba a pasar las congruencias a un sistema de ecuaciones y resuélvelo.

[zhazzu]

Re: Problema Aritmetica

Tengo otra duda. Esta vez no es referente a problemas para practicar. Simplemente es curiosidad.

Demostrar que si a es congruente con b(mod n), entonces mcd(a,n) = mcd(b,n)

[angel relativamente]

Re: Problema Aritmetica

¿Sabrías ver que $mcd(a,n)=mcd(kn+a,n)$, con $k\in \mathbb{Z}$?
Si ves eso observa que si a es congruente con b módulo n es equivalente a que $b=a+kn, \; k \in \mathbb{Z}$

PD: Te demuestro lo primero, pero te invito a que lo hagas tú solo antes.
Sea $d=mcd(a,n)$. En particular, $d$ divide a $a$ y a $n$. Veamos que $d=mcd(a+kn,n)$. En primer lugar vemos que es divisor: Es trivial porque $d$ divide a $a+kn$ debido a que divide a $a$ y a $n$. Veamos que, de todos los divisores, es el máximo. Lo haremos por reducción al absurdo. Sea $d'$ un divisor común de $a+kn$ y de $n$ tal que $d'>d$. Como $d'$ divide a $n$, entonces divide a $kn$ y por tanto ha de dividir a $a$. Tenemos pues que $d'$ divide a $a$ y a $n$ y además $d'>d$, lo cual es un absurdo pues $d=mcd(a,n) \; \square$

[zhazzu]

Re: Problema Aritmetica

Todo lo escrito lo he entendido perfectamente. Eso es una demostracion a medias donde me invitas a acabarla o ya esta acabada ? Lo digo porque yo la veo completa.

Es decir, esto: a es congruente con b módulo n es equivalente a que es lo que nos ha permitido llegar a ver que mcd(a,n) = mcd(b,n). No estaria ya todo demostrardo entonces ?

[angel relativamente]

Re: Problema Aritmetica

Correcto, lo que he puesto después de la PD completa la demostración. Lo que te invitaba es a que la completases tú solo antes de leer la PD