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`

.

- http://ochaochaocha3.blogspot.com/2013/10/extgcd-on-javascript-and-ruby.html
- https://qiita.com/drken/items/ae02240cd1f8edfc86fd

Recommended Posts