maths.chinese_remainder_theorem

Chinese Remainder Theorem: GCD ( Greatest Common Divisor ) or HCF ( Highest Common Factor )

If GCD(a,b) = 1, then for any remainder ra modulo a and any remainder rb modulo b there exists integer n, such that n = ra (mod a) and n = ra(mod b). If n1 and n2 are two such integers, then n1=n2(mod ab)

Algorithm :

  1. Use extended euclid algorithm to find x,y such that a*x + b*y = 1

  2. Take n = ra*by + rb*ax

Functions

chinese_remainder_theorem(→ int)

chinese_remainder_theorem2(→ int)

extended_euclid(→ tuple[int, int])

invert_modulo(→ int)

Module Contents

maths.chinese_remainder_theorem.chinese_remainder_theorem(n1: int, r1: int, n2: int, r2: int) → int
>>> chinese_remainder_theorem(5,1,7,3)
31
Explanation31 is the smallest number such that

  1. When we divide it by 5, we get remainder 1

  2. When we divide it by 7, we get remainder 3

>>> chinese_remainder_theorem(6,1,4,3)
14
maths.chinese_remainder_theorem.chinese_remainder_theorem2(n1: int, r1: int, n2: int, r2: int) → int
>>> chinese_remainder_theorem2(5,1,7,3)
31

>>> chinese_remainder_theorem2(6,1,4,3)
14
maths.chinese_remainder_theorem.extended_euclid(a: int, b: int) → tuple[int, int]
>>> extended_euclid(10, 6)
(-1, 2)

>>> extended_euclid(7, 5)
(-2, 3)
maths.chinese_remainder_theorem.invert_modulo(a: int, n: int) → int
>>> invert_modulo(2, 5)
3

>>> invert_modulo(8,7)
1