Escuela Normal Superior “ALMAFUERTE” – I.S.F.D.
N° 106
Profesorado de Educación Secundaria en Matemática
Álgebra 3er Año – Prof.: Lic. Tatiana Benitez
Unidad 1 - DIVISIBILIDAD
Algunas demostraciones pendientes
1. Divisor común máximo
Teorema. Sean tales que o , entonces existe un único que
satisface:
i.
ii. | |
iii. Dado , si | y | entonces |
Demostración
Existencia.
Sea el conjunto * ⁄ +.
Si entonces pues , si entonces pues
( ) , entonces en cuyo caso o pertenecen a según
sea o .
Luego es un subconjunto no vacío de . Sea el primer elemento de (existe por el
principio de buena ordenación). Luego, y , para todo .
Debemos probar que satisface i., ii., iii.:
i. pues y
ii. Sean el cociente y el resto de la división de por . Luego , -
y . Queremos probar que .
Supongamos que no, es decir que . Entonces . Además, como
entonces , - con . Luego, de , - y , -:
( ) ( ) ( )
Y como y , entonces . Pero esto no puede ocurrir pues
debe ser y es el primer elemento de .
Por lo tanto, debe ser . Luego | .
Análogamente se determina que | .
Luego | y | .
iii. Sea tal que | y | .
Como entonces , con .
DIVISIBILIDAD 1
Escuela Normal Superior “ALMAFUERTE” – I.S.F.D. N° 106
Profesorado de Educación Secundaria en Matemática
Álgebra 3er Año – Prof.: Lic. Tatiana Benitez
Como | y | entonces divide a cualquier combinación lineal entera de y .
Por lo tanto, | .
Luego | .
Unicidad.
Supongamos que y son enteros que satisfacen i., ii., iii.
Como satisface ii.: | y | . Pero como verifica iii. esto implica que | . Y como
y satisfacen i. entonces . , -
Como satisface ii.: | y | . Pero como verifica iii. esto implica que | . Y como
y satisfacen i. entonces . , -
Luego, de , - y , -: .
2. Ecuaciones diofánticas lineales
Teorema: Condición suficiente
La condición suficiente para que la ecuación diofántica lineal tenga solución es que
los coeficientes sean coprimos.
Demostración
y son coprimos, luego ( ) . Entonces existen tales que .
Multiplicando miembro a miembro por :
( ) ( )
Llamando :
Luego, ( ) es solución.
3. Ecuaciones diofánticas lineales
Teorema. Sea una ecuación diofántica y ( ) una solución particular,
entonces toda solución ( ) está dada por las expresiones:
( ) ( )
( ) ( )
Demostración
DIVISIBILIDAD 2
Escuela Normal Superior “ALMAFUERTE” – I.S.F.D. N° 106
Profesorado de Educación Secundaria en Matemática
Álgebra 3er Año – Prof.: Lic. Tatiana Benitez
Si ( ) es solución particular de , verifica . De lo anterior
resulta:
( ) ( )
( ) ( )
Dividiendo miembro a miembro por ( ) tenemos
( ) ( ) , -
( ) ( )
Por definición de divisibilidad:
| ( )
( ) ( )
Pero, por propiedad:
( ) ( )
Además, por propiedad ( | y( ) entonces | ):
|( )
( )
Lo que implica que existe un tal que
( )
, -
( )
Sustituyendo , - en , -:
( ) [ ( ) ]
( ) ( ) ( )
( ) [ ]
( ) ( ) ( )
( )
( ) ( ) ( )
Multiplicando miembro a miembro por ( )
DIVISIBILIDAD 3
Escuela Normal Superior “ALMAFUERTE” – I.S.F.D. N° 106
Profesorado de Educación Secundaria en Matemática
Álgebra 3er Año – Prof.: Lic. Tatiana Benitez
( )
( )
( ) ( )
( )
( )
, -
( )
Luego, de , - y , -:
( ) ( )
( ) ( )
es solución de .
En general, si ( ) es solución de una ecuación diofántica lineal, las soluciones ( ) son de
la forma: ( ) ( ) con .
Verifico:
( ) ( )
( ) ( ) ( ) ( )
Teniendo en cuenta que ( ) es solución, entonces :
( ) ( )
Luego ( ) ( ), con , es solución.
4. Ecuaciones lineales de congruencia
Teorema: Condición necesaria y suficiente
La condición necesaria y suficiente para que la ecuación de congruencia ⌊ tenga
solución es que el divisor común máximo entre y sea también divisor de .
Demostración – Parte 1
“La ecuación de congruencia ⌊ tiene solución, entonces el divisor común máximo
entre y sea también divisor de .”
Dem.)
es solución de ⌊ , entonces ⌊
DIVISIBILIDAD 4
Escuela Normal Superior “ALMAFUERTE” – I.S.F.D. N° 106
Profesorado de Educación Secundaria en Matemática
Álgebra 3er Año – Prof.: Lic. Tatiana Benitez
Luego, existe tal que :
( )
Por otro lado, ( )| y ( )| entonces ( ) divide a cualquier combinación
lineal entera de y :
( )| ( )
Luego ( )| .
Demostración – Parte 2
Sea la ecuación de congruencia ⌊ . Si el divisor común máximo entre y es
también divisor de , entonces la ecuación ⌊ posee solución.”
Dem.)
( )| y ( )|
Luego, ( )
y( )
son coprimos y es combinación lineal entera de ellos, es decir,
existen tales que:
( ) ( )
Multiplicando miembro a miembro por :
( ) ( )
Además, ( ) es divisor de . Luego existe tal que ( ) :
( ) ( )
( ) ( )
( ( )) ( ( ))
( ) ( )
Donde y , con :
( )
Por definición de congruencia:
⌊
Luego, existe solución de ⌊ .
DIVISIBILIDAD 5
Escuela Normal Superior “ALMAFUERTE” – I.S.F.D. N° 106
Profesorado de Educación Secundaria en Matemática
Álgebra 3er Año – Prof.: Lic. Tatiana Benitez
5. Teorema Fundamental de la Aritmética
Teorema. Sea . Si entonces existen primos positivos tales que
Además, esta escritura es única, salvo en el orden de los factores.
Demostración
Si es primo, entonces y:
Si es compuesto, entonces tiene un divisor positivo tal que . Por el
principio del buen orden podemos suponer que es el menor de los divisores positivos de
. Entonces debe ser primo, de lo contrario tendría un divisor positivo mayor que uno
y menor que y que también es divisor de , y esto no puede ocurrir ya que es el menor
de los divisores positivos de .
Entonces existe tal que con primo y . Si es primo, queda
demostrado. Si no es primo, entonces existe primo y tales que
con .
Así, . Si es primo, queda demostrado. Si no es primo, se repite el
proceso, obteniendo una sucesión decreciente (finita) de números .
Entonces, después de un número finito de pasos tenemos que:
Para probar que la expresión obtenida es única, salvo en orden, supongamos que se
puede expresar de dos maneras distintas como producto de números primos:
Como | , entonces | . Pero es primo para todo , luego
para algún . Podemos suponer que .
Dividiendo a por obtenemos:
DIVISIBILIDAD 6
Escuela Normal Superior “ALMAFUERTE” – I.S.F.D. N° 106
Profesorado de Educación Secundaria en Matemática
Álgebra 3er Año – Prof.: Lic. Tatiana Benitez
Repitiendo el procedimiento para y suponiendo que obtenemos:
lo que no es posible porque es primo para todo .
Por lo tanto y .
6. Función Tau:
Sea y ,y su descomposición en factores primos. Asociando los
factores primos que se repiten tenemos: , con primo y un
número entero.
Los divisores de son:
( )
( )
( )
Luego, el conjunto de los divisores positivos de será:
( ) { ⁄ }
La cantidad de divisores positivos de está determinada por:
( ) ( )( ) ( )
La expresión anterior se corresponde con la función aritmética Tau ( ) que determina la
cantidad de divisores positivos de un número y :
( ) ∏( )
7. Función Phi de Euler:
Dado , la función Phi de Euler, denotada por ( ), indica la cantidad de enteros positivos
menores que y coprimos con :
( ) ⁄ ( ) * ⁄ ( ) +
Observaciones:
Si es primo, entonces ( ) .
Si , entonces ( ) .
DIVISIBILIDAD 7
Escuela Normal Superior “ALMAFUERTE” – I.S.F.D. N° 106
Profesorado de Educación Secundaria en Matemática
Álgebra 3er Año – Prof.: Lic. Tatiana Benitez
Proposición. Si es primo positivo y , entonces ( ) . /.
Demostración
Si es un primo positivo, entonces existen números no coprimos con , y ellos son:
, , , ,( ) . Por lo tanto la cantidad de números menores a coprimos con
será: .
Entonces
( )
( )
Luego
( ) ( )
Si , con primo y un número entero, tenemos:
( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
Luego, la cantidad de enteros positivos menores que y coprimos con será:
( ) ( ) ( ) ( )
8. Pequeño Teorema de Fermat
Lema. Sea un primo postivo y sea tal que . Entonces
{ ( ) ( ) ( ) (( ) )} * +
Demostración
Queremos probar que para todo tal que , el resto de la división de por
pertenece al conjunto * +.
Como el resto de la división por es siempre mayor o igual a cero y menor que , entonces
sólo debemos probar que si entonces el resto de dividir por no es cero.
DIVISIBILIDAD 8
Escuela Normal Superior “ALMAFUERTE” – I.S.F.D. N° 106
Profesorado de Educación Secundaria en Matemática
Álgebra 3er Año – Prof.: Lic. Tatiana Benitez
Supongamos que no, que ( ) . Entonces | y como es primo entonces | o
| . Pero ninguna de las posibilidades puede ocurrir, pues y por hipótesis
no es divisible por .
Por otro lado, sea , con . Como es primo y entonces ( ) .
Luego la ecuación lineal de congruencia ⌊ tiene una solución , no negativa menor
que . Pero no es divisible por , por lo tanto no puede ser cero. Luego ,y
⌊ .
Luego, y como ⌊ y entonces ( ) . Es decir
( ) .
9. Teorema: Pequeño teorema de Fermat
Sea un primo positivo y sea . Si no es divisor de , entonces ⌊ .
Demostración
Por el lema anterior, tenemos que:
( ) 0 ( )⌊ ( )⌊ ( )⌊ (( ) )⌊ 1 , -
⌊
Por propiedades de congruencia:
( )⌊ ( )⌊ ( )⌊ ( ) (( ) )⌊
Luego
( )⌊ ( )⌊ ( )⌊ (( ) )⌊ ( ) ⌊ , -
Por propiedad transitiva de , - y , -:
( ) ( ) ⌊
Luego
( ) ( ) ⌊
Y como ( ) y son coprimos esto implica que ⌊ .
10. Corolario del Pequeño Teorema de Fermat
Sea un primo positivo y sea , entonces ⌊ .
Demostración
Por teorema anterior, tenemos que ⌊ , y por propiedad de congruencias:
⌊ . Luego ⌊ .
DIVISIBILIDAD 9
Escuela Normal Superior “ALMAFUERTE” – I.S.F.D. N° 106
Profesorado de Educación Secundaria en Matemática
Álgebra 3er Año – Prof.: Lic. Tatiana Benitez
11. Teorema chino del resto
Sean , y sean tales que ( ) para todo , es
decir coprimos entre sí.
Se plantean las siguientes ecuaciones de congruencias: ⌊ para .
Entonces el sistema:
⌊
⌊
{ ⌊
tiene solución y dos soluciones cualesquiera son congruentes módulo .
Además existe una única solución tal que .
La demostración de este Teorema nos dice cómo resolver las ecuaciones de congruencias del
enunciado. Es, por lo tanto, una demostración constructiva.
Demostración
Sea , y sea para todo .
Como . / ( ) , luego existen tales que y
( ). Entonces la ecuación lineal de congruencia ⌊ posee
solución para todo .
Se define el número entero :
Veremos que es solución del sistema:
Por propiedad de reflexiva de congruencia:
∑ ⌊
Además, como | para , se tiene que: ̇ , luego: ⌊
DIVISIBILIDAD 10
Escuela Normal Superior “ALMAFUERTE” – I.S.F.D. N° 106
Profesorado de Educación Secundaria en Matemática
Álgebra 3er Año – Prof.: Lic. Tatiana Benitez
Como ⌊ , se sigue que ⌊
Por lo tanto, para todo :
Luego, es solución del sistema.
Sea otra solución del sistema. Por lo tanto, para todo : ⌊ .
Por propiedad de congruencia:
⌊
Como son coprimos entre sí, se verifica:
⌊ ⌊ ⌊
Lo que implica que ⌊ . Es decir: ⌊
Por lo tanto: ⌊
Luego, dos soluciones cualesquiera son congruentes entre sí módulo .
DIVISIBILIDAD 11
