constructor-igor / TechSugar

Tech. Sugar seminars
7 stars 7 forks source link

Chinese remainder theorem #446

Closed constructor-igor closed 4 years ago

constructor-igor commented 4 years ago

https://en.wikipedia.org/wiki/Chinese_remainder_theorem

constructor-igor commented 4 years ago
N = 119
a[0] = 3, r[0]=2, 119 = 3*39+2
a[1] = 5, r[1]=4, 119 = 5*23+4
a[2] = 8, r[2]=7, 119 = 8*14+7
N = 338692039
a[0] = 1003, r[0]=2, 338692039 = 1003*337679+2
a[1] = 1005, r[1]=4, 338692039 = 1005*337007+4
a[2] = 1008, r[2]=7, 338692039 = 1008*336004+7