Skip to content

Instantly share code, notes, and snippets.

@p7g

p7g/chinese-remainder-theorem.py

Last active December 16, 2020 06:11
Show Gist options
  • Save p7g/293cbfda7690505ff48959bf294b5f54 to your computer and use it in GitHub Desktop.
Save p7g/293cbfda7690505ff48959bf294b5f54 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
chinese-remainder-theorem.py
times = "17,x,13,19".split(",")
equations = [(rem, int(mod)) for rem, mod in enumerate(times) if mod != "x"]
M = reduce(mul, map(itemgetter(1), equations))
x = 0
for a, m in equations:
y = M // m
z = pow(y, -1, m)
x += a * y * z
print(x % M)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment