gistfile1.rb

require 'pp'

c1 = 63
r1 = 1
c2 = 100
r2 = 91

gcdr = []
gcdc = []
rems  = []

if r1 > r2
  gcdc << [c1, c2]
else
  gcdc << [c2, c1]
end

while true
  i = 0
  res = gcdc[-1][i] / gcdc[-1][i+1]
  rem = gcdc[-1][i] % gcdc[-1][i+1]
  break if rem == 0
  gcdr << res
  newc = [rem, gcdc[-1][i+1]]
  gcdc << newc
  rems  << rem
  i = 1
  res = gcdc[-1][i] / gcdc[-1][i-1]
  rem = gcdc[-1][i] % gcdc[-1][i-1]
  break if rem == 0
  gcdr << res
  newc = [gcdc[-1][i-1], rem]
  gcdc << newc
  rems  << rem
end

pp gcdc
pp gcdr
pp rems

c = (r2 - r1).abs
#rems.delete_at(-1) if rems.size.even?
#gcdr.delete_at(-1) if gcdr.size.even?
rm = rems[-1]
rm1 = rems[-2]
mati = (1..100).each do |i|
  mod = rems.size.even? ? (rm * i - c) % rm1 : (rm * i + c) % rm1
  break i if mod == 0
end
v = rems.size.even? ? (rm * mati - c) / rm1 : (rm * mati + c) / rm1

pp "rm = #{rm}, rm-1 = #{rm1}, c = #{c}"
pp "mati = #{mati}, v = #{v}"

valli = []
valli << gcdr[1..-1]
valli << mati
valli << v
valli.flatten!

pp valli

while true
  break if valli.size == 2
  valli[-3] = valli[-3] * valli[-2] + valli[-1]
  valli.delete_at(-1)
  pp valli
end

alpha1 = r2 > r1 ? valli[0] % c1 : valli[0] % c2
alphar = r2 > r1 ? valli[0] / c1 : valli[0] / c2
alphad = r2 > r1 ? c1 : c2
pp "#{valli[0]} = #{alphad} * #{alphar} + #{alpha1}"

n = r2 > r1 ? c2 * alpha1 + r2 : c1 * alpha1 + r1
pp r2 > r1 ? "N = #{c2} * #{alpha1} + #{r2} = #{n}" : "N = #{c1} * #{alpha1} + #{r1} = #{n}"
pp "N = #{n}"