Chinese remainder theorem: Difference between revisions

=={{header|FreeBASIC}}==

Partial {{trans|C}}. Uses the code from [[Greatest_common_divisor#Recursive_solution]] as an include.

<lang freebasic>

#include "gcd.bas"

function mul_inv( a as integer, b as integer ) as integer

if b = 1 then return 1

for i as integer = 1 to b

if a*i mod b = 1 then return i

next i

return 0

end function

function chinese_remainder(n() as integer, a() as integer) as integer

dim as integer p, i, prod = 1, sum = 0, ln = ubound(n)

for p = 0 to ln-1

for i = p+1 to ln

if gcd(n(i), n(p))>1 then

print "N not coprime"

end

end if

next i

next p

for i = 0 to ln

prod *= n(i)

next i

for i = 0 to ln

p = prod/n(i)

sum += a(i) * mul_inv(p, n(i))*p

next i

return sum mod prod

end function

dim as integer n(0 to 2) = { 3, 5, 7 }

dim as integer a(0 to 2) = { 2, 3, 2 }

print chinese_remainder(n(), a())</lang>

{{out}}<pre>23>/pre>