1) Introducción.

La congruencia de números fue establecida por Gauss a los 24 años en su famoso libro “Disquisitiones  Arithmeticae”, introduciendo también la notación utilizada actualmente “º”. Denotaremos por Z al conjunto de los números enteros y por N al de los naturales (sin considerar al 0).

2) Definiciones y Propiedades.

Sea m un número natural. Dados a,bÎZ (a y b son números enteros) se dice que a y b son congruentes modulo “m” si a – b es divisible por m. Esta relación la escribiremos
                                               aºbmod(m)

Ejemplos:
            a) 7 y 22 son congruentes modulo 5 y se escribe:                    b) 27 y 19 son  congruentes modulo 4                               7º 22 mod(5)                                                                           27º19mod(4)

                Porque 22 – 7 = 15, divisible por 5.                                       Porque 27 – 19 = 8, divisible por 4.

Proposición: Sea mÎN (m es natural) entonces a,bÎZ son congruentes modulo m si y solo si dejan el mismo resto al dividirlos por m.

Demostración:
            Por el algoritmo de la división existen para “a” q₁ÎZ y r₁ÎN con    0 £  r₁ < m    tal que:
                        a = q₁·m + r₁
            Análogamente para b es decir existen para “b” q₂ÎZ y r₂ÎN con     0 £  r₂ < m    tal que:
                        b = q₂·m + r₂.
             Entonces a – b = (q₁·m + r₁) – (q₂·m + r₂) = q₁·m – q₂·m + r₁ – r₂ = (q₁ – q₂)·m + (r₁ – r₂)
             Podemos ver que   –m < (r₁ – r₂)< m,     por lo que a – b es divisible por m si y solo si (r₁ – r₂)=0 es              decir si y solo si r₁ = r₂. 

Ejemplos:
             a) 7 y 22 son congruentes modulo 5:                b) 27 y 19 son  congruentes modulo 4
                Porque 22 deja resto 2 en la división por 5               Porque 27 deja resto 3 en la división por  4
                y 7 deja resto también 2.                                            y  19 también.

Proposición: Si mÎN entonces cada número entero a es congruente con uno de los números 1, 2, …, m – 1.

Demostración:   
            Por el algoritmo de la división existen para “a” qÎZ y rÎN con   0 £  r <m     tal que
                        a = q·m + r
            Entonces a – r = q·m que es divisible por m luego a y r son congruentes, a º r mod(m).

Ejemplos:
            a) 57º1mod(4)        b) 63º3mod(10)     c) 257º2mod(17)        d) 805º7mod(19)

Propiedades:

a)      aºa mod(m).

b)      Si aºb mod(m)   entonces   bºa mod(m).

c)      Si aºb mod(m)  y  bºc mod(m) entonces aºc mod(m).

d)      Si aºb mod(m)  y  cºd mod(m) entonces (a + c)º(b + d)mod(m)  y  acºbd mod(m).

e)      Si aºb mod(m)  entonces  acºbc mod(m).

f)        Si aºb mod(m) y c¹0 divide a “a” y “b” entonces a/cºb/c mod(m).

g)      Si aºb mod(m) entonces aⁿºbⁿ mod(m)

Ejemplos:
           a) 17º3mod(7) y  22º1mod(7) entonces  39º4mod(7)  por d)   39 = 17 + 22, 4= 3 + 1.
           b) 17º3mod(7) entonces  85º15mod(7)  por e)  85 = 17·5 y  15 = 5·3
           c) 85º15mod(7) y  15º1mod(7) entonces 85º1mod(7) por c).
           d) 16º2mod(7) entonces 16²⁰º2²⁰mod(7)  pero 2²⁰= (2³)⁶·2² =8⁶·4 y  8⁶·4º1⁶·4mod(7) por tanto
                                        16²⁰º4mod(7).                                         

Ejercicio1: Demuestra que si d divide a m con d,mÎN y aºbmod(m) entonces  aºbmod(d).

            Ejemplo: 3 divide a 6 y   26º2mod(6) entonces 26º2mod(3).

Ejercicio2: Demuestra que si p es un número primo entonces p es congruente con 1 o 5 modulo6. Es decir que p deja resto 1 o 5 al dividirlo por 6.

3) Teoremas importantes.

Definición: Sea mÎN, llamamos función de Euler y la denotamos por f(m) a la función que nos da la cantidad de números naturales primos relativos con m y que no exceden a este.

Ejemplos:
            f(6) = 2, son estos: 1 y  5.                         f(15) = 8,  son estos: 1, 2, 4, 7, 8, 11, 13, 14

Propiedades:
a) f(p) = p – 1 si p es primo.      b)  f(p^k) = (p – 1)p^{k – 1}       c) f(ab) = f(a)· f(b) si   m.c.d(a, b) = 1.

Teorema: (De Euler) Sean a y m dos números enteros con m ³ 1 y m.c.d(a, m) = 1, entonces se tiene que:
                                      a^f(m)º1mod(m) 

Corolario: (Pequeño teorema de Fermat) Si p es un número primo que no divide al número a entonces:
       a^{p – 1}º1mod(p).

Teorema: (De Wilson) Si p es un número primo entonces (p – 1)!º-1mod(p).