Scribd
Cargar
44 vistas3 páginas

Congruencias y Teoremas de Números Enteros

El documento aborda el concepto de congruencias en matemáticas, definiendo que dos enteros son congruentes respecto a un módulo si su diferencia es divisible por dicho módulo. Se presentan propiedades de las congruencias, el pequeño teorema de Fermat y ejemplos de congruencias importantes, así como la relación de equivalencia que permite descomponer el conjunto de enteros en clases de restos. Además, se menciona la función indicador de Euler y su relación con la congruencia.

Cargado por

alvaromahesh6
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Temas abordados

  • teorema de Fermat extendido,
  • números primos,
  • restos de divisibilidad,
  • números congruentes y demostra…,
  • números congruentes módulo,
  • función indicador de Euler,
  • divisibilidad,
  • módulo primo,
  • suma de cifras,
  • congruencias y divisibilidad
44 vistas3 páginas

Congruencias y Teoremas de Números Enteros

El documento aborda el concepto de congruencias en matemáticas, definiendo que dos enteros son congruentes respecto a un módulo si su diferencia es divisible por dicho módulo. Se presentan propiedades de las congruencias, el pequeño teorema de Fermat y ejemplos de congruencias importantes, así como la relación de equivalencia que permite descomponer el conjunto de enteros en clases de restos. Además, se menciona la función indicador de Euler y su relación con la congruencia.

Cargado por

alvaromahesh6
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Temas abordados

  • teorema de Fermat extendido,
  • números primos,
  • restos de divisibilidad,
  • números congruentes y demostra…,
  • números congruentes módulo,
  • función indicador de Euler,
  • divisibilidad,
  • módulo primo,
  • suma de cifras,
  • congruencias y divisibilidad

CONGRUENCIAS

2.1 Si la diferencia de dos enteros a y b es divisible por m, se dice que a


y b son congruentes respecto al módulo m, y se emplea la notación de Gauss :
a b(mod m): Esta de…nición equivale a decir que a y b dan el mismo resto al
ser divididos por m:
2.2 Propiedades
i) Si dos números son congruentes con un tercero son congruentes entre sí.
ii) a 0(mod m) quiere decir que a es múltiplo de m:
iii) Si a b y c d; entonces a + c b + d; a c b d y ac bd (todas
mod m): En efecto, como a b y c d son múltiplos de m; su suma y diferencia
también lo son.
iv) Aunque a b(mod m) =) na nb(mod m); el recíproco no tiene por
qué ser cierto. Por ejemplo, 4 7 = 28 8 = 4 2(mod 10); pero sin embargo 7 y
2 no son congruentes entre sí, módulo 10. Esto ilustra el importante resultado
siguiente :
Si na nb(mod m) y q es el m.c.d. de n y m; entonces a b(mod m=q):
En efecto, n = qN; m = qM;con M y N primos entre sí. Ya que n (a b)
es divisible por m, N (a b) es divisible por M, y por el segundo teorema de
Euclides, a b es divisible por M.
El caso q = 1 da el importante resultado siguiente:
v) Si na nb(mod m) y n es primo con m; entonces a b(mod m)

2.3 Restos mínimos


Dado m; cualquier entero k se puede escribir en la forma k = qm + r;
con 0 r < m: Este r se llama el mínimo resto de k módulo m:
El conjunto de los números 0; 1; 2; 3; ; m 1 es un conjunto completo de
restos mínimos módulo m, o conjunto de números incongruentes módulo m.
Teorema
Si a y b son primos entre sí, y r es un entero cualquiera, los restos mínimos
módulo b de los números

r; a + r; a + 2r; a + 3r; ; (b 1) a + r
son los números

0; 1, 2, 3, ; b 1
aunque no necesariamente en este orden.
Demostración.
En el primer conjunto hay b números; por lo tanto, bastará probar que no
hay dos de ellos que den el mismo resto al ser divididos por b:
Supongamos, por el contrario, que sa + r y ta + r (0 s < b; 0 t < b) dan
el mismo resto al ser divididos por b: Entonces sa ta(mod b); y como a y b
son primos entre sí, s t(mod b)
De aquí que s = t; puesto que ambos números son menores que b:

1
2.5 El pequeño teorema de Fermat(1640)
Si p es primo, y a no es divisible por p, entonces ap 1 1(mod p)
Demostración
Tomando en el teorema anterior r = 0; resulta que los números

a; 2a; 3a; ; (p 1)a


son congruentes (mod p) a los números 1; 2; 3; ; p 1 (no necesariamente
en ese orden).Multiplicando todas esas congruencias obtenemos

ap 1
1 2 (p 1) 1 2 (p 1)
pero, al ser p primo, se pueden simpli…car todos los factores comunes a los
dos miembros de la congruencia, y resulta el enunciado.
Consecuencia
Multiplicando los dos miembros de la congruencia anterior por a resulta

ap a(mod p) () ap a 0(mod p); si p es primo.


2.6 Congruencias importantes respecto de algunos módulos
i) Cualquier entero n es congruente (mod 9) con la suma de sus cifras.
En efecto, sea n = a:10k +b:10k 1 + +h (aquí, h es la cifra de las unidades
de n). Como 10k 1(mod 9); resulta

n (a + b + + h) (mod9)
En este resultado se basan los criterios de divisibilidad.
ii)Cuadrados
Cualquiera que sea el entero n; se verif ica

0(mod 4) si n es par
n2
1(mod 4) si n es impar
8
< 0(mod 8) si n 0(mod 4)
n2 4(mod 8) si n 2(mod 4)
:
1(mod 8) si n es impar
El conjunto de las clases de restos
La relación de congruencia, por tener las propiedades re‡exiva, simétrica y
transitiva, es una relación de equivalencia que permite descomponer el conjunto
Z en clases, tantas como valga el módulo de la congruencia. El conjunto de las
clases se representa por Z/mZ, y en el la suma y el producto de congruencias
le induce estructura de anillo conmutativo. El hecho de ser primo el módulo de
la congruencia permite a…rmar más:

Z=pZ es un cuerpo si y sólo si p es primo


Cuando p no es primo, el anillo de clases de restos tiene divisores de cero.

La extensión por Euler del teorema de Fermat

2
La función ”indicador” de Euler se de…ne así

(m) = número de enteros positivos menores que m y primos con m

Entonces se veri…ca la implicación


(m)
mcd(a; m) = 1 =) a 1(mod m):

También podría gustarte