<jupyter_start><jupyter_text>Algoritmos de Euclides<jupyter_code>from IPython.display import Math, display
import os

if 'examples' in os.getcwd():
    os.chdir('..')<jupyter_output><empty_output><jupyter_text>Máximo común divisorEste algoritmo funciona en cualquier dominio euclídeo.<jupyter_code>import numpy as np
from compalg import IZ
numbers = [
    (60, 36),
    (0, 5),
    (0, 0),
    (5460, 1),
    (-60, 36),
    (-60, -36)
]

for a, b in numbers:
    display(Math(r"\text{mcd}(" + str(a) + ", \, " + str(b) + ") = " + str(IZ.gcd(a, b))))<jupyter_output><empty_output><jupyter_text>Funciona con números aleatorios.<jupyter_code>for _ in range(10):
    a, b = np.random.randint(-5000, 5000, (2,), dtype=np.int32)
    display(Math(r"\text{mcd}(" + str(a) + ", \, " + str(b) + ") = " + str(IZ.gcd(a, b))))<jupyter_output><empty_output><jupyter_text>Funciona con más de dos elementos.<jupyter_code>display(Math(r"\text{mcd}(" + str(1155) + ", \, " + str(315) + ", \, " + str(-3675) + ") = " + str(IZ.gcd(1155, 315, -3675))))<jupyter_output><empty_output><jupyter_text>Algoritmo de Euclides extendidoEste algoritmo funciona en cualquier dominio euclídeo.<jupyter_code>for a, b in numbers:
    gcd, (x, y) = IZ.bezout(a, b)
    display(Math(str(a) + "\cdot " + str(x) + "+" + str(b) + "\cdot " + str(y) + "=" + str(gcd)))<jupyter_output><empty_output><jupyter_text>Funciona con números aleatorios.<jupyter_code>for _ in range(10):
    a, b = np.random.randint(-5000, 5000, (2,), dtype=np.int32)
    gcd, (x, y) = IZ.bezout(a, b)
    display(Math(str(a) + "\cdot " + str(x) + "+" + str(b) + "\cdot " + str(y) + "=" + str(gcd)))<jupyter_output><empty_output><jupyter_text>Teorema chino del resto<jupyter_code>from algorithms import solve_congruences
tests = [
    ([18], [8]),
    ([1, 1, 1], [7, 13, 11]),
    ([4, 12, 0], [9, 14, 17])
]

for b, n in tests:
    x, z = solve_congruences(b, n)
    for bi, ni in zip(b, n):
        display(Math(r"x \equiv " + str(bi) + r" \mod " + str(ni)))
    display(Math(r"\implies x = " + str(x) + r" \in " + z.__latex__()))
    print()


tests = [
    ([5], [3], [21]),
    ([4, 9, 33, 1], [8, 23, 1, 42], [21, 38, 53, 55])
]

for a, b, n in tests:
    x, z = solve_congruences(a, b, n)
    for ai, bi, ni in zip(a, b, n):
        display(Math(str(ai) + r"x \equiv " + str(bi) + r" \mod " + str(ni)))
    display(Math(r"\implies x = " + str(x) + r" \in " + z.__latex__()))
    print()

try:
    solve_congruences([0, 0, 0], [12, 35, 21])
except:
    display(Math(r"\text{No se puede resolver el siguiente sistema porque las } n \text{ no son coprimas:}"))
    display(Math(r"x \equiv 0 \mod 12"))
    display(Math(r"x \equiv 0 \mod 35"))
    display(Math(r"x \equiv 0 \mod 21"))<jupyter_output><empty_output><jupyter_text>Máximo común divisor en un DFU<jupyter_code>from compalg import Var, IZ, IF
x = Var('x')

IZx = IZ[x]

tests = [
    (x ** 2 + 2 * x + 1,                           x + 1),                                         # x + 1
    ((x ** 3 + 1) * (6 * x ** 2 + 5 * x + 1),      (x ** 3 + 1) * (7 * x ** 5 + x ** 2 + 3 * x)),  # x^3 + 1
    (48 * x ** 3 - 84 * x ** 2 + 42 * x - 36,      -4 * x ** 3 - 10 * x ** 2 + 44 * x - 30),       # 4x - 6
    (3 * (x + 1) * (x - 2) * (x + 5) * (x - 11),   5 * (x + 3) * (x - 7) * x),                     # -1
    (10 * (x + 1) * (x - 2) * (x + 5) * (x - 11),  8 * (x + 3) * (x - 7) * x),                     # -2
    (12 * x ** 3 + 60 * x + 24,                    8 * x ** 3 + 40 * x + 16)                       # 4x^3 + 20x + 8
]

for p, q in tests:
    gcd = IZx.gcd(p, q)
    r = getattr(gcd, "__latex__", repr)
    display(Math(r"\text{mcd}(" + p.__latex__() + ", \, " + q.__latex__() + ") = " + r()))<jupyter_output><empty_output><jupyter_text>También funciona para cualquier cuerpo y para más de dos.<jupyter_code>x = Var('x')

IF7x = IF(7)[x]
g = (x ** 2 + 4 * x + 6) @ IF7x
p = (g * 5) @ IF7x
q = (g * (x + 1)) @ IF7x
r = (g * (x - 1)) @ IF7x

gcd = IF7x.gcd(p, q, r)
display(Math(r"\text{mcd}(" + p.__latex__() + ", \, " + q.__latex__() + ", \, " + r.__latex__() + ") = " + gcd.__latex__()))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.21643238002908385, 'fraction_numerical': 0.05380513814832768, 'mean_word_length': 2.6749777382012465, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 37, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '432189', 'license': 'MIT', 'n_tokens_mistral': 1963, 'n_tokens_neox': 1788, 'n_words': 432, 'path': 'examples/euclides_tests.ipynb', 'repo_name': 'Soy-yo/computer-algebra-algorithms', 'size': '4126'}