If rr(2) ="-0" then rr(2) = "0"
xx = rt(2)
Loop
ReDim s(mcd), rs(mcd)
s(1) = xx: i = "2"
If mcd <> "1" Then
Do
x(1) = i: x(2) = "1": j = Restar(x(), n)
x(1) = s(j): x(2) = mx: s(i) = Sumar(x(), n)
If i = mcd Then Exit Do
x(1) = i: x(2) = "1": i = Sumar(x(), n)
Loop
End If
i = "0": res = ""
Do
x(1) = i: x(2) = "1": j = Sumar(x(), n)
rs(i) = rs(j) + rc + "x(" + j + ") = " + s(j) + " + k*"
+ m
res = res + rs(i) + rc: i = j
If i = mcd Then Exit Do
Loop
Else
res = "¿No hay solución!"
End If
CongruenciasE = res
End Function
Ejemplo 7: Para hallar el elemento inverso
hay que resolver la
congruencia que
tiene solución si y solamente son primos relativos. En este caso Por supuesto, primero hay
que hallar el valor de con la función de Euler. Por ejemplo,
utilizando la función CongruenciasE, con los argumentos
donde son variables de tipo
string, la solución de la congruencia es Por tanto, el elemento inverso de la clase
es la
clase
Ejemplo 8: Resolver la congruencia:
Por los dos métodos anteriores se obtiene la
solución:
Ejemplo 9: Resolver la congruencia:
Los dos métodos anteriores dan el resultado
siguiente:
;
Cuando el módulo no tiene más que 8
dígitos, la longitud de los números a y b puede ser
muy superior a la longitud del modulo y los dos programas
siguientes seguirán funcionando con una velocidad
aceptable.
Para resolver las congruencias de primer grado existe
también el método de las fracciones continuas [9].
A continuación se considerarán las fracciones
continuas finitas de la forma siguiente:
(6a)
, donde los números son números naturales. Las fracciones
continuas se llaman reducidas de la
fracción continua Cada fracción continua y sus reducidas
se pueden expresar en la forma de fracciones ordinarias. Si
, entonces y
para calcular las reducidas siguientes se conocen las
fórmulas de recurrencia siguientes:
(6b)
Se ha demostrado que:
(6c)
También se conoce que cada fracción
ordinaria se puede desarrollar en una fracción continua
finita, y que todas las reducidas son fracciones ordinarias
irreducibles. Para resolver la congruencia Si se tiene que
resolver la congruencia (2), se puede suponer que los
números son
primos relativos. Sea (6a) el desarrollo de la fracción
ordinaria a/m en fración continua. Entonces, según
la relación (6c) aplicada para , resulta que
, es decir
Así la congruencia (2) tiene las
soluciones
(6d)
Ejemplo 10: En la congruencia el máximo
común divisor de 6 y de 15 es 3, que divide al
número 21. La congruencia equivalente es El desarrollo en
fracción continua de 2/5 es y así la solución es:
En el caso cuando los coeficientes de la congruencia y
los números que intervienen en el proceso de
resolución pueden ser almacenados en variables de tipo
Long se puede utilizar el el pgrama siguiente, basado en el
método de las fracciones continuas.
Public Function MetodoFraC(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, rr() As Long, d As Long
Dim x As Long, mcd As Long, mx As Long, rc As String, rs
As String, t As Long
Dim p() As Long, q() As Long
If m < 1 Then
MetodoFraC = " 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
If ax < 0 Then ax = -ax: bx = -bx
rr() = FraContFra(ax, mx)
d = UBound(rr())
ReDim p(d), q(d)
p(0) = rr(0): q(0) = 1
p(1) = rr(0) * rr(1) + 1: q(1) = rr(1)
For i = 2 To d
p(i) = rr(i) * p(i – 1) + p(i – 2)
q(i) = rr(i) * q(i – 1) + q(i – 2)
Next i
x = bx * q(d – 1)
t = (d + 1) Mod 2
If t = 1 Then x = -x
ReDim s(mcd)
x = x (mod mx)
s(1) = x
If s(1) < 0 Then
s(1) = s(1) + mx
End If
For i = 2 To mcd: s(i) = s(i – 1) + m: 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
MetodoFraC = rs
End Function
Public Function FraContFra(ByVal a0 As Long, ByVal b0 As
Long) As Variant
"Desarrollo de una fracción ordinaria en
fracción continua
Dim i As Long, j As Long, x As String, n As
Long
Dim ax As Long, bx As Long, q0 As String, q() As
Long
ax = Abs(a0): bx = Abs(b0)
Do
qx = Int(ax / bx): rx = ax – qx * bx
If rx <> 0 Then
i = i + 1
q0 = q0 + Str$(qx) + ","
ax = bx: bx = rx
Else
q0 = q0 + Str$(qx) + ","
i = i + 1
Exit Do
End If
Loop
d = i – 1: j = 0
ReDim q(d)
Do
For i = 1 To Len(q0)
x = Left$(q0, i)
If Right$(x, 1) = "," Then
q(j) = Val(Left$(x, Len(x) – 1))
q0 = Mid$(q0, i + 1)
Exit For
End If
Next i
If q0 = "" Then Exit Do
j = j + 1
Loop
FraContFra = q()
End Function
Esta función es utilizable si los coeficientes de
la congruencia y los números que aparecen durante el
cálculo pueden ser almacenados en variables de tipo
Long.
Finalmente, si se utilizan las operaciones con
números enteros largos el código anterior se puede
transformar en un código "5 estrellas" para la
resolución de las congruencias de primer grado, basado
también en el método de las fracciones continuas.
Esta vez, los números se almacenan en variables de tipo
string y el tiempo necesario para la resolución es
más que razonable. El programa siguiente (escrita en
negrita) se puede utilizar siempre, incluso cuando las funciones
"CongruenciasD" y "CongruenciasE" tardan demasiado tiempo en los
cálculos.
Public Function MFrContCg(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
Long, k As String
Dim xx As String, mcd As String, mx As String, rc As
String, rs As String
Dim p() As String, q() As String, x(2) As String,
fr() As String
Dim d As Long, t As Long, n As Integer, rr() As
String, dif As String
n = 7: x(1) = m: x(2) = "1"
xx = Restar(x(), n)
If Left$(xx, 1) = "-" Or xx = "1" Then
MFrContCg = " El módulo tiene que ser un
entero mayor que 1"
Exit Function
End If
rc = Chr$(13) + Chr$(10)
x(1) = a: x(2) = m
mcd = MaxComDiv(x(), n)
x(1) = b: x(2) = mcd
rr() = DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
xx = rr(2)
If xx = "0" Then
If mcd = "1" Then
ax = a: bx = b: mx = m
Else
x(2) = mcd
x(1) = a: rr() = DivisionEuclidea(x(), n): ax =
rr(1)
x(1) = b: rr() = DivisionEuclidea(x(), n): bx =
rr(1)
x(1) = m: rr() = DivisionEuclidea(x(), n): mx =
rr(1)
End If
If Left$(ax, 1) = "-" Then
ax = Mid$(ax, 1)
If Left$(bx, 1) = "-" Then bx = Mid$(bx, 1) Else bx =
"-" + bx
End If
fr() = FrContFrCg(ax, mx)
d = UBound(fr())
ReDim p(d), q(d)
p(0) = fr(0): q(0) = "1"
x(1) = fr(0): x(2) = fr(1)
x(1) = Multiplicar(x(), n): x(2) = "1"
p(1) = Sumar(x(), n): q(1) = fr(1)
For i = 2 To d
x(1) = fr(i): x(2) = p(i – 1)
x(1) = Multiplicar(x(), n): x(2) = p(i –
2)
p(i) = Sumar(x(), n)
x(1) = fr(i): x(2) = q(i – 1)
x(1) = Multiplicar(x(), n): x(2) = q(i –
2)
q(i) = Sumar(x(), n)
Next i
x(1) = bx: x(2) = q(d – 1)
xx = Multiplicar(x(), n)
t = (d + 1) Mod 2
If t = 1 Then
If Left$(xx, 1) = "-" Then xx = Mid$(xx, 1) Else xx =
"-" + xx
End If
ReDim s(mcd)
s(1) = xx
x(1) = s(1): x(2) = mx: rr() = DivisionEuclidea(x(),
n)
If rr(2) = "-0" Then rr(2) = "0"
s(1) = rr(2)
Do
If Left$(s(1), 1) = "-" Then
x(1) = s(1): x(2) = mx: s(1) = Sumar(x(),
n)
Else
Exit Do
End If
Loop
If mcd <> "1" Then
k = "1"
Do
x(1) = k: x(2) = "1": k = Sumar(x(),
n)
x(1) = s(k – 1): x(2) = mx: s(k) = Sumar(x(),
n)
Loop Until k = mcd
End If
k = "0": rs = ""
Do
x(1) = k: x(2) = "1": k = Sumar(x(),
n)
rs = rs + rc + "x(k) = " + s(k) + " + k*" +
m
Loop Until k = mcd
Else
rs = "No hay soluciones"
End If
MFrContCg = rs
End Function
Public Function FrContFrCg(ByVal a0 As String, ByVal
b0 As String) As Variant
" — Desarrollo de una fracción ordinaria en
fracción continua, operando con enteros
largos
Dim i As Long, j As Long, xx As String, n As
Integer
Dim ax As String, bx As String, q0 As String, q() As
String
Dim x(2) As String, rr() As String, d As
Long
n = 7: i = 0
If Left$(a0, 1) = "-" Then ax = Mid$(a0, 1) Else ax =
a0
If Left$(b0, 1) = "-" Then bx = Mid$(b0, 1) Else bx =
b0
Do
x(1) = ax: x(2) = bx
rr() = DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
qx = rr(1): rx = rr(2)
i = i + 1
q0 = q0 + qx + ","
If rx <> "0" Then
ax = bx: bx = rx
Else
Exit Do
End If
Loop
d = i – 1: j = 0
ReDim q(d)
Do
For i = 1 To Len(q0)
xx = Left$(q0, i)
If Right$(xx, 1) = "," Then
q(j) = Left$(xx, Len(xx) – 1)
q0 = Mid$(q0, i + 1)
Exit For
End If
Next i
If q0 = "" Then Exit Do
j = j + 1
Loop
FrContFrCg = q()
End Function
Ejemplo 12: Utilizando el método anterior,
resolver la congruencia siguiente:
La solución es La función "MetodoFrc" no podría
resolver la congruencia puesto que su módulo no puede ser
almacenado en variables de tipo Long. Los dos programas
"CongruenciasD" o "CongruenciasE" probablemente tardarían
mucho para dar este resultado.
Ejemplo 13: Resolver la congruencia
siguiente:
Según la función FrContFrCg, las
soluciones son:
§4.
Resolución de congruencias de grado
superior.
Las congruencias de grado superior tienen la forma
siguiente:
(7)
, donde los coeficientes del polinomio son enteros y el
modulo es un
número natural mayor que 1. Las soluciones se buscan en el
conjunto de los números enteros.
Hay que observar que si el máximo común
divisor de los enteros no divide al coeficiente entonces la congruencia no
tiene solución.
A continuación no se van a exponer los detalles
de la teoría de este tipo de congruencias (se puede
consultar la bibliografía). Se establecerán
solamente programas en el lenguaje Visual-Basic, para hallar sus
soluciones (cuando existen), utilizando el método directo,
es decir seleccionando entre los números de 1 a a aquellos que son
soluciones de la congruencia (7). Si es una solución de la congruencia (7),
obviamente serán soluciones también todos los
números naturales de la forma
Public Function CongrGrS(ByRef p() As Long, ByVal m As
Long) As string
Dim i As Integer, j As Integer, k As Integer, gp As
Integer, rs As String
Dim x As Long, y As Long, z As Long, r As Long, mcd As
Long
Dim s0() As Long, p0() As Long
gp = UBound(p())
' Si el m.c.d. de los primeros gp-1 coeficientes y del
módulo no divide al término libre, no hay
solución
i = 0: x = Abs(p(0))
Do
i = i + 1
If i < gp Then y = Abs(p(i)) Else y = m
If y <> 0 Then
Do
If x < y Then z = x: x = y: y = z
r = x Mod y
If r = 0 Then Exit Do
x = y: y = r
Loop
x = y
End If
Loop While i <= gp – 1
mcd = y
y = p(gp) Mod mcd
If y = 0 Then
If mcd = 1 Then
m0 = m: p0() = p()
Else
m0 = m / mcd
ReDim p0(gp)
For i = 0 To gp
p0(i) = p(i) / mcd
Next i
End If
' ——— SOLUCIÓN
——————–
ReDim s0(m0)
For j = 0 To m0 – 1
x = 0
If j = 0 Then
x = p0(gp) Mod m0
Else
x = p0(0) Mod m0
For i = 1 To gp
x = x * j + p0(i)
x = x Mod m0
Next i
End If
If x = 0 Then
k = k + 1
s0(k) = j
End If
Next j
End If
If k <> 0 Then
For i = 1 To k
rs = rs + rc + "x(" + Str$(i) + ") = " + Str$(s0(i)) + "
+ k*" + Str$(k)
Next i
Else
rs = "No hay soluciones"
End If
CongrGrS = rs
End Function
Ejemplo 14: Según el programa anterior,
las soluciones de la congruencia
, son las siguientes: y
Sin embargo La función CongrGrS no sirve si los
coeficientes del polinomio ó el modulo son enteros muy
largos. Para estos casos hay que utilizar la función
siguiente, que puede operar con enteros largos:
Public Function CongrGrSEG(ByRef p() As String, ByVal m
As String) As String
Dim i As Integer, j As String, k As Integer, gp As
Integer, rt As String, rr() As String, rs As string
Dim xx As String, yy As String, zz As String, r As
String, mcd As String, dif As String, dif1 As String
Dim s0() As String, p0() As String, x(2) As String, m0
As String, n As Integer
n = 7: gp = UBound(p())
If Left$(p(0), 1) = "-" Then xx = Mid$(p(0), 2) Else xx
= p(0)
' Si el m.c.d. de los primeros gp-1 coeficientes y del
módulo no divide al término libre, no hay
solución
i = 0
Do
i = i + 1
If i < gp Then
If Left$(p(i), 1) = "-" Then yy = Mid$(p(i), 2) Else yy
= p(i)
Else
yy = m
End If
If yy <> "0" Then
Do
x(1) = xx: x(2) = yy: rt = Restar(x(), n)
If Left$(rt, 1) = "-" Then zz = xx: xx = yy: yy =
zz
x(1) = xx: x(2) = yy: rr() = DivisionEuclidea(x(), n): r
= rr(2)
If r ="-0" then r = "0"
If r = "0" Then Exit Do
xx = yy: yy = r
Loop
xx = yy
End If
Loop While i <= gp – 1
mcd = yy
x(1) = p(gp): x(2) = mcd: rr() = DivisionEuclidea(x(),
n)
If rr(2) ="-0" then rr(2) = "0"
yy = rr(2)
If yy = "0" Then
If mcd = "1" Then
m0 = m: p0() = p()
Else
x(1) = m: x(2) = mcd: rr() = DivisionEuclidea(x(), n):
m0 = rr(1)
ReDim p0(gp)
For i = 0 To gp
x(1) = p(i): x(2) = mcd: rr() = DivisionEuclidea(x(),
n): p0(i) = rr(1)
Next i
End If
'' ——- SOLUCIÓN ————-'
ReDim s0(m0) " m0 no puede ser muy grande
j = "0": k=0: x(1) = m0: x(2) = "1": dif = Restar(x(),
n)
Do
xx = "0"
If j = 0 Then
x(1) = p0(gp): x(2) = m0: rr() = DivisionEuclidea(x(),
n)
If rr(2) ="-0" then rr(2) = "0"
xx = rr(2)
Else
x(1) = p0(0): x(2) = m0: rr() = DivisionEuclidea(x(),
n)
If rr(2) ="-0" then rr(2) = "0"
xx = rr(2)
For i = 1 To gp
x(1) = xx: x(2) = j: rt = Multiplicar(x(), n)
x(1) = rt: x(2) = p0(i): xx = Sumar(x(), n)
x(1) = xx: x(2) = m0: rr() = DivisionEuclidea(x(),
n)
If rr(2) ="-0" then rr(2) = "0"
xx = rr(2)
Next i
End If
If xx = "0" Or xx = "-0" Then
k = k + 1
s0(k) = j
End If
x(1) = j: x(2) = "1": j = Sumar(x(), n)
x(1) = dif: x(2) = j: dif1 = Restar(x(), n)
Loop While Left$(dif1, 1) <> "-"
End If
If k <> 0 Then
For i = 1 To k
rs = rs + rc + "x(" + Str$(i) + ") = " + s0(i) + " + k*"
+ m0
Next i
Else
rs = "No hay soluciones"
End If
CongrGrSEG = rs
End Function
Ejemplo 15: Utilizando la función
CongrGrSEG, las soluciones de la congruencia
siguiente:
, son y
Ejemplo 16: Utilizando el mismo código que
en el ejemplo11, se obtiene que la congruencia
, tiene las soluciones siguientes:
Para que el último programa funcione, los
coeficientes del polinomio pueden ser enteros bastante largos
pero el módulo no. Según un teorema de Lagrange
[8], si m es un número primo el número de las
soluciones es inferior o igual al grado del polinomio. Si m no es
primo pueden haber hasta m soluciones y, si m es grande, no se
podría dimensionar una matriz s0() que contenga las
soluciones [utilizando la instrucción: ReDim s0(m)]. En
este último caso sería preferible presentar las
soluciones en una variable de tipo String, separadas por comas, y
no como elementos de una matriz. El programa anterior se puede
modificar en este sentido:
Public Function CongrGrSEGB(ByRef p() As String, ByVal m
As String) As String
Dim i As Integer, j As String, k As Integer, gp As
Integer, rt As String, rr() As String, rs As String
Dim xx As String, yy As String, zz As String, r As
String, mcd As String, dif As String, dif1 As String
Dim s0 As String, s() As String, p0() As String, x(2) As
String, m0 As String, n As Integer
n = 7: gp = UBound(p())
If Left$(p(0), 1) = "-" Then xx = Mid$(p(0), 2) Else xx
= p(0)
' ¿Pueden existir soluciones?
i = 0
Do
i = i + 1
If i < gp Then
If Left$(p(i), 1) = "-" Then yy = Mid$(p(i), 2) Else yy
= p(i)
Else
yy = m
End If
If yy <> "0" Then
Do
x(1) = xx: x(2) = yy: rt = Restar(x(), n)
If Left$(rt, 1) = "-" Then zz = xx: xx = yy: yy =
zz
x(1) = xx: x(2) = yy: rr() = DivisionEuclidea(x(),
n)
r = rr(2)
If r = "0" Then Exit Do
xx = yy: yy = r
Loop
xx = yy
End If
Loop While i <= gp – 1
mcd = yy
x(1) = p(gp): x(2) = mcd: rr() = DivisionEuclidea(x(),
n)
If rr(2) = "-0" Then rr(2) = "0"
yy = rr(2)
If yy = "0" Then
If mcd = "1" Then
m0 = m: p0() = p()
Else
x(1) = m: x(2) = mcd: rr() = DivisionEuclidea(x(), n):
m0 = rr(1)
ReDim p0(gp)
For i = 0 To gp
x(1) = p(i): x(2) = mcd: rr() = DivisionEuclidea(x(),
n): p0(i) = rr(1)
Next i
End If
' ———— SOLUCIÓN
——————-
j = "0": s0 = "": k = 0: x(1) = m0: x(2) = "1": dif =
Restar(x(), n)
Do
xx = "0"
If j = 0 Then
x(1) = p0(gp): x(2) = m0: rr() = DivisionEuclidea(x(),
n)
If rr(2) = "-0" Then rr(2) = "0"
xx = rr(2)
Else
x(1) = p0(0): x(2) = m0: rr() = DivisionEuclidea(x(),
n)
If rr(2) = "-0" Then rr(2) = "0"
xx = rr(2)
For i = 1 To gp
x(1) = xx: x(2) = j: rt = Multiplicar(x(), n)
x(1) = rt: x(2) = p0(i): xx = Sumar(x(), n)
x(1) = xx: x(2) = m0: rr() = DivisionEuclidea(x(),
n)
If rr(2) = "-0" Then rr(2) = "0"
xx = rr(2)
Next i
End If
If xx = "-0" Then xx = "0"
If xx = "0" Then
k = k + 1
s0 = s0 + j + " , "
End If
x(1) = j: x(2) = "1": j = Sumar(x(), n)
x(1) = dif: x(2) = j: dif1 = Restar(x(), n)
Loop While Left$(dif1, 1) <> "-"
End If
If k <> 0 Then
rs = "x = " + Left$(s0, Len(s0) – 5) + " mod (" + m0 +
")"
Else
rs = "No hay soluciones"
End If
CongrGrSEGB = rs
End Function
Ejemplo 17: En el caso de la
congruencia
El programa anterior da las soluciones:
Es evidente que en este caso no era conveniente utilizar
una matriz con 2374586 elementos para que al final contenga solo
tres elementos. De todos modos, trabajando el ordenador a tres
GHz, el resultado ha tardado en aparecer alrededor de 5-6
minutos. Si el módulo sería todavía mas
grande, el tiempo de ejecución aumentaría mucho. Si
en el ejemplo anterior se añadiría otra cifra
más, el tiempo de ejecución podría alargarse
fácilmente hasta una hora. En consecuencia, los
coeficientes del polinomio pueden ser bastante grandes pero si el
módulo tiene más de 6-7 cifras, la
resolución de la congruencia tardaría
demasiado.
§5. Sistemas
de congruencias de primar grado.
Un sistema de congruencias de grado 1 tiene la forma
siguiente:
(8)
El sistema (8) no siempre tiene soluciones. Las razones
pueden ser distintas: o bien algunas congruencias no tienen
solución o bien la solución de una no es
solución de alguna de las otras.
Existe un teorema de un autor chino que afirma lo
siguiente:
Teorema 7 (chino): Si los módulos
son dos a dos
primos relativos y, entonces el sistema tiene solución única respecto
al módulo
El teorema 6 será consecuencia del teorema 7", en
el caso
Teorema 7": Si los módulos son dos a dos primos
relativos y son
también primos relativos, entonces el sistema (8) tiene
solución única respecto al módulo
En efecto, puesto que los números y el número son primos relativos, la
congruencia tiene
la solución según el teorema de Euler. Esto es la
única solución de esta congruencia puesto que si
tuviésemos también resultaría que Luego, teniendo en cuenta que son primos relativos, de
aquí se obtiene que Obviamente, , donde si e si Así es solución del sistema (8) puesto
que
, cualquiera que sea es decir es solución de la congruencia (8). Si
fuera otra
solución entonces, según la propiedad 10,
resultaría que
Teorema 8: Si en el sistema de congruencias (8)
son primos
relativos y son dos
soluciones distintas del sistema, entonces donde M es el mínimo
común múltiplo de los módulos. En efecto si
entonces
y
Así de donde resulta que es un divisor de la diferencia Puesto que primos relativos resulta que
Por consiguiente el teorema
(8) se cumple para Suponiendo que se cumple para esto significa que Luego son soluciones
también de la congruencia lo que implica que Puesto que el mínimo común
múltiplo de y del módulo esresulta que es decir el teorema se cumple también en
el caso Por
consiguiente el teorema queda demostrado por inducción
completa.
Para resolver el sistema (8) se puede proceder de la
manera siguiente: En cada congruencia se calcula el máximo
común divisor de de Si en alguna congruencia del sistema, no divide el número
el sistema no tiene
solución. En el caso contrario en cada congruencia se
dividen los números entre obteniendo el sistema equivalente
siguiente:
(8")
Luego, se resuelve la primera congruencia del sistema
(8"). Si esta solución es luego entre los valores se busca una solución que verifique la segunda
congruencia. Si no hay tal solución el sistema no tiene
solución. En el caso contrario la solución del
sistema formado de las primeras dos congruencias será
Luego, entre
se busca a aquella
solución del
sistema, formado da las primeras dos congruencias de (8"), que
verifique la tercera congruencia. Si no existe el sistema (8") no tiene
solución En el caso contrario, según el teorema (8)
la solución del sistema formado por las primera tres
congruencias de (8") será Continuando este proceso o bien se obtiene que
el sistema (8") no tiene solución, o bien se obtiene su
solución respecto al módulo
Ejemplo 18: Resolver el sistema de congruencias
por el método anterior:
(9)
La resolución del sistema (9) se reduce a la
resolución del sistema (9"):
(9")
La solución de la primera congruencia es
Entre los valores
0, 3, 6, el número 3 es solución del sistema
formado de las primeras dos congruencias. Luego el valor 3 es el
número que verifica el sistema (9"). Por tanto la
solución del sistema es 6. Respecto al módulo el sistema tiene las
soluciones: y
Siguiendo el método expuesto en el ejemplo 14,
para le resolución de los sistemas de congruencias en el
ordenador se puede utilizar el código Visual-Basic
siguiente:
Public Function RSC1(ByRef a0() As Long, ByRef b0() As
Long, ByRef m0() As Long) As String
Dim i As Long, j As Integer, n As Long, u() As Long, x
As Long, kk as integer
Dim mcd() As Long, mcm() As Long, k As Integer, ui As
Long, xy As Long
Dim rc As String, y As Long, w As Long, m() As Long, a()
As Long
Dim sw As Integer, res As String, xx() As Long, b() As
Long
rc = Chr$(13) + Chr$(10): m() = m0(): a() = a0(): b() =
b0(): n = UBound(a0())
ReDim mcd(n), mcm(n), u(n), resultado(2),
xx(n)
' Cambios para que la primera congruencia tenga el menor
módulo.
For i = 2 To n
If m(i) < m(1) Then
xy = m(1): m(1) = m(i): m(i) = xy
xy = a(1): a(1) = a(i): a(i) = xy
xy = b(1): b(1) = b(i): b(i) = xy
End If
Next i
' ¿Tienen soluciones las congruencias del
sistema?
For i = 1 To n
mcd(i) = MaxComDivC(a(i), m(i))
x = b(i) Mod mcd(i)
If x <> 0 And mcd(i) <> 1 Then
RSC1 = "No hay solución"
Exit Function
End If
Next i
For i = 1 To n
If mcd(i) <> 1 Then
a(i) = a(i) / mcd(i): b(i) = b(i) / mcd(i): m(i) = m(i)
/ mcd(i)
End If
Next i
' Resolución de la primera congruencia (cuyo
módulo es menor)
a(1) = a(1) Mod m(1): b(1) = b(1) Mod m(1)
For i = 1 To m(1) – 1
x = (a(1) * i – b(1)) Mod m(1)
If x = 0 Then k = i: Exit For
Next i
'Resolución del sistema
u(1) = k: mcm(1) = m(1)
For i = 2 To n
mcm(i) = MinComMultC(mcm(i – 1), m(i))
For j = u(i – 1) To mcm(i) Step m(i – 1)
sw = 0
For kk = 1 To i – 1: xx(kk) = 0: Next kk
For kk = 1 To i
xx(kk) = (a(kk) * j – b(kk)) Mod m(kk)
Next kk
For kk = 1 To i
If xx(kk) <> 0 Then sw = 1: Exit For
Next kk
If sw = 0 Then
u(i) = j: sw = 0: Exit For
End If
Next j
If sw = 1 Then
RSC1 = " No hay solución"
Exit Function
End If
If i = n Then Exit For
Next i
' Presentación del resultado
ui = u(i): res = "Solución: " + rc
res = res + "x = " + Str$(ui) + " + " + "k*" +
Str$(mcm(n))
w = MinComMultC(m0(1), m0(2))
For i = 3 To n
w = MinComMultC(w, m0(i))
Next i
If ui + mcm(n) < w Then
res = res + rc
res = res + rc + "Soluciones respecto al módulo:
" + Str$(w) + rc
i = 0: sw = 0
Do
y = ui + i * mcm(n): res = res + "x = " + Str$(y) + " +
k*" + Str(w) + rc
i = i + 1
Loop While y + mcm(n) < w
End If
RSC1 = res
End Function
Public Function MaxComDiv3(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
MaxComDivC3 = bx
End Function
Public Function MinComMult3(ByVal a As Long, ByVal b As
Long) As Long
MinComMult3 = Abs(a * b) / MaxComDiv3(a, b)
End Function
Ejemplo 19: Aplicando el código expuesto
anteriormente al sistema:
(10)
, se obtiene la solución Respecto el módulo las soluciones son:
La function RSC1 tiene suslimitaciones puesto que los
coeficientes del sistema y los números que aparecen
durante el cálculo se almacenan en variables de tipo Long.
A continuación se presentan dos funciones que hacen los
mismo que la Función RSC1 pero trabajan con variables de
tipo String y son capaces de almacenar números enteros muy
largos. La Función RSC2 se basa en el método
directo y la segunda usa el me´todo de las fracciones
continuas;
Public Function RSC2(ByRef a0() As String, ByRef b0() As
String, ByRef m0() As String) As String
Dim i As String, ii As Integer, j As String, n As
Integer, nc As Integer
Dim mcd() As String, x(2) As String, k As String, kk As
Integer
Dim mcm() As String, ui As String, v1 As String, rr() As
String
Dim a() As String, b() As String, m() As String, u() As
String
rc = Chr$(13) + Chr$(10): a() = a0(): b() = b0(): m() =
m0()
n = 7: nc = UBound(a0())
If nc = 1 Then
MsgBox "El sistema debe tener más de una
congruencia"
End
End If
ReDim mcd(nc), u(nc), xx(nc), mcm(nc)
For kk = 1 To nc
x(1) = a(kk): x(2) = m(kk)
mcd(kk) = MaxComDiv(x(), n)
x(1) = b(kk): x(2) = mcd(kk): rr() =
DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
If rr(2) <> "0" And mcd(kk) <> "1"
Then
RSC2 = "No hay solución"
Exit Function
End If
Next kk
For kk = 1 To nc
If mcd(kk) <> "1" Then
x(1) = a(kk): x(2) = mcd(kk): rr() =
DivisionEuclidea(x(), n): a(kk) = rr(1)
x(1) = b(kk): x(2) = mcd(kk): rr() =
DivisionEuclidea(x(), n): b(kk) = rr(1)
x(1) = m(kk): x(2) = mcd(kk): rr() =
DivisionEuclidea(x(), n): m(kk) = rr(1)
End If
Next kk
' Resolución de la primera congruencia por el
método directo.
x(1) = a(1): x(2) = m(1): rr() = DivisionEuclidea(x(),
n)
If rr(2) = "-0" Then rr(2) = "0"
a(1) = rr(2)
x(1) = b(1): x(2) = m(1): rr() = DivisionEuclidea(x(),
n)
If rr(2) = "-0" Then rr(2) = "0"
b(1) = rr(2)
i = "0": x(1) = m(1): x(2) = "1": v = Restar(x(),
n)
Do
x(1) = i: x(2) = "1": i = Sumar(x(), n)
x(1) = a(1): x(2) = i: y = Multiplicar(x(),
n)
x(1) = y: x(2) = b(1): y = Restar(x(), n)
x(1) = y: x(2) = m(1): rr() = DivisionEuclidea(x(),
n)
If rr(2) = "-0" Then rr(2) = "0"
If rr(2) = "0" Then k = i: Exit Do
x(1) = i: x(2) = v: v1 = Restar(x(), n)
Loop While Left$(v1, 1) = "-" Or v1 = "0"
'Resolución del sistema
u(1) = k: mcm(1) = m(1)
For ii = 2 To nc
x(1) = mcm(ii – 1): x(2) = m(ii): mcm(ii) =
MinComMult(x(), n)
Next ii
For ii = 2 To nc
j = u(ii – 1)
Do
For kk = 1 To ii: xx(kk) = "0": Next kk
sw = 0
For kk = 1 To ii
x(1) = a(kk): x(2) = j: xx(kk) = Multiplicar(x(),
n)
x(1) = xx(kk): x(2) = b(kk): xx(kk) = Restar(x(),
n)
x(1) = xx(kk): x(2) = m(kk): rr() =
DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
xx(kk) = rr(2)
Next kk
For kk = 1 To ii
If xx(kk) <> "0" Then sw = 1: Exit For
Next kk
If sw = 0 Then
u(ii) = j: sw = 0: Exit Do
End If
x(1) = j: x(2) = m(ii – 1): j = Sumar(x(), n)
x(1) = j: x(2) = mcm(ii): dif = Restar(x(),
n)
Loop While Left$(dif, 1) = "-" Or dif = "0"
If sw = 1 Then
RSC2 = " No hay solución"
Exit Function
End If
If ii = nc Then Exit For
Next ii
' Presentación del resultado
ui = u(ii): res = "Solución: " + rc
es = res + "x = " + ui + " + " + "k*" +
mcm(nc)
RSC2 = res
End Function
Ejemplo 20: El sistema de congruencias siguiente
no puede ser resuelto utilizando la función "RSC1" puesto
que sus coeficientes no pueden ser almacenados en variables de
tipo Long.
(11)
Para esto se puede servir de la función "RSC2",
que trabaja con números enteros almacenados en variables
de tipo String. Con esta función se obtiene la siguiente
solución del sistema (11):
Public Function RSCFRC(ByRef a0() As String, ByRef b0()
As String, ByRef m0() As String) As String
Dim i As String, ii As Integer, j As String, n As
Integer, nc As Integer, u() As String, y As String
Dim mcd() As String, mcm() As String, x(2) As String, k
As String, kk As Integer, ui As String
Dim rc As String, w As String, m() As String, a() As
String, dif As String, v1 As String
Dim sw As Integer, res As String, xx() As String, b() As
String, rr() As String, fr() As String
rc = Chr$(13) + Chr$(10): a() = a0(): b() = b0(): m() =
m0()
n = 7: nc = UBound(a0())
ReDim mcd(nc), mcm(nc), u(nc), resultado(2),
xx(nc)
For kk = 1 To nc
x(1) = a(kk): x(2) = m(kk)
mcd(kk) = MaxComDiv(x(), n)
x(1) = b(kk): x(2) = mcd(kk): rr() =
DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
If rr(2) <> "0" And mcd(kk) <> "1"
Then
RSCFRC = "No hay solución"
Exit Function
End If
Next kk
For kk = 1 To nc
If mcd(kk) <> "1" Then
x(1) = a(kk): x(2) = mcd(kk): rr() =
DivisionEuclidea(x(), n): a(kk) = rr(1)
x(1) = b(kk): x(2) = mcd(kk): rr() =
DivisionEuclidea(x(), n): b(kk) = rr(1)
x(1) = m(kk): x(2) = mcd(kk): rr() =
DivisionEuclidea(x(), n): m(kk) = rr(1)
End If
Next kk
' Resolución de la primera congruencia por el
método de las fracciones continuas
fr() = FrContFrCg(a(1), m(1))
d = UBound(fr())
ReDim p(d), q(d)
p(0) = fr(0): q(0) = "1"
x(1) = fr(0): x(2) = fr(1)
x(1) = Multiplicar(x(), n): x(2) = "1"
p(1) = Sumar(x(), n): q(1) = fr(1)
For ii = 2 To d
x(1) = fr(ii): x(2) = p(ii – 1)
x(1) = Multiplicar(x(), n): x(2) = p(ii – 2)
p(ii) = Sumar(x(), n)
x(1) = fr(ii): x(2) = q(ii – 1)
x(1) = Multiplicar(x(), n): x(2) = q(ii – 2)
q(ii) = Sumar(x(), n)
Next ii
x(1) = b(1): x(2) = q(d – 1)
xy = Multiplicar(x(), n)
t = (d + 1) Mod 2
If t = 1 Then
If Left$(xy, 1) = "-" Then xy = Mid$(xy, 1) Else xy =
"-" + xy
End If
x(1) = xy: x(2) = m(1): rr() = DivisionEuclidea(x(),
n)
If rr(2) = "-0" Then rr(2) = "0"
u(1) = rr(2): mcm(1) = m(1)
For ii = 2 To nc
x(1) = mcm(ii – 1): x(2) = m(ii)
mcm(ii) = MinComMult(x(), n)
j = u(ii – 1)
Do
For kk = 1 To ii – 1: xx(kk) = "0": Next kk
sw = 0
For kk = 1 To ii
x(1) = a(kk): x(2) = j: xx(kk) = Multiplicar(x(),
n)
x(1) = xx(kk): x(2) = b(kk): xx(kk) = Restar(x(),
n)
x(1) = xx(kk): x(2) = m(kk): rr() =
DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
xx(kk) = rr(2)
Next kk
For kk = 1 To ii
If xx(kk) <> "0" Then sw = 1: Exit For
Next kk
If sw = 0 Then
u(ii) = j: sw = 0: Exit Do
End If
x(1) = j: x(2) = m(ii – 1): j = Sumar(x(), n)
x(1) = j: x(2) = mcm(ii): dif = Restar(x(),
n)
Loop While Left$(dif, 1) = "-" Or dif = "0"
If sw = 1 Then
RSCFRC = " No hay solución"
Exit Function
End If
If ii = nc Then Exit For
Next ii
' Presentación del resultado
ui = u(ii): res = "Solución: " + rc
res = res + "x = " + ui + " + " + "k*" +
mcm(nc)
RSCFRC = res
End Function
Ejemplo 21: Resolver el sistema de
congruencias:
Utilizando las funciones RSC2 o RSCFRC, la
solución es:
§6. Sistemas
de congruencias de grado superior.
Este tipo de sistemas de congruencias tienen la forma
siguiente:
(12)
Para que el sistema tenga soluciones cada congruencia
debe tener soluciones y tienen que existir soluciones comunes.
Primero hay que resolver la congruencia de menor módulo y
luego hay que comprobar ¿cuáles de sus soluciones
son soluciones de las otras congruencias? Si la primera
congruencia no tuviera el menor módulo, hay que cambiar el
sistema tal que la congruencia de menor módulo sea la
primera congruencia del sistema (esto es importante puesto que
las soluciones de la primera congruencia se buscarán por
el método directo, es decir, comprobando
¿cuáles de los números de cero hasta el
módulo son soluciones.
La función siguiente devuelve las soluciones de
los sistemas de congruencias de grado superior (siempre y cuando
los datos introducidos y los números que intervienen en
los cálculos pueden ser almacenados en variables de tipo
Long):
Public Function SCNL(ByRef sist() As String, ByVal mdls
As String, ByVal nc As Integer) As String
Dim p() As Long, gp As Integer, gs As Integer, m As
Long, m0() As Long, gpol() As Integer
Dim i As Integer, mcd() As Long, p0() As Long, s0() As
Long, s1() As Long, rc As String
Dim z As Long, r As Long, rs As String, ns As Integer,
sw As Integer, j As Integer
Dim res As String, ui As Long, s2() As Long, kk As
Integer, xy As String, ii As Long
Dim w As Long, w1 As Long, vp0 As Long, vp00 As Long,
vp() As Long, q() As Long, pol() As Long
Dim x As Long, y As Long, k As Integer, mcm() As Long,
mo() As Long, rr() As Long
rc = Chr$(13) + Chr$(10)
ReDim mo(nc)
rr() = RutinaCoeficientes(mdls)
rr(0) = rr(0)
For i = 1 To nc
mo(i) = rr(i – 1)
Next i
'——— Cambios para que la primera congruencia tenga
el módulo menor.
For i = 2 To nc
If mo(i) < mo(1) Then
xy = mo(1): mo(1) = mo(i): mo(i) = xy
xy = sist(1): sist(1) = sist(i): sist(i) = xy
End If
Next i
ReDim gpol(nc)
gs = 0
For j = 1 To nc
pol() = RutinaCoeficientes(sist(j))
gpol(j) = UBound(pol())
If gpol(j) > gs Then gs = gpol(j)
Next j
ReDim p(gs, nc)
For i = 1 To nc
pol() = RutinaCoeficientes(sist(i))
For j = 0 To gpol(i)
p(j, i) = pol(j)
Next j
Next i
' El sistema ¿puede tener soluciones?
ReDim mcd(nc)
For i = 1 To nc
x = Abs(p(0, i))
For j = 1 To gpol(i)
If j < gpol(i) Then y = Abs(p(j, i)) Else y =
mo(i)
If y <> 0 Then x = MaxComDivC(x, y)
Next j
mcd(i) = x
y = p(gpol(i), i) Mod mcd(i)
If y <> 0 Then
SCNL = "No hay soluciones"
Exit Function
End If
Next i
ReDim p0(gs, nc), m0(nc)
For i = 1 To nc
If mcd(i) = 1 Then
m0(i) = mo(i)
For j = 0 To gpol(i)
p0(j, i) = p(j, i)
Next j
Else
m0(i) = mo(i) / mcd(i)
For j = 0 To gpol(i)
p0(j, i) = p(j, i) / mcd(i)
Next j
End If
Next i
'——– Resolución de la congruencia de
módulo menor.
ReDim s0(m0(1))
For j = 0 To m0(1) – 1
x = 0
If j = 0 Then
x = p0(gpol(1), 1) Mod m0(1)
Else
x = p0(0, 1) Mod m0(1)
For i = 1 To gpol(1)
x = (x * j) Mod m0(1)
x = (x + p0(i, 1)) Mod m0(1)
Next i
End If
If x = 0 Then
k = k + 1
s0(k) = j
End If
Next j
ns = k
If ns <> 0 Then
ReDim s1(ns), s2(ns), vp(nc), mcm(nc)
For i = 1 To ns: s1(i) = s0(i): Next i
ReDim s2(m0(1))
w = MinComMultC(mo(1), mo(2))
For i = 3 To nc
w = MinComMultC(w, mo(i))
Next i
For i = 1 To ns: s1(i) = s0(i): Next i
mcm(1) = m0(1)
For i = 2 To nc
mcm(i) = MinComMultC(mcm(i – 1), m0(i))
Next i
w = MinComMultC(mo(1), mo(2))
For i = 3 To nc
w = MinComMultC(w, mo(i))
Next i
kk = 0
For k = 1 To ns
ii = 0
For i = 2 To nc
ReDim q(gpol(i))
q(0) = p(0, i)
Do
vp0 = s1(k) + ii * m0(1): vp00 = vp0 Mod
mo(i)
For j = 1 To gpol(i)
q(j) = vp0 * q(j – 1) Mod mo(i)
q(j) = q(j) + p(j, i) Mod mo(i)
Next j
vp(i) = q(gpol(i)) Mod m0(i)
If vp(i) = 0 Then Exit Do
ii = ii + 1
Loop While vp0 < mcm(i) + m0(1)
Next i
For i = 2 To nc
If vp(i) <> 0 Then sw = 1
Next i
If sw = 0 Then
If vp0 <> s2(kk) Or kk = 0 Then
kk = kk + 1: s2(kk) = vp0
End If
Else
sw = 0
End If
Next k
If kk = 0 Then
SCNL = "No hay soluciones"
Exit Function
End If
'Ordenación de las soluciones
For i = 1 To kk
For j = i + 1 To kk
If s2(i) > s2(j) Then
z = s2(i): s2(i) = s2(j): s2(j) = z
End If
Next j
Next i
'Edición de los resultados
res = "Soluciónes: " + rc + rc
For i = 1 To kk
ui = s2(i)
res = res + "x = " + Str$(ui) + " + " + "k*" +
Str$(mcm(nc)) + rc
Next i
If mcm(nc) < w Then
res = res + rc + "Soluciones respecto al módulo:
" + Str$(w) + rc
res = res + rc
For i = 1 To kk
ui = s2(i): ii = 0
Do
y = ui + ii * mcm(nc)
res = res + "x = " + Str$(y) + " + k*" + Str(w) +
rc
ii = ii + 1
Loop While y + mcm(nc) < w
res = res + rc: y = 0
Next i
End If
Else
res = "No hay soluciones"
End If
SCNL = res
End Function
Public Function MaxComDivC(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 = a: bx = 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
MaxComDivC = bx
End Function
Public Function MinComMultC(ByVal a As Long, ByVal b As
Long) As Long
MinComMultC = (a * b) / MaxComDivC(a, b)
End Function
Public Function RutinaCoeficientes(ByVal t As String) As
Variant
Dim i As Integer, j As Integer, k As Integer, lt As
Integer
Dim i0 As Integer, nco As Integer, gp As
Integer
Dim bb As String, px() As Long
'—- Número de las comas en la cadena
t
If Right$(t, 1) <> "," Then t = t + ","
k = 1: lt = Len(t): nco = 0
Do
bb = Right$(Left$(t, k), 1)
If bb = "," Then
nco = nco + 1
End If
k = k + 1
If k > lt Then Exit Do
Loop
gp = nco – 1
'— Separación de los coeficientes
ReDim px(gp)
k = 1: i = 1: i0 = 0: j = 0
Do
bb = Right$(Left$(t, k), 1)
If bb = "," Then
j = j + 1
px(i0) = Val(Left$(t, k – 1))
i = i + 1: i0 = i0 + 1
t = Mid$(t, k + 1)
k = 1
Else
k = k + 1
End If
If j = nco Then Exit Do
Loop
RutinaCoeficientes = px()
End Function
Ejemplo 22: Para resolver el sistema de
congruencias:
, por el código anterior, hay que suministrar los
argumentos siguientes:
El resultado será:
Ejemplo 23: Resolver el sistema:
Se observa que todos los coeficientes y el módulo
de la primera congruencia del sistema son múltiplos de 2.
Al dividir en la primera congruencia los coeficientes y el
módulo entre 2, la resolución del sistema se reduce
a la resolución del sistema del ejemplo 21. Por tanto la
solución del sistema del ejemplo 21 es la misma que la del
ejemplo 21, respecto al módulo 555.
El mínimo común múltiplo de los
módulo 74 y 15 es 1110 y respecto a este módulo la
soluciones distintas son las siguientes:
Cuando algunos de los coeficientes del sistema o los
resultados intermedios de los cálculos no pueden ser
almacenados en variables de tipo Long, para resolver el sistema
hay que recurrir al programa siguiente que trabaja con variables
de tipo string, utilizando las funciones Multiplicar, Sumar,
Restar, DivisionEuclidea, MaxComDiv, MinComMult (expuestas en
[11]):
Public Function SCNLNG(ByRef sist() As String, ByVal
mdls As String, nc As Integer) As String
Dim p() As String, gp As Integer, gs As Integer, m As
String, m0() As String
Dim i As Integer, mcd() As String, p0() As String, s0()
As String, s1() As String
Dim z As String, r As String, rs As String, ns As
Integer, sw As Integer
Dim res As String, ui As String, s2() As String, kk As
Integer, xy As String
Dim w As String, vp0 As String, vp() As String, q() As
String, pol() As String
Dim x(2) As String, y As String, k As Integer, mcm() As
String, rr() As String
Dim mo() As String, gpol() As Integer, xx As String, rc
As String, n As Integer
Dim ii As String, j As Integer, jj As String, w0 As
String
ReDim mo(nc), gpol(nc)
rc = Chr$(13) + Chr$(10): n = 7
rr() = RutinaCoeficientes(mdls)
For i = 1 To nc : mo(i) = rr(i – 1) : Next i
'——— Cambios para que la primera congruencia tenga
el módulo menor.
For i = 2 To nc
x(1) = mo(i): x(2) = mo(1): y = Restar(x(),
n)
If Left$(y, 1) = "-" Then
xy = mo(1): mo(1) = mo(i): mo(i) = xy
xy = sist(1): sist(1) = sist(i): sist(i) = xy
End If
Next i
gs = 0
For j = 1 To nc
pol() = RutinaCoeficientes(sist(j))
gpol(j) = UBound(pol())
If gpol(j) > gs Then gs = gpol(j)
Next j
ReDim p(gs, nc)
For i = 1 To nc
pol() = RutinaCoeficientes(sist(i))
For j = 0 To gpol(i)
p(j, i) = pol(j)
Next j
Next i
' El sistema ¿puede tener soluciones?
ReDim mcd(nc)
For i = 1 To nc
If Left$(p(0, i), 1) = "-" Then y = Mid$(p(0, i), 2)
Else y = p(0, i)
For j = 1 To gpol(i)
If j < gpol(i) Then
If Left$(p(j, i), 1) = "-" Then xx = Mid$(p(j, i), 2)
Else xx = p(j, i)
Else
xx = mo(i)
End If
If xx <> "0" Then
x(1) = xx: x(2) = y: mcd(i) = MaxComDiv(x(),
n)
y = mcd(i)
Else
mcd(i) = y
End If
Next j
x(1) = p(gpol(i), i): x(2) = mcd(i): rr() =
DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
y = rr(2)
If y <> "0" Then
SCNLNG = "No hay soluciones"
Exit Function
End If
Next i
ReDim p0(gs, nc), m0(nc)
For i = 1 To nc
If mcd(i) = "1" Then
m0(i) = mo(i)
For j = 0 To gpol(i)
p0(j, i) = p(j, i)
Next j
Else
x(1) = mo(i): x(2) = mcd(i): rr() =
DivisionEuclidea(x(), n)
m0(i) = rr(1)
For j = 0 To gpol(i)
x(1) = p(j, i): x(2) = mcd(i): rr() =
DivisionEuclidea(x(), n)
p0(j, i) = rr(1)
Next j
End If
Next i
'———- Resolución de la congruencia de
módulo menor.
ReDim s0(m0(1))
jj = "0": k = 0
Do
If jj = "0" Then
x(1) = p(gpol(1), 1): x(2) = m0(1): rr() =
DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
z = rr(2)
Else
z = p(0, 1)
For i = 1 To gpol(1)
x(1) = jj: x(2) = z: x(1) = Multiplicar(x(),
n)
x(2) = p(i, 1): z = Sumar(x(), n)
Next i
x(1) = z: x(2) = m0(1)
rr() = DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
z = rr(2)
End If
If z = "0" Then
k = k + 1: s0(k) = jj
End If
(1) = jj: x(2) = "1": jj = Sumar(x(), n)
f jj = m0(1) Then Exit Do
Loop
ns = k
' Resolución del sistema
If ns <> 0 Then
ReDim s1(ns), s2(ns), vp(nc), mcm(nc)
For i = 1 To ns: s1(i) = s0(i): Next i
ReDim s2(m0(1))
For i = 1 To ns: s1(i) = s0(i): Next i
mcm(1) = m0(1)
For i = 2 To nc
x(1) = mcm(i – 1): x(2) = m0(i)
mcm(i) = MinComMult(x(), n)
Next i
x(1) = m0(1): x(2) = m0(2)
w0 = MinComMult(x(), n)
For i = 3 To nc
x(1) = w0: x(2) = m0(i)
w0 = MinComMult(x(), n)
Next i
x(1) = mo(1): x(2) = mo(2)
w = MinComMult(x(), n)
For i = 3 To nc
x(1) = w: x(2) = mo(i)
w = MinComMult(x(), n)
Next i
kk = 0
For k = 1 To ns
ii = "0"
For i = 2 To nc
ReDim q(gpol(i))
q(0) = p(0, i)
Do
x(1) = ii: x(2) = m0(1): x(1) = Multiplicar(x(), n):
x(2) = s1(k)
vp0 = Sumar(x(), n)
For j = 1 To gpol(i)
x(1) = vp0: x(2) = q(j – 1)
x(1) = Multiplicar(x(), n): x(2) = p(j, i)
q(j) = Sumar(x(), n)
Next j
x(1) = q(gpol(i)): x(2) = m0(i): rr() =
DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
vp(i) = rr(2)
If vp(i) = "0" Then Exit Do
x(1) = ii: x(2) = "1": ii = Sumar(x(), n)
x(1) = mcm(i): x(2) = m0(1): x(2) = Sumar(x(), n): x(1)
= vp0
y = Restar(x(), n)
Loop While Left$(y, 1) = "-"
Next i
For i = 2 To nc
If vp(i) <> "0" Then sw = 1
Next i
If sw = 0 Then
If vp0 <> s2(kk) Or kk = 0 Then
kk = kk + 1: s2(kk) = vp0
End If
Else
sw = 0
End If
Next k
If kk = 0 Then
SCNLNG = "No hay soluciones"
Exit Function
End If
' Ordenar las soluciones
For i = 1 To kk
For j = i + 1 To kk
If s2(i) > s2(j) Then
xy = s2(i): s2(i) = s2(j): s2(j) = xy
End If
Next j
Next i
'Edición de las soluciones
res = "Soluciónes: " + rc + rc
For i = 1 To kk
ui = s2(i)
res = res + "x = " + ui + " + " + "k*" + mcm(nc) +
rc
Next i
If w0 <> w Then
res = res + rc + "Soluciones respecto al módulo:
" + w + rc
res = res + rc
For i = 1 To kk
ui = s2(i): ii = 0
Do
y = ui + ii * mcm(nc)
res = res + "x = " + y + " + k*" + w + rc
ii = ii + 1
x(1) = y: x(2) = mcm(nc)
x(1) = Sumar(x(), n): x(2) = w
y = Restar(x(), n)
Loop While Left$(y, 1) = "-"
res = res + rc: y = 0
Next i
End If
Else
res = "No hay soluciones"
End If
SCNLNG = res
End Function
Public Function RutinaCoeficientesB(ByVal t As String)
As Variant
Dim i As Integer, j As Integer, k As Integer, lt As
Integer
Dim i0 As Integer, nco As Integer, gp As
Integer
Dim bb As String, px() As String
'—- Número de las comas en la cadena
t
If Right$(t, 1) <> "," Then t = t + ","
k = 1: lt = Len(t): nco = 0
Do
bb = Right$(Left$(t, k), 1)
If bb = "," Then
nco = nco + 1
End If
k = k + 1
If k > lt Then Exit Do
Loop
gp = nco – 1
'— Separación de los coeficientes
ReDim px(gp)
k = 1: i = 1: i0 = 0: j = 0
Do
bb = Right$(Left$(t, k), 1)
If bb = "," Then
j = j + 1
px(i0) = Left$(t, k – 1)
i = i + 1: i0 = i0 + 1
t = Mid$(t, k + 1)
k = 1
Else
k = k + 1
End If
If j = nco Then Exit Do
Loop
RutinaCoeficientes = px()
End Function
En la función SCNLNG las soluciones de de la
congruencia de módulo menor y las soluciones del sistema
se almacenaban en matrices Si los módulos son
moderadamente grandes y no primos esto tiene la desventaja que
los matrices utilizados para contener las soluciones tienen
demasiados elementos, aunque finalmente pocas soluciones
tendremos que almacenar en ellas. El código siguiente no
utilizara matrices para retener las soluciones pero tiene la
desventaja de no ordenar las soluciones (de menor a
mayor).
Public Function SCNLNGB(ByRef sist() As String, ByVal
mdls As String, nc As Integer) As String
Dim p() As String, gp As Integer, gs As Integer, m As
String, m0() As String
Dim i As Integer, mcd() As String, p0() As String, n As
Integer. ii As String
Dim z As String, r As String, rs As String, ns As
Integer, rc As String
Dim res As String, ui As String, kk As Integer, jj As
String, sw As Integer
Dim vp0 As String, vp() As String, q() As String, pol()
As String
Dim x(2) As String, y As String, mcm() As String, rr()
As String
Dim mo() As String, gpol() As Integer, xx As String, xy
As String
ReDim mo(nc), gpol(nc)
rc = Chr$(13) + Chr$(10): n = 7
rr() = RutinaCoeficientes(mdls)
For i = 1 To nc : mo(i) = rr(i – 1) : Next i
'——— Cambios para que la primera congruencia tenga
el módulo menor.
For i = 2 To nc
x(1) = mo(i): x(2) = mo(1): y = Restar(x(),
n)
If Left$(y, 1) = "-" Then
xy = mo(1): mo(1) = mo(i): mo(i) = xy
xy = sist(1): sist(1) = sist(i): sist(i) = xy
End If
Next i
gs = 0
For j = 1 To nc
pol() = RutinaCoeficientes(sist(j))
gpol(j) = UBound(pol())
If gpol(j) > gs Then gs = gpol(j)
Next j
ReDim p(gs, nc)
For i = 1 To nc
pol() = RutinaCoeficientes(sist(i))
For j = 0 To gpol(i)
p(j, i) = pol(j)
Next j
Next i
' El sistema ¿puede tener soluciones?
ReDim mcd(nc)
For i = 1 To nc
If Left$(p(0, i), 1) = "-" Then y = Mid$(p(0, i), 2)
Else y = p(0, i)
For j = 1 To gpol(i)
If j < gpol(i) Then
If Left$(p(j, i), 1) = "-" Then xx = Mid$(p(j, i), 2)
Else xx = p(j, i)
Else
xx = mo(i)
End If
If xx <> "0" Then
x(1) = xx: x(2) = y: mcd(i) = MaxComDiv(x(),
n)
y = xx
Else
mcd(i) = y
End If
Next j
x(1) = p(gpol(i), i): x(2) = mcd(i): rr() =
DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
y = rr(2)
If y <> "0" Then
SCNLNGB = "No hay soluciones"
Exit Function
End If
Next i
ReDim p0(gs, nc), m0(nc)
For i = 1 To nc
If mcd(i) = "1" Then
m0(i) = mo(i)
For j = 0 To gpol(i)
p0(j, i) = p(j, i)
Next j
Else
x(1) = mo(i): x(2) = mcd(i): rr() =
DivisionEuclidea(x(), n)
m0(i) = rr(1)
For j = 0 To gpol(i)
x(1) = p(j, i): x(2) = mcd(i): rr() =
DivisionEuclidea(x(), n)
p0(j, i) = rr(1)
Next j
End If
Next i
ReDim mcm(nc), vp(nc)
mcm(1) = m0(1)
For i = 2 To nc
x(1) = mcm(i – 1): x(2) = m0(i)
mcm(i) = MinComMult(x(), n)
Next i
"———- Resolución de la congruencia de
módulo menor.
jj = "0"
Do
If jj = "0" Then
x(1) = p(gpol(1), 1): x(2) = m0(1): rr() =
DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
z = rr(2)
Else
x(1) = p(0, 1): x(2) = m0(1): rr() =
DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
z = rr(2)
For i = 1 To gpol(1)
x(1) = z: x(2) = jj: x(1) = Multiplicar(x(),
n)
x(2) = p(i, 1): x(1) = Sumar(x(), n): x(2) =
m0(1)
rr() = DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
z = rr(2)
Next i
End If
If z = "0" Then
' Comprobación si jj verifica las otras
congruencias
For i = 2 To nc
ReDim q(gpol(i))
q(0) = p(0, i)
Do
x(1) = ii: x(2) = m0(1): x(1) = Multiplicar(x(), n):
x(2) = jj
vp0 = Sumar(x(), n)
For j = 1 To gpol(i)
x(1) = vp0: x(2) = q(j – 1)
x(1) = Multiplicar(x(), n): x(2) = p(j, i)
q(j) = Sumar(x(), n)
Next j
x(1) = q(gpol(i)): x(2) = m0(i): rr() =
DivisionEuclidea(x(), n)
If rr(2) = "-0" Then rr(2) = "0"
Vp(i) = rr(2)
If vp(i) = "0" Then Exit Do
x(1) = ii: x(2) = "1": ii = Sumar(x(), n)
x(1) = mcm(i): x(2) = m0(1): x(2) = Sumar(x(), n): x(1)
= vp0
y = Restar(x(), n)
Loop While Left$(y, 1) = "-"
Next i
ii = "0"
For i = 2 To nc
If vp(i) <> "0" Then sw = 1
Next i
If sw = 0 Then
vp0 = vp0 Mod mcm(nc)
If kk = 0 Then res = "x = "
res = res + vp0 + ","
If kk = 0 Then kk = 1
Else
sw = 0
End If
End If
x(1) = jj: x(2) = "1": jj = Sumar(x(), n)
If jj = mo(1) Then Exit Do
Loop
If Right$(res, 1) = "," Then res = Left$(res, Len(res) –
1)
If kk = 1 Then res = res + " + k*" + mcm(nc) Else res =
"No hay soluciones"
SCNLNGB = res
End Function
Ejemplo 24: Resolver el sistema de congruencias
siguiente:
Aplicando uno de los dos códigos anteriores se
obtiene que las soluciones son las siguientes:
Los dos últimos programas funcionan bien si los
módulos no son demasiado grandes. En el caso contrario el
tiempo de espera puede llegar considerable. Pero así son
las cosas, siempre habrá límites (sobre todo para
los módulos), que podrán mejorar con la
evolución de los ordenadores, pero existirán
siempre.
Observación 3: En los programas expuestos
en este trabajo se utilizó con cierta frecuencia el
código siguiente: rr() = DivisionEuclidea:If rr(2)="-0"
then rr(2)="0".Se puede prescindir de la secuencia If rr(2)="-0"
then rr(2)="0"si en el programa de operaciones con números
enteros grandes [11] se elimina el resultado "-0" Para esto en la
función DivisionEclidea, antes de devolver el resultado,
hay que incluir el código If rt(2 ) = "-0" then rt(2) =
"0" También en la función Multiplicar, antes de de
devolver el resultado hay que incluir el código If at =
"-0" then at= "0". De todos modos, si el usuario hace o no estas
modificaciones, los programas que se refieren a congruencias o
ecuaciones diofánticas, funcionarán perfectamente.
Si se lleva a cabo esta pequeña modificación en
[11], en las aplicaciones anteriores o futuras ya no
debería preocuparse del resultado "-0".
Bibliografía:
[1] P.Bachmann, Niedere Zahlentheorie, 1910
[2] R.D Garmichael:Thérie des nombre,
1919
[3] L.E. Dickson. Einfürung in die Zahlentheorie,
1931
[4] B.P. Huppert, Endlichen gruppen
[5] Kiss Ernö, A számelmélet Elemei,
Technikai Könyvkiado, Bukarest, 1960
[6] Eugen Rusu, Bazele teoriei numerelor,
1953
[7]Vinogradov, Los bases de la teoría de los
números (en ruso), 1952
[8] I. Creanga, C. Czacu, P. Minu?, GH. Opai?, Corina
Reischer, Introducere în teoría
numerelor, Editura Didactia ?i Pedagogica, Bucure?ti,
1965
[9] A.L. Hincin, Frac?ii Continue, Editura Tehnica,
Bucarest, 1960
[10] A. Péter Santha, Índice y
periódo de los elementos de un semigupo, Monografias.com,
2012
[11] A. Peter Santha, Cálculos con números
enteros grandes en ordenadores, Monografias.com, 2012
Autor:
Aladar Peter Santha
Página anterior | Volver al principio del trabajo | Página siguiente |