Congruencias (página 2)

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