Neural Sync Active

Modular Arithmetic Deep Dive

Registry Synced

141 words

1 min read

Reading compass

Now · Extended Euclidean Algorithm

Extended Euclidean Algorithm

Find

x, y

such that

ax + by = \gcd(a, b)


python
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

System:

x \equiv a_1 \pmod{n_1}

x \equiv a_2 \pmod{n_2}

with

\gcd(n_1, n_2) = 1

. Solution:

x = a_1 M_1 y_1 + a_2 M_2 y_2

where

M_i = n_1 n_2 / n_i

and

y_i M_i \equiv 1 \pmod{n_i}

. Example: Solve

x \equiv 2 \pmod{3}

x \equiv 3 \pmod{5}

M_1 = 5

M_2 = 3

y_1 = 5^{-1} \equiv 2 \pmod{3}

y_2 = 3^{-1} \equiv 2 \pmod{5}

x = 2(5)(2) + 3(3)(2) = 20 + 18 = 38 \equiv 8 \pmod{15}