//
// Chinese Remainder Theorem
//
// Using FutureBasic 7.0.34
// August 25, R.W


Int n(2) = { 3, 5, 7 }         // Rosetta's test data
Int a(2) = { 2, 3, 2 }

//Int n(2) = { 11, 12, 13 }    // Expecting 1000
//Int a(2) = { 10, 4, 12 }

//Int n(2) = { 11, 22, 19 }    // Failure test
//Int a(2) = { 10, 4, 9 }

//
// Greatest Common Factor

local fn GCF(x As UInt64, y As UInt64) As UInt64
  UInt64 t
  While y
    t = y
    y = x Mod y
    x = t
  Wend
end fn = x

// x = (ax) MOD b == 1
local fn ModularMultiplicativeInverse( a1 as Int, b1 as Int ) as Int
  Int i
  if b1 == 1 then return 1
  for i = 1 to b1
    if (a1 * i) % b1 == 1 then return i
  next i
end fn = 0

local fn chinese_remainder(ln as int ) as int
  int i,j,p,prod,sum,ni,ai
  prod = 1
  sum = 0
  for i = 0 to ln-1
    for j = i+1 to ln-1
      if fn GCF( n(i), n(j) ) > 1
        print "N relative prime with no GCF"
      end if
    next
  next
  for i = 0 to ln-1
    prod *= n(i)
  next
  for i = 0 to ln-1
    ni = n(i)
    ai = a(i)
    p = prod / ni
    sum += ai * fn ModularMultiplicativeInverse(p,ni) * p
  next

end fn = sum mod prod

//
// main

window 1

print fn chinese_remainder(3)

HandleEvents