I needed it in Advent of Code 2020 Day 13, so I ported it to Ruby by referring to the information that came out. For details on the algorithm, see Kenchon's article.
If you write roughly what you can do, It can be used when you want to find "a number that is 2 when divided by 3, 8 when divided by 10, and 9 when divided by 31".
Pass an array of remainders (b) and divisions (m) to the crt method.
If the return value is (r, m), then the solution is x ≡ r (mod m).
def ext_gcd(a, b, values)
d = a
if b.zero?
values[:x] = 1
values[:y] = 0
else
d = ext_gcd(b, a % b, values)
x = values[:x]
y = values[:y]
values[:x] = y
values[:y] = x - (a / b) * y
end
d
end
def crt(b, m)
r = 0
mM = 1
b.zip(m) do |bi, mi|
val = {}
d = extgcd_h(mM, mi, val)
p = val[:x]
q = val[:y]
return [0, -1] if (bi - r) % d != 0
tmp = (bi - r) / d * p % (mi / d)
r += mM * tmp
mM *= mi / d
end
[r % mM, mM]
end
Divide by 19 and get over 0, Divide by 37 and over 24, When you want to find a number that is more than 504 divided by 523
b = [0, 24, 504]
m = [19, 37, 523]
ans = crt(b, m) # => [317965, 367669]
The answer is 367669n + 317965 with n as an integer.
The minimum natural number that satisfies the condition is 317965.
Recommended Posts