Foros de matemática

Matemática => Esquemas de demostración - Inducción => Mensaje iniciado por: mathspirit en 18/06/2017, 09:14:21 pm



Título: Prueba de divisibilidad por Fermat
Publicado por: mathspirit en 18/06/2017, 09:14:21 pm
Hola! Me pidieron probar que para todo a en Enteros vale:

[texx]728 | a^{27} - a^3[/texx]

Empecé la prueba y creo que tengo casi todo, sólo me falta ver que [texx]91 | a^{27} - a^3[/texx]

En teoría tendría que usar Fermat (creo), pero no se me ocurre muy bien cómo hacer ya que Fermat sólo dice:

[texx]a^{91} \equiv{a} (mod 91)[/texx] y [texx]a^{90} \equiv{1} (mod 91)[/texx] (esto último porque a es coprimo con 91)

Y los exponentes de la proposición a probar son mucho menores.


Título: Re: Prueba de divisibilidad por Fermat
Publicado por: robinlambada en 18/06/2017, 10:21:51 pm
Hola:
Hola! Me pidieron probar que para todo a en Enteros vale:

[texx]728 | a^{27} - a^3[/texx]

Empecé la prueba y creo que tengo casi todo, sólo me falta ver que [texx]91 | a^{27} - a^3[/texx]

En teoría tendría que usar Fermat (creo), pero no se me ocurre muy bien cómo hacer ya que Fermat sólo dice:

[texx]a^{91} \equiv{a} (mod 91)[/texx] y [texx]a^{90} \equiv{1} (mod 91)[/texx] (esto último porque a es coprimo con 91)

Y los exponentes de la proposición a probar son mucho menores.
¿Has probado a factorizar?
[texx]2^3\cdot{}91\cdot{}k=a^3(a^{24}-1)[/texx]

Saludos.


Título: Re: Prueba de divisibilidad por Fermat
Publicado por: Ignacio Larrosa en 19/06/2017, 05:37:47 am
Hola! Me pidieron probar que para todo a en Enteros vale:

[texx]728 | a^{27} - a^3[/texx]

Empecé la prueba y creo que tengo casi todo, sólo me falta ver que [texx]91 | a^{27} - a^3[/texx]

En teoría tendría que usar Fermat (creo), pero no se me ocurre muy bien cómo hacer ya que Fermat sólo dice:

[texx]a^{91} \equiv{a} (mod 91)[/texx] y [texx]a^{90} \equiv{1} (mod 91)[/texx] (esto último porque a es coprimo con 91)

Y los exponentes de la proposición a probar son mucho menores.

Ojo que el teorema de Fermat es para números primos:

[texx]p\textrm{ primo y mcd}(a, p) = 1\;\Longrightarrow{} a^{p-1} \equiv{} 1\textrm{ (mod }p)[/texx]

El que vale para módulos compuestos es el teorema de Euler-Fermat, que tal y como te puse en este otro mensaje Hallar resto de división mas rápidamente (http://rinconmatematico.com/foros/index.php?topic=96300.msg387205#msg387205) nos dice que:

[texx]{mcd}(a, m) = 1\;\Longrightarrow{} a^{\varphi(m)} \equiv{} 1\textrm{ (mod }m)[/texx]

Pero [texx]91 = 7\cdot{}13\textrm{ y }\varphi(91)=\varphi(7)\varphi(13)=6\cdot{}12=72[/texx]

Supongo que redujiste el problema a comprobar la divisibilidad por [texx]91[/texx] porque descompusiste [texx]a^{27} - a^3 = a^3(a^{24}-1)[/texx]y razonaste que si [texx]a[/texx] es par el primer factor es múltiplo de [texx]8[/texx], y si es impar lo es el segundo, pues el cuadrado de un impar siempre es igual a [texx]1\textrm{ (mod }8)[/texx]. Pues se trata de ir un paso más allá y ver que es divisible por [texx]91[/texx] si y solo si lo es por [texx]7\textrm{ y por }13[/texx]. Para ello puedes aplicar el teorema de Fermat con módulos [texx]7\textrm{ y }13[/texx], que si que son primos.

[texx]91[/texx] es el único compuesto no cuadrado y menor que [texx]100[/texx] que no es divisible por [texx]2, 3, 5\textrm{ u }11[/texx], lo que hace que frecuentemente se le tome por primo ...

Saludos,


Título: Re: Prueba de divisibilidad por Fermat
Publicado por: mathspirit en 24/06/2017, 04:01:44 pm
[texx]728 | a^{27} - a^3[/texx]

[texx][/texx]
Supongo que redujiste el problema a comprobar la divisibilidad por [texx]91[/texx] porque descompusiste [texx]a^{27} - a^3 = a^3(a^{24}-1)[/texx]y razonaste que si [texx]a[/texx] es par el primer factor es múltiplo de [texx]8[/texx], y si es impar lo es el segundo, pues el cuadrado de un impar siempre es igual a [texx]1\textrm{ (mod }8)[/texx]. Pues se trata de ir un paso más allá y ver que es divisible por [texx]91[/texx] si y solo si lo es por [texx]7\textrm{ y por }13[/texx]. Para ello puedes aplicar el teorema de Fermat con módulos [texx]7\textrm{ y }13[/texx], que si que son primos.
Saludos,

Muchas gracias! Si, lo reduje a comprobar por 91 por lo que comentás, pero igual creo que lo había hecho medio mal. Reduzco el ejercicio en comprobar (1) que [texx]2^3 | a^{27} - a^3[/texx], (2) que [texx]7 | a^{27} - a^3[/texx] y (3) [texx]13 | a^{27} - a^3[/texx]. Esto sólo es posible porque estos factores son coprimos entre si.

(1)

En este caso me di cuenta que lo hice mal, cómo se comprueba que el cuadrado de un impar siempre da resto 1 módulo 8?

(2)


[texx]\varphi(7) = 6 => a^6 \equiv{1} (mod7)[/texx] si a coprimo con 7 (si no lo es, a al cubo sería múltiplo de 7 => [texx]7 | a^3(a^{24} - 1)[/texx]).

[texx]=> (a^6)^4 \equiv{1} (mod7) => a^{24} \equiv{1} (mod7) => 7 | a^{24} - 1[/texx]

El (3) sale de forma idéntica a (2).


Título: Re: Prueba de divisibilidad por Fermat
Publicado por: Ignacio Larrosa en 24/06/2017, 08:40:58 pm

cómo se comprueba que el cuadrado de un impar siempre da resto 1 módulo 8?


Directamente. Todos los impares son iguales a [texx]1, 3, 5\textrm{ o }7\textrm{ mod }8[/texx]. Entonces,

[texx]1^2 = 1 \equiv{} 1 \textrm{ mod }8[/texx]

[texx]3^2 = 9  \equiv{} 1 \textrm{ mod }8[/texx]

[texx]5^2 = 25  \equiv{} 1 \textrm{ mod }8[/texx]

[texx]7^2 = 49  \equiv{} 1 \textrm{ mod }8[/texx]

O bien:

[texx](2k + 1)^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1 \equiv{} 1 \textrm{ mod }8[/texx]

puesto que o bien [texx]k\textrm{ o bien }(k +1)[/texx] es par.

Saludos,





Título: Re: Prueba de divisibilidad por Fermat
Publicado por: mathspirit en 25/06/2017, 07:47:41 pm
Genial, me quedó claro, gracias!