中国の剰余定理

今年 2021 年の次の 3 個の素数年は, 2027, 2029, 2039 年である。

2027 で割ると余りが 101
2029 で割ると余りが 103
2039 で割ると余りが 107

となるような最小の正整数を求めよ

答えは，ずっと下へスクロール

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

function chinese_remainder_theorem(a1, r1, a2, r2, a3, r3)
    #=
    a1, r1 最初の除数と剰余
    a2 r2 二番目の除数と剰余
    a3, r3 最後の除数と剰余
    =#
    gcd1, m1, n1 = xgcd(a1, a2*a3)
    gcd2, m2, n2 = xgcd(a2, a1*a3)
    gcd3, m3, n3 = xgcd(a3, a1*a2)
    answer = r1*a2*a3*n1 + a1*r2*a3*n2 +a1*a2*r3*n3
    while answer < 0
        answer += a1*a2*a3
    end
    answer
end

function xgcd(a, b)
    m, n, x, y = 1, 0, 0, 1
    while b > 0
        q = a ÷ b
        x, m = m - q * x, x
        y, n = n - q * y, y
        a, b = b, a % b
    end
    a, m, n
end

chinese_remainder_theorem(2027, 101, 2029, 103, 2039, 107)

求まる解は 7966458745

確かに，

16352423282 % 2027 # 101
16352423282 % 2029 # 103
16352423282 % 2039 # 107