1load("number-theory.sage")
 2
 3#####
 4# Chinese Remainder Theorem tests
 5a_i = [5, 3, 10]
 6m_i = [7, 11, 13]
 7M = 1001
 8assert crt(a_i, m_i, M) == 894
 9
10a_i = [3, 8]
11m_i = [13, 17]
12M = 221
13assert crt(a_i, m_i, M) == 42
14
15
16#####
17# gcd, using Binary Euclidean algorithm tests
18assert gcd(21, 12) == 3
19assert gcd(1_426_668_559_730, 810_653_094_756) == 1_417_082
20
21assert gcd_recursive(21, 12) == 3
22
23#####
24# Extended Euclidean algorithm tests
25assert egcd(7, 19) == (1, -8, 3)
26assert egcd_recursive(7, 19) == (1, -8, 3)
27
28#####
29# Inverse modulo N tests
30assert inv_mod(7, 19) == 11