Iterative CRT Merging — அடிப்படை

Iterative CRT Merging — பகா எண் / mod கணிதத்தில் முக்கிய நுட்பம்.

உண்மை உலகில் இது ஏன் முக்கியம்?

மறையீடு, நேர்காணல், கலவையியல் — பகா எண்கள், mod கணிதம்.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

மையக் கருத்து: mod-ஐ ஒவ்வொரு படியிலும் பயன்படுத்து; gcd/பகா காரணி சரிபார்.

Pythonில் முயற்சி செய்வோம்

def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def crt_two(r1: int, m1: int, r2: int, m2: int) -> int:
    g, x, _ = ext_gcd(m1, m2)
    if (r2 - r1) % g != 0:
        raise ValueError("no solution")
    lcm = m1 // g * m2
    t = ((r2 - r1) // g * x) % (m2 // g)
    return (r1 + t * m1) % lcm


print(crt_two(2, 3, 3, 5))

பொதுவான தவறுகள்

• mod முடிவில் மட்டும்.
• gcd சரிபார்ப்பு மறப்பு.
• overflow.

முக்கிய பாடங்கள்

• mod_pow வார்ப்புரு.
• சிறு mod 7 உதாரணம்.
• காரணிப்படுத்தல்.