- Congruencias en el
conjunto de los números naturales - Congruencias en el
conjunto de los números enteros - Resolución
de congruencias de primer grado - Resolución
de congruencias de grado superior - Sistemas de
congruencias de primar grado - Sistemas de
congruencias de grado superior - Bibliografía
§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)
Página siguiente |