Foros de matemática
19/10/2017, 12:37:07 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de insercción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Prueba de divisibilidad por Fermat  (Leído 298 veces)
0 Usuarios y 1 Visitante están viendo este tema.
mathspirit
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 58


Ver Perfil
« : 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.
En línea
robinlambada
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 2.461


Ver Perfil
« Respuesta #1 : 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.
En línea

Envejecer es como escalar una gran montaña: mientras se sube las fuerzas disminuyen, pero la mirada es más libre, la vista más amplia y serena.

La verdadera juventud una vez alcanzada, nunca se pierde.
Ignacio Larrosa
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.383


Ver Perfil WWW
« Respuesta #2 : 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 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,
En línea

Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por mucho menos ...
mathspirit
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 58


Ver Perfil
« Respuesta #3 : 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).
En línea
Ignacio Larrosa
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.383


Ver Perfil WWW
« Respuesta #4 : 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,



En línea

Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por mucho menos ...
mathspirit
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 58


Ver Perfil
« Respuesta #5 : 25/06/2017, 07:47:41 pm »

Genial, me quedó claro, gracias!
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!