Congruencias

§1.
Congruencias en el conjunto de los números
naturales.

Definición 1: Si y se dice que son congruentes módulo m si en la
división entera por m dan el mismo resto y en este caso,
se escribe

Con otras palabras si y solamente si,

La relación de congruencia es evidentemente una
relación de equivalencia (reflexiva, simétrica y
transitiva) puesto que la relación de igualdad lo
es:

Propiedad reflexiva:

Propiedad simétrica:

Propiedad transitiva:

A partir de la definición de la congruencia de
los números naturales es fácil demostrar las
siguientes propiedades:

Propiedad 1:

En efecto,

Así, tiene ser cierto puesto que implicaría que
es decir
resultaría que Por tanto la diferencia existe y implica que es divisible por Al revés, si existe y es divisible por m entonces
y existe tal que Entonces de la
división euclidea , donde resulta que Esto quiere decir es también el resto de la
división euclidea de por y así

Propiedad 2:

En efecto, si entonces divide la diferencia y así según la propiedad 1
Si entonces se puede considerar
la congruencia equivalente: de donde resulta que divide a Por tanto

Propiedad 3:

En efecto, si entonces de resulta que es múltiplo de es decir existe tal que De aquí resulta que es decir es múltiplo de
y según la
propiedad 1, tendremos la primera implicación. Si
tendremos
también de
donde resulta la segunda implicación.

Propiedad 4:

En efecto, si entonces según la propiedad 1divide a y así Si entonces según la propiedad 1
divide la
diferencia y
así

Propiedad 5:

En efecto, si según la propiedad1 divide la diferencia
y así
Por tanto,
divide la
diferencia y
así, utilizando de nuevo la propiedad 1, resulta que
Si hay que razonar de la misma
manera a partir de la congruencia

Propiedad 6: Si es un divisor común de los
números naturales y es un divisor de m, sean Entonces

En efecto, se puede suponer que Puesto que divide el número , resulta que divide a Así, según la propiedad1
Al revés,
y y así, el
número es un
divisor de Por
tanto será
un divisor de

Propiedad 7:

En efecto, se puede suponer que yLuego, es un divisor común de las diferencias
y de de donde resulta que
divide a

, y teniendo en cuenta que resulta que

Por inducción completa de aquí resulta
que

Propiedad 8: Si y entonces existe tal que

En efecto, es un divisor de la diferencia y así existe
tal que La recíproca es
evidente.

Propiedad 9:

En efecto, se puede suponer que Entonces, según la propiedad 8
y y así resulta
que:

, y así la propiedad queda demostrada.

Por inducción completa también en este
caso resulta que

Propiedad 10: entontes donde es el mínimo común
múltiplo de los números

En efecto, se puede suponer que y, según la propiedad 1, es un múltiplo
común de los números Entonces, puesto que cualquier múltiplo
común de ciertos números es múltiplo del
mínimo común múltiplo de estos
números, será múltiplo de M, es decir

Observación 1: La relación de
equivalencia divide
al conjunto N en clases de equivalencia, dos a dos disjuntas y
cada clase contiene los números naturales que dan el mismo
resto en la división por m. La clase a la que pertenece el
número se
notará con Los elementos de las clases se llaman
representantes de la clase. Normalmente se trabaja con el
representante menor. El conjunto de todas las clases de N
respecto al módulo m se nota con y

Luego, las propiedades siguientes son
evidentes:

es
divisible por m.

Por ejemplo: Si y entonces , y

Las operaciones en el conjunto de las clases se definen
de la manera siguiente:

,

Estas operaciones no dependen de la elección de
los representantes en las clases. En efecto, si

y , donde . Entonces

Obviamente, la conmutatividad y asociatividad de la suma
y de la multiplicación de las clases se reduce a las mimas
propiedades de la suma y de la multiplicación en
N.

En la
resta es siempre posible. En efecto, sean

En efecto, si entonces

Si entonces existe tal que e

Puesto que cualquiera que sea y es un elemento opuesto bilateral de , es un grupo conmutativo. Luego, teniendo en
cuenta que la propiedad distributiva de la multiplicación
de las clases respecto a la suma de las clases también se
reduce a la distributividad de la multiplicación respecto
a la suma en N, y que es un elemento neutro en la
multiplicación de las clases, resulta que es un anillo asociativo,
conmutativo y con elemento neutro, que puede tener divisores de
cero (si por ejemplo pero ). Si m es un número primo entonces
no tiene divisores
de cero y el elemento inverso de debe existir puesto que los productos son no nulos y dos a dos
diferentes. Si dos de ellos fueran iguales resultaría la
existencia de los divisores de cero: de resultaría que donde y ). Así, alguno de los productos
mencionados debe ser igual a Si y entonces Por tanto si m es un número primo,
es un
cuerpo.

Teorema 0:

En efecto:

La segunda propiedad se demuestra de manera
análoga.

Por definición, dos números naturales son
primos entre sí (o son primos relativos) si su
máximo común divisor es 1, es decir

Teorema 1: Los números son primos relativos, si y
solamente sí, es un elemento inversible del anillo

En efecto si son primos relativos resulta que existen
tal que

Entonces en tienen lugar las implicaciones
siguientes:

Por tanto es inversible en Al revés si es inversible en existe tal que

Así el único divisor común de
es el número
1 y por consiguiente son primos relativos.

Teorema 2 (de Fermat): Si p es un número
primo y entonces

En efecto, el teorema se cumple para Si y teniendo en cuenta que es un grupo, el elemento
es de índice
1(ver [8]) y si es
el elemento inverso de entonces

Multiplicando ambas partes de la congruencia con resulta que

Por definición, si y es el indicador de Euler entonces y para es el número de aquellos números
naturales no nulos
y menores que para
los cuales son
primos relativos.

Teorema 3 (de Euler): Si son números naturales y son primos relativos,
entonces

En efecto, sean los números naturales no nulos, menores
que m y primos relativos conPuesto que son primos relativos,

, tendremos

, y así

Según el teorema 1, son inversibles en y, como producto de elementos inversibles,
lo es
también. Entonces,

, y

Finalmente, y el teorema queda demostrado.

Observación 2: El Teorema de Fermat es
consecuencia del teorema de Euler puesto que si es un número primo,
entonces

Teorema 4 (de Wilson): p es un número
primo si, y solamente si,

Antes de demostrar el teorema hay que averiguar
cuáles de las clases coinciden con su clase inversa, es decir
cuáles cumplen las igualdades

Primero hay que observar que en no hay divisores de cero y por
tanto

Luego, teniendo en cuenta que al multiplicar todos los
elementos de un grupo finito multiplicativo, el producto
será igual con el producto de aquellos elementos que
coinciden con su inverso,

Por tanto

Al revés, si el número p que cumple la
condición no
fuera primo, debería tener una descomposición
donde Al ser u un divisor de p, u
tendría que ser un divisor común de y y así u debería dividir la
diferencia lo que
es imposible, al ser u mayor que 1. La contradicción
obtenida demuestra que p tiene que ser un número
primo.

§2.
Congruencias en el conjunto de los números
enteros.

Si ,
y se dice que a y b son
congruentes módulo m, si m divide la diferencia y se escribe Con otras
palabras,

La relación de congruencia es evidentemente una
relación de equivalencia (reflexiva, simétrica y
transitiva):

Propiedad reflexiva: ya que m divide la diferencia

Propiedad simétrica: puesto que si m divide a la diferencia
dividirá
también la diferencia

Propiedad transitiva:

En efecto, si m divide a y entonces m dividirá a

A partir de la definición de la congruencia de
los números enteros es fácil demostrar las
siguientes propiedades:

En efecto, m divide a las diferencias Por tanto

En efecto, m divide la diferencia al ser m un divisor de

Esta ultima propiedad es evidente puesto que u es
divisor de m, m es divisor de y así u es divisor de

Si es el
máximo común divisor de los números enteros
y d es un divisor
de m, entonces

En efecto, y divide a resulta que y así es decir Por tanto, divide a Al revés de resulta que es un divisor de y así será un divisor

La relación de equivalencia divide al conjunto Z en
clases de equivalencia, dos a dos disjuntas y cada clase contiene
los números enteros tales que la diferencia de dos
cualesquiera de ellos sea un múltiplo de m. La clase a la
que pertenece el número se notará con Los elementos de las clases se llaman
representantes de la clase. Normalmente se trabaja con el
representante mayor o igual a cero. El conjunto de todas las
clases de Z respecto al módulo m se nota con y

Luego, las propiedades siguientes son
evidentes:

Por ejemplo: Si y entonces , y

Las operaciones en el conjunto de las clases se definen
de la manera siguiente:

, .

Estas operaciones no dependen de la elección de
los representantes en las clases. En efecto, si

Entonces,

Teorema 5:

En efecto:

Obviamente la conmutatividad y asociatividad de la suma
y de la multiplicación de las clases se reduce a las mimas
propiedades de la suma y la multiplicación en
Z.

Puesto que cualquiera que sea y es un elemento opuesto bilateral de , es un grupo conmutativo. Luego, teniendo en
cuenta que la propiedad distributiva de la multiplicación
de las clases respecto a la suma de las clases también se
reduce a la distributividad de la multiplicación respecto
a la suma en Z, y que es un elemento neutro en la
multiplicación de las clases, resulta que es un anillo asociativo,
conmutativo y con elemento neutro, que puede tener divisores de
cero (si por ejemplo pero Si es un número primo entonces no tiene divisores de cero y
el elemento inverso de debe existir puesto que los productos son no nulos y dos a dos
diferentes (Si dos de ellos fueran iguales resultaría la
existencia de los divisores de cero: de resultaría que donde y ). Así, alguno de los productos
mencionados debe ser igual a Si y entonces Por tanto si m es un número primo,
es un
cuerpo.

Definición 2: Una congruencia de grado n
tiene la forma

(1)

, donde es
una función polinomio con coeficientes enteros, es un número natural
mayor que 1 y no es
un múltiplo de

Resolver la congruencia significa hallar todos los
números enteros para los cuales la congruencia es
verdadera.

Una congruencia de primer grado tiene la
forma:

(2)

, donde no
es múltiplo de

§3.
Resolución de congruencias de primer
grado.

Teorema 6: Si el máximo común
divisor de divide a
la congruencia (2)
tiene solución. En efecto, la condición es
necesaria puesto que si es una solución

(3)

Teniendo en cuenta que yde (3) resulta que

, es decir d tiene que ser un divisor La condición es
también suficiente, puesto que si el máximo
común divisor de divide a entonces (según la propiedad
3)

, donde son primos relativos. Entonces, según el
teorema de Euler donde Así, será una solución de la
congruencia y por
tanto, también de la congruencia

Si es una
solución de la congruencia y es una solución cualquiera entonces la
solución general de esta congruencia
será:

(3)

En efecto,

En el caso y
las soluciones obtenidas son todas las soluciones de la
congruencia (2). Si teniendo en cuenta que las soluciones
correspondientes que se obtienen para son incongruentes respecto al módulo
la solución
general de la congruencia (2) será la
siguiente:

(4)

Ejemplo 1: Resolver la congruencia:

Puesto 2 es el máximo común divisor de 4 y
6 y 2 no divide a 3, la congruencia no tiene solución. Se
llegaría a la misma conclusión por el método
directo, es decir averiguando que ninguno de los números
1,2,3,4,5 es solución de la congruencia.

Ejemplo 2: Resolver la congruencia:

Puesto que 4 y 11 son primos relativos, la congruencia
tiene solución. Calculando los productos y el resto de la división de cada
producto en la división por 11 resulta que Por tanto, la
solución de la congruencia es

A continuación, el método anterior se
llamará el método directo.

Observando que 11 es un número primo, la
solución se podría obtener también
utilizando el teorema de Fermat:

El teorema de Wilson sirve también para resolver
la congruencia anterior. Teniendo en cuenta que según el
teorema de Wilson

, resultan las equivalencias siguientes:

Ejemplo 3: Resolver la congruencia

Utilizando el método directo, se observa
quePor
consiguiente, la solución de la congruencia es Puesto que 12 no es un
número primo, el teorema de Fermat no es utilizable en
este caso. Sin embargo el teorema de Euler es
aplicable.

Teniendo en cuenta que ( entre los números
1,2,3,4,5,6,7,8,9,10,11 hay cuatro números que son primos
con 12), resulta que Por consiguiente,

Ejemplo 4: Resolver la congruencia:

(5)

(6)

Por el método directo se obtiene que Por tanto la solución
general de la congruencia (6) es Las soluciones 5 y 12 son incongruentes
respecto al módulo 14 y así la solución
general de la congruencia (5) se escribirá de la manera
siguiente:

Si los númerosno superan a los cálculos anteriores se
podrían efectuar con los códigos siguientes (que
corresponden al método directo, al método de Euler
ó al método de Simpson, respectivamente, y el
usuario debe decidir qué método es posible y con
qué método quiere trabajar):

Public Function MetodoDirecto(ByVal a As Long, ByVal b
As Long, ByVal m As Long) As String

Dim s() As Long, ax As Long, bx As Long, i As Long, k As
Long

Dim x As Long, mcd As Long, mx As Long, rc As String, rs
As String

If m < 1 Then

MetodoDirecto = " El módulo tiene que ser un
entero mayor que 1"

Exit Function

End If

rc = Chr$(13) + Chr$(10): mcd = MaxComDiv2(a,
m)

x = b Mod mcd

If x = 0 Then

If mcd = 1 Then

ax = a: bx = b: mx = m

Else

ax = a / mcd: bx = b / mcd: mx = m / mcd

End If

ax = ax Mod mx

bx = bx Mod mx

For i = 1 To mx – 1

x = (ax * i – bx) Mod mx

If x = 0 Then k = i: Exit For

Next i

ReDim s(mcd)

s(1) = k

For i = 2 To mcd: s(i) = s(i – 1) + mx: Next
i

For i = 1 To mcd

rs = rs + rc + "x(" + Str$(i) + ") = " + Str$(s(i)) + "
+ k*" + Str$(m)

Next i

Else

rs = "No hay soluciones"

End If

MetodoDirecto = rs

End Function

Public Function MetodoEuler(ByVal a As Long, ByVal b As
Long, ByVal m As Long) As String

Dim s() As Long, ax As Long, bx As Long, cx As Long, rc
As String

Dim x As Long, mcd As Long, mx As Long, em As Long, rs
As String

If m < 1 Then

MetodoEuler = " El módulo tiene que ser un entero
mayor que 1"

Exit Function

End If

rc = Chr$(13) + Chr$(10): mcd = MaxComDiv2(a,
m)

x = b Mod mcd

If x = 0 Then

If mcd = 1 Then

ax = a: bx = b: mx = m

Else

ax = a / mcd: bx = b / mcd: mx = m / mcd

End If

ax = ax Mod mx

bx = bx Mod mx

For i = 2 To Sqr(m)

x = m Mod i

If x = 0 Then Exit For

Next i

If i > Sqr(m) Then em = m – 1 Else em =
Euler(mx)

x = bx

For i = 1 To em – 1

x = x * ax

x = x Mod mx

Next i

ReDim s(mcd)

s(1) = x

For i = 2 To mcd: s(i) = s(i – 1) + mx: Next
i

For i = 1 To mcd

rs = rs + rc + "x(" + Str$(i) + ") = " + Str$(s(i)) + "
+ k*" + Str$(m)

Next i

Else

rs = "No hay soluciones"

End If

MetodoEuler = rs

End Function

Public Function MetodoSimpson(ByVal a As Long, ByVal b
As Long, ByVal m As Long) As String

Dim i As Integer, s() As Long, rc As String, rs As
String

Dim x As Long, ax As Long, bx As Long

If m < 1 Then

MetodoSimpson = " El módulo tiene que ser un
entero mayor que 1."

Exit Function

End If

ax = a: bx = b

rc = Chr$(13) + Chr$(10)

mcd = MaxComDiv2(ax, m)

x = bx Mod mcd

If x <> 0 Then

MetodoSimpson = "La congruencia no tiene
soluciones."

Exit Function

End If

If ax < 0 Then ax = -ax: bx = -bx

For i = 2 To Sqr(m)

x = m Mod i

If x = 0 Then

MetodoSimpson = "El módulo no es primo, el
método de Simpson no es utilizable"

Exit Function

End If

Next i

If m < ax Then

MetodoSimpson = "m es primo pero p < Abs(a), el
método de Simpson no es aplicable"

Exit Function

End If

ax = ax Mod m

bx = bx Mod m

x = bx

For i = 2 To m – 1

If i <> Abs(ax) Then

x = i * x

x = x Mod m

End If

Next i

x = -x

rs = "x = " + Str$(x) + " + k*" + Str$(m)

MetodoSimpson = rs

End Function

Public Function MaxComDiv2(ByVal a As Long, ByVal b As
Long) As Long

Dim ax As Long, bx As Long, x As Long, qx As Long, rx As
Long

ax = Abs(a): bx = Abs(b)

If ax < bx Then

x = ax: ax = bx: bx = x

End If

Do

rx = ax Mod bx

If rx = 0 Then Exit Do

ax = bx: bx = rx

Loop

MaxComDiv2 = bx

End Function

Public Function Euler(ByVal m As Long) As
Long

Dim i As Integer, j As Integer, mcd As
Integer

For i = 1 To m – 1

mcd = MaxComDiv2(i, m)

If mcd = 1 Then j = j + 1

Next i

Euler = j

End Function

Ejemplo 5: Al resolver la congruenciapor el método directo
o de Euler, se obtienen las soluciones siguientes donde

Ejemplo 6: Al resolver la congruencia por el método de
Simpson, se obtiene la solución:

Ejemplo 7: La congruencia no tiene soluciones puesto que el
máximo común divisor de los números
es 4 y 4 no divide
el número

La Cuando los número enteros no tienen más de 8
dígitos (las variables son de tipo Long), estos programas
funcionan bien y son más rápidos cuándo el
módulo es menor.

Public Function CongruenciasD(ByVal a As String, ByVal b
As String, ByVal m As String) As String

Dim s() As String, ax As String, bx As String, i As
String, j As String, k As String

Dim mcd As String, mx As String, n As Integer, rt() As
String, rs() As String

Dim x(2) As String, rr As String, dif As String, rc As
String, res As String

rc = Chr$(13) + Chr$(10): n = 7

x(1) = a: x(2) = m: mcd = MaxComDiv(x(), n)

x(1) = b: x(2) = mcd: rt() = DivisionEuclidea(x(),
n)

If rr(2) ="-0" then rr(2) = "0"

If rr(2) = "0" Then

If mcd = "1" Then

ax = a: bx = b: mx = m

Else

x(2) = mcd

x(1) = a: rt() = DivisionEuclidea(x(), n): ax =
rt(1)

x(1) = b: rt() = DivisionEuclidea(x(), n): bx =
rt(1)

x(1) = m: rt() = DivisionEuclidea(x(), n): mx =
rt(1)

End If

If mx = "1" Then

If m = "1" Then

CongruenciasD = "¡El módulo tiedne que ser
mayor que 1!"

Else

CongruenciasD = "Cualquier número natural es
solución."

End If

Exit Function

End If

x(2) = mx

x(1) = ax: rt() = DivisionEuclidea(x(), n): ax =
rt(2)

x(1) = bx: rt() = DivisionEuclidea(x(), n)

If rr(2) ="-0" then rr(2) = "0"

bx = rt(2)

i = "1"

Do

x(1) = ax: x(2) = i: x(1) = Multiplicar(x(),
n)

x(2) = bx: dif = Restar(x(), n)

x(1) = dif: x(2) = mx: rt() = DivisionEuclidea(x(),
n)

If rr(2) ="-0" then rr(2) = "0"

If rt(2) = "0" Then k = i: Exit Do

x(1) = i: x(2) = "1"

i = Sumar(x(), n)

Loop

ReDim s(mcd), rs(mcd)

s(1) = k: i = "1"

If mcd <> "1" Then

Do

x(1) = i: x(2) = "1": j = Sumar(x(), n)

x(1) = s(i): x(2) = mx: s(j) = Sumar(x(), n): i =
j

Loop Until i = mcd

End If

i = "0": res = ""

Do

x(1) = i: x(2) = "1": j = Sumar(x(), n)

rs(j) = rs(j) + rc + "x(" + j + ") = " + s(j) + " + k*"
+ m

res = res + rs(j) + rc: i = j

Loop Until i = mcd

Else

res = "No hay soluciones"

End If

CongruenciasD = res

End Function

Public Function CongruenciasE(ByVal a As String, ByVal b
As String, ByVal m As String) As String

Dim s() As String, ax As String, bx As String, cx As
String, n As Integer, pr As String

Dim xx As String, mcd As String, mx As String, em As
String, x(2) As String, rt() As String

Dim res As String, fi As Integer, fm As Integer, rs() As
String, mcd2 As String, j As String

If m = "1" Then

CongruenciasE = "¡El módulo tiedne que ser
mayor que 1!"

Exit Function

End If

n = 7: x(1) = a: x(2) = m

mcd = MaxComDiv(x(), n)

x(1) = b: x(2) = mcd

rt() = DivisionEuclidea(x(), n)

If rr(2) ="-0" then rr(2) = "0"

xx = rt(2)

If xx = "0" Then

If mcd = 1 Then

ax = a: bx = b: mx = m

Else

'ax = a / mcd: bx = b / mcd: mx = m / mcd

x(2) = mcd

x(1) = a: rt() = DivisionEuclidea(x(), n): ax =
rt(1)

x(1) = b: rt() = DivisionEuclidea(x(), n): bx =
rt(1)

x(1) = m: rt() = DivisionEuclidea(x(), n): mx =
rt(1)

End If

If mx = "1" Then

CongruenciasE = "Cualquier número natural es
solución."

Exit Function

End If

fm = Val(Right$(mx, 1)) ' última cifra de
mx

If fm = 0 Mod 2 Then fm = 0

x(1) = ax: x(2) = mx

rt() = DivisionEuclidea(x(), n): ax = rt(2)

x(1) = bx: x(2) = mx:rt() = DivisionEuclidea(x(),
n)

If rr(2) ="-0" then rr(2) = "0"

bx = rt(2)

'Establecer el valor de
FunciónEuler(m)-1.

i = "1": pr = "0"

Do

x(1) = i: x(2) = "1": i = Sumar(x(), n)

If i = mx Then Exit Do

x(1) = i: x(2) = mx

fi = Val(Right$(i, 1))

If fi = 0 Mod 2 Then fi = 0

If fi <> 0 Or fm <> 0 Then

' cuando i y mx no son pares los dos.

mcd2 = MaxComDiv(x(), n)

If mcd2 = "1" Then

x(1) = pr: x(2) = "1": pr = Sumar(x(), n)

End If

End If

Loop

xx = bx: i = "0"

Do

If i = pr Then Exit Do

x(1) = i: x(2) = "1": i = Sumar(x(), n)

x(1) = xx: x(2) = ax: xx = Multiplicar(x(),
n)

x(1) = xx: x(2) = mx: rt() = DivisionEuclidea(x(),
n)