ДЗ по математике

main2.py

def extended_gcd(a, b):
    """
    Расширенный алгоритм Евклида.
    Возвращает кортеж (g, x, y), где:
    g = НОД(a, b)
    x, y такие, что a*x + b*y = g
    """
    if b == 0:
        return (a, 1, 0)
    else:
        g, x2, y2 = extended_gcd(b, a % b)
        x = y2
        y = x2 - (a // b) * y2
        return (g, x, y)


def gcd_euclid(a, b):
    """
    Алгоритм Евклида для нахождения НОД(a,b). 
    Возвращает НОД и одновременно выводит шаги.
    """
    print(f"Вычисляем gcd({a}, {b}) алгоритмом Евклида.\nШаги делений:")
    A, B = a, b
    while B != 0:
        q = A // B
        r = A % B
        print(f"  {A} = {B} * {q} + {r}")
        A, B = B, r
    print(f"НОД({a}, {b}) = {A}\n")
    return A


def build_continued_fraction(numerator, denominator):
    """
    Возвращает список коэффициентов цепной дроби для дроби numerator/denominator.
    Предполагается, что знаменатель положительный.
    """
    result = []
    x, y = numerator, denominator

    while y != 0:
        whole = x // y
        result.append(whole)
        x, y = y, x % y

    return result


def build_convergents(partial_quotients):
    """
    Вычисляет последовательные приближения (сходящиеся) цепной дроби
    по её неполным частным. Возвращает два списка: числители и знаменатели.

    Используем рекуррентные соотношения:
        num[k] = a[k] * num[k-1] + num[k-2]
        den[k] = a[k] * den[k-1] + den[k-2]
    """
    numerators = []
    denominators = []

    num_prev2, num_prev1 = 0, 1  # Начальные значения
    den_prev2, den_prev1 = 1, 0

    for idx, coeff in enumerate(partial_quotients):
        num = coeff * num_prev1 + num_prev2
        den = coeff * den_prev1 + den_prev2

        numerators.append(num)
        denominators.append(den)

        # Обновление предыдущих значений для следующего шага
        num_prev2, num_prev1 = num_prev1, num
        den_prev2, den_prev1 = den_prev1, den

    return numerators, denominators


def solve_congruence():
    # ДАНО из условия
    a = 14546
    m = 19929
    alpha = 29  # Я родился 29 мая поэтому указываю 29
    
    b = 7 * alpha  # b = 7 * α
    
    print("Задано сравнение:")
    print(f"  {a} * x ≡ 7 * α (mod {m})")
    print(f"Подставим α = {alpha}, тогда b = 7 * {alpha} = {b}\n")
    
    # 1. Вычисляем НОД(a, m) с помощью алгоритма Евклида
    print("1) Находим НОД(a, m):")
    g = gcd_euclid(a, m)
    
    # 2. Проверяем, делится ли b на НОД(a, m). Если не делится, решений нет.
    print("2) Проверяем делимость b на НОД(a, m):")
    if b % g != 0:
        print(f"  Поскольку b = {b} не делится на gcd({a}, {m}) = {g}, решения не существует.")
        return
    else:
        print(f"  b = {b} делится на gcd({a}, {m}) = {g}. Следовательно, решения существуют.")
        print(f"  Число решений сравнения будет равно НОД, то есть {g}.\n")
    
    # Сократим сравнение на НОД g. Все коэффициенты делим на g.
    a_reduced = a // g
    m_reduced = m // g
    b_reduced = b // g
    
    print(f"Сокращаем сравнение, деля a, b, m на {g}:")
    print(f"  a' = {a} / {g} = {a_reduced}")
    print(f"  b' = {b} / {g} = {b_reduced}")
    print(f"  m' = {m} / {g} = {m_reduced}")
    print(f"Новое упрощённое сравнение имеет вид:\n  {a_reduced} * x ≡ {b_reduced} (mod {m_reduced})\n")
    
    # 3. Снова пользуемся алгоритмом Евклида, но уже для (a', m') - чтобы найти их НОД (для уверенности, он должен быть 1).
    print("3) Проверяем gcd(a', m') и используем расширенный алгоритм Евклида для нахождения обратного элемента:")
    gcd_reduced = gcd_euclid(a_reduced, m_reduced)
    if gcd_reduced != 1:
        # Теоретически, если мы уже всё сократили, gcd(a_reduced, m_reduced) должен быть 1.
        print(f"  Оказалось, gcd({a_reduced}, {m_reduced}) = {gcd_reduced} ≠ 1")
        return
    else:
        print(f"  gcd({a_reduced}, {m_reduced}) = 1, всё корректно.\n")
    
    # 4. сделал в тетради и таблицу из 5 пункта тож в тетради
    # И тут тоже решил доделать и доделал

    # 4: Разложение a'/m' в цепную дробь
    print("4) Разлагаем дробь a'/m' в цепную:")
    part_q = build_continued_fraction(a_reduced, m_reduced)
    print(f"   {a_reduced} на {m_reduced} → получаем последовательность: {part_q}")
    print("   Это соответствует представлению вида: q0 + 1/(q1 + 1/(q2 + ...))\n")
    
    # 5) Вычисляем P[n], Q[n] (таблица)
    print("5.1) Таблица последовательности P_n и Q_n для цепной дроби:")
    P, Q = build_convergents(part_q)

    print(f"{'n':>2} | {'a[n]':>5} | {'P[n]':>7} | {'Q[n]':>7}")
    print("---------------------------------")
    for i, a_i in enumerate(part_q):
    	print(f"{i:>2} | {a_i:>5} | {P[i]:>7} | {Q[i]:>7}")

    print()

    # 5. С помощью расширенного алгоритма Евклида найдём x0:
    #    Нужно найти такое x0, что (a' * x0) % m' = 1,
    #    а потом умножить x0 на b'.
    #    Расширенный алгоритм Евклида вернёт (g, x, y), где a'*x + m'*y = gcd(a', m') = 1.
    #    Тогда x есть обратный элемент a' по модулю m'.
    print("5.2) Находим обратный элемент a' по модулю m' (то есть решаем a'*x = 1 mod m'):\n")
    _, inv_a_reduced, _ = extended_gcd(a_reduced, m_reduced)
    
    # inv_a_reduced может быть отрицательным, приведём его к положительному остатку по модулю m'
    inv_a_reduced_mod = inv_a_reduced % m_reduced
    print(f"  Найденный коэффициент (обратный элемент) = {inv_a_reduced}.")
    print(f"  Приведём его к остатку по модулю {m_reduced}: inv_a_reduced_mod = {inv_a_reduced_mod}.\n")
    
    # Тогда частное решение x0: x0 = b' * inv_a_reduced (mod m')
    x0 = (b_reduced * inv_a_reduced_mod) % m_reduced
    
    print(f"6) Подставляем b' = {b_reduced} и получаем частное решение x0:")
    print(f"  x0 = (b' * inv_a_reduced_mod) mod m' = ({b_reduced} * {inv_a_reduced_mod}) mod {m_reduced} = {x0}\n")
    
    # 7. Формула в задании: x0 = (-1)^(n-1) * P_{n-1} * b, где P_{n-1} получается из цепной дроби.
    #    Но фактически этот x0 уже нашли через расширенный алгоритм Евклида.
    #    (Если бы вручную расписывали цепную дробь, получили бы тот же результат.)
    print("7) Формулу x0 = (-1)^{{n-1}}*P_{{n-1}}*b из теории мы фактически "
      "воспроизвели через расширенный алгоритм.\n"
      "   Поэтому x0 = {} при сокращённом сравнении.\n".format(x0))
    
    # 8. Так как исходный НОД(a, m) = g = 7, общее число решений = 7.
    #    Каждый последующий корень отличается на m' (то есть 19929/7 = 2847).
    #    Итоговые решения в первоначальном сравнении:
    #       x ≡ x0 + k*m'   (mod m), для k = 0, 1, ..., g-1.
    #    Так как все корни будут отличаться по модулю 19929 только на кратные 2847,
    #    и после 7 раз они замкнутся в исходную систему.
    
    print("8) Учитываем исходный НОД = g = 7. Тогда все решения исходного сравнения:\n"
          "   x = x0 + k * m', где k = 0, 1, 2, ..., g-1, и всё это берётся по модулю 19929.\n")
    
    solutions = []
    for k in range(g):
        sol = (x0 + k*m_reduced) % m  # Можно оставить % m, чтобы каждый был в диапазоне [0, m-1].
        solutions.append(sol)
    
    print(f"Число различных решений = {g}. Эти решения (в пределах 0..{m-1}):")
    for idx, s in enumerate(solutions):
        print(f"  k = {idx}: x = {s}")
    
    # Проверка найденных решений уравнения
    print("\nПроверка корректности решений:")
    for candidate in solutions:
    	computed = (a * candidate) % m
    	expected = b % m
    	print(f"x = {candidate} → ({a} * {candidate}) % {m} = {computed}", end=' ')
    	print("— корректно" if computed == expected else "— несоответствие!")

    print("\nВсе проверки завершены.")


if __name__ == "__main__":
    solve_congruence()

Вывол_программы.txt

Задано сравнение:
  14546 * x ≡ 7 * α (mod 19929)
Подставим α = 29, тогда b = 7 * 29 = 203

1) Находим НОД(a, m):
Вычисляем gcd(14546, 19929) алгоритмом Евклида.
Шаги делений:
  14546 = 19929 * 0 + 14546
  19929 = 14546 * 1 + 5383
  14546 = 5383 * 2 + 3780
  5383 = 3780 * 1 + 1603
  3780 = 1603 * 2 + 574
  1603 = 574 * 2 + 455
  574 = 455 * 1 + 119
  455 = 119 * 3 + 98
  119 = 98 * 1 + 21
  98 = 21 * 4 + 14
  21 = 14 * 1 + 7
  14 = 7 * 2 + 0
НОД(14546, 19929) = 7

2) Проверяем делимость b на НОД(a, m):
  b = 203 делится на gcd(14546, 19929) = 7. Следовательно, решения существуют.
  Число решений сравнения будет равно НОД, то есть 7.

Сокращаем сравнение, деля a, b, m на 7:
  a' = 14546 / 7 = 2078
  b' = 203 / 7 = 29
  m' = 19929 / 7 = 2847
Новое упрощённое сравнение имеет вид:
  2078 * x ≡ 29 (mod 2847)

3) Проверяем gcd(a', m') и используем расширенный алгоритм Евклида для нахождения обратного элемента:
Вычисляем gcd(2078, 2847) алгоритмом Евклида.
Шаги делений:
  2078 = 2847 * 0 + 2078
  2847 = 2078 * 1 + 769
  2078 = 769 * 2 + 540
  769 = 540 * 1 + 229
  540 = 229 * 2 + 82
  229 = 82 * 2 + 65
  82 = 65 * 1 + 17
  65 = 17 * 3 + 14
  17 = 14 * 1 + 3
  14 = 3 * 4 + 2
  3 = 2 * 1 + 1
  2 = 1 * 2 + 0
НОД(2078, 2847) = 1

  gcd(2078, 2847) = 1, всё корректно.

4) Разлагаем дробь a'/m' в цепную:
   2078 на 2847 → получаем последовательность: [0, 1, 2, 1, 2, 2, 1, 3, 1, 4, 1, 2]
   Это соответствует представлению вида: q0 + 1/(q1 + 1/(q2 + ...))

5.1) Таблица последовательности P_n и Q_n для цепной дроби:
 n |  a[n] |    P[n] |    Q[n]
---------------------------------
 0 |     0 |       0 |       1
 1 |     1 |       1 |       1
 2 |     2 |       2 |       3
 3 |     1 |       3 |       4
 4 |     2 |       8 |      11
 5 |     2 |      19 |      26
 6 |     1 |      27 |      37
 7 |     3 |     100 |     137
 8 |     1 |     127 |     174
 9 |     4 |     608 |     833
10 |     1 |     735 |    1007
11 |     2 |    2078 |    2847

5.2) Находим обратный элемент a' по модулю m' (то есть решаем a'*x = 1 mod m'):

  Найденный коэффициент (обратный элемент) = 1007.
  Приведём его к остатку по модулю 2847: inv_a_reduced_mod = 1007.

6) Подставляем b' = 29 и получаем частное решение x0:
  x0 = (b' * inv_a_reduced_mod) mod m' = (29 * 1007) mod 2847 = 733

7) Формулу x0 = (-1)^{n-1}*P_{n-1}*b из теории мы фактически воспроизвели через расширенный алгоритм.
   Поэтому x0 = 733 при сокращённом сравнении.

8) Учитываем исходный НОД = g = 7. Тогда все решения исходного сравнения:
   x = x0 + k * m', где k = 0, 1, 2, ..., g-1, и всё это берётся по модулю 19929.

Число различных решений = 7. Эти решения (в пределах 0..19928):
  k = 0: x = 733
  k = 1: x = 3580
  k = 2: x = 6427
  k = 3: x = 9274
  k = 4: x = 12121
  k = 5: x = 14968
  k = 6: x = 17815

Проверка корректности решений:
x = 733 → (14546 * 733) % 19929 = 203 — корректно
x = 3580 → (14546 * 3580) % 19929 = 203 — корректно
x = 6427 → (14546 * 6427) % 19929 = 203 — корректно
x = 9274 → (14546 * 9274) % 19929 = 203 — корректно
x = 12121 → (14546 * 12121) % 19929 = 203 — корректно
x = 14968 → (14546 * 14968) % 19929 = 203 — корректно
x = 17815 → (14546 * 17815) % 19929 = 203 — корректно

Все проверки завершены.