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)