Chinese remainder theorem: Difference between revisions
m
Automated syntax highlighting fixup (second round - minor fixes)
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
||
Line 50:
::: <math>x \pmod{N}</math>.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F mul_inv(=a, =b)
V b0 = b
V x0 = 0
Line 80 ⟶ 79:
{{out}}
<pre>23</pre>
=={{header|360 Assembly}}==
{{trans|REXX}}
<syntaxhighlight lang="360asm">* Chinese remainder theorem 06/09/2015
CHINESE CSECT
USING CHINESE,R12 base addr
Line 131 ⟶ 129:
x= 23
</pre>
=={{header|Action!}}==
<syntaxhighlight lang=
INT b0,x0,x1,q,tmp
Line 185 ⟶ 182:
23
</pre>
=={{header|Ada}}==
Using the package Mod_Inv from [[http://rosettacode.org/wiki/Modular_inverse#Ada]].
<syntaxhighlight lang=
procedure Chin_Rema is
Line 210 ⟶ 206:
Ada.Text_IO.Put_Line(Integer'Image(Sum mod Prod));
end Chin_Rema;</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">mulInv: function [a0, b0][
[a b x0]: @[a0 b0 0]
result: 1
Line 250 ⟶ 245:
<pre>23</pre>
=={{header|AWK}}==
{{trans|C}}
We are using the split-function to create both arrays, thus the indices start at 1. This is the only difference to the C version.
<syntaxhighlight lang="awk"># Usage: GAWK -f CHINESE_REMAINDER_THEOREM.AWK
BEGIN {
len = split("3 5 7", n)
Line 293 ⟶ 287:
{{out}}
<pre>23</pre>
=={{header|BQN}}==
Multiplicative Modular inverse function taken from BQNcrate.
<syntaxhighlight lang="bqn">MulInv←⊣|·⊑{0=𝕨?1‿0;(⌽-(0⋈𝕩⌊∘÷𝕨)⊸×)𝕨𝕊˜𝕨|𝕩}
ChRem←{
num 𝕊 rem:
Line 306 ⟶ 299:
•Show 3‿5‿7 ChRem 2‿3‿2
•Show 10‿4‿9 ChRem 11‿22‿19</syntaxhighlight><syntaxhighlight lang="text">23
172</syntaxhighlight>
=={{header|Bracmat}}==
{{trans|C}}
<syntaxhighlight lang="bracmat">( ( mul-inv
= a b b0 q x0 x1
. !arg:(?a.?b:?b0)
Line 351 ⟶ 343:
Output:
<pre>23</pre>
=={{header|C}}==
When n are not pairwise coprime, the program crashes due to division by zero, which is one way to convey error.
<syntaxhighlight lang="c">#include <stdio.h>
// returns x where (a * x) % b == 1
Line 393 ⟶ 384:
return 0;
}</syntaxhighlight>
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">using System;
using System.Linq;
Line 448 ⟶ 438:
}
}</syntaxhighlight>
=={{header|C++}}==
<syntaxhighlight lang="cpp">// Requires C++17
#include <iostream>
#include <numeric>
Line 505 ⟶ 494:
{{out}}
<pre>23</pre>
=={{header|Clojure}}==
Modeled after the Python version http://rosettacode.org/wiki/Category:Python
<syntaxhighlight lang="lisp">(ns test-p.core
(:require [clojure.math.numeric-tower :as math]))
Line 555 ⟶ 543:
23
</pre>
=={{header|Coffeescript}}==
<syntaxhighlight lang="coffeescript">crt = (n,a) ->
sum = 0
prod = n.reduce (a,c) -> a*c
Line 581 ⟶ 568:
23
</pre>
=={{header|Common Lisp}}==
Using function ''invmod'' from [[http://rosettacode.org/wiki/Modular_inverse#Common_Lisp]].
<syntaxhighlight lang="lisp">
(defun chinese-remainder (am)
"Calculates the Chinese Remainder for the given set of integer modulo pairs.
Line 625 ⟶ 611:
{{trans|Ruby}}
<syntaxhighlight lang="crystal">def extended_gcd(a, b)
last_remainder, remainder = a.abs, b.abs
x, last_x = 0, 1
Line 665 ⟶ 651:
1731
</pre>
=={{header|D}}==
{{trans|Python}}
<syntaxhighlight lang="d">import std.stdio, std.algorithm;
T chineseRemainder(T)(in T[] n, in T[] a) pure nothrow @safe @nogc
Line 714 ⟶ 699:
{{libheader| Velthuis.BigIntegers}}
{{Trans|Java}}
<syntaxhighlight lang=
program ChineseRemainderTheorem;
Line 781 ⟶ 766:
{{out}}
<pre>23</pre>
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight lang="text">func mul_inv a b . x1 .
b0 = b
x1 = 1
Line 822 ⟶ 805:
{{out}}
<pre>23</pre>
=={{header|EchoLisp}}==
'''egcd''' - extended gcd - and '''crt-solve''' - chinese remainder theorem solve - are included in math.lib.
<syntaxhighlight lang="scheme">
(lib 'math)
math.lib v1.10 ® EchoLisp
Line 835 ⟶ 817:
💥 error: mod[i] must be co-primes : assertion failed : 1005
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Ruby}}
{{works with|Elixir|1.2}}
Brute-force:
<syntaxhighlight lang="elixir">defmodule Chinese do
def remainder(mods, remainders) do
max = Enum.reduce(mods, fn x,acc -> x*acc end)
Line 860 ⟶ 841:
[1000]
</pre>
=={{header|Erlang}}==
{{trans|OCaml}}
<syntaxhighlight lang="erlang">-module(crt).
-import(lists, [zip/2, unzip/1, foldl/3, sum/1]).
-export([egcd/2, mod/2, mod_inv/2, chinese_remainder/1]).
Line 913 ⟶ 893:
23
</pre>
=={{header|F_Sharp|F#}}==
===[https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Search_by_sieving sieving]===
<syntaxhighlight lang="fsharp">let rec sieve cs x N =
match cs with
| [] -> Some(x)
Line 947 ⟶ 926:
<br>
This uses [[Modular_inverse#F.23]]
<syntaxhighlight lang="fsharp">
//Chinese Division Theorem: Nigel Galloway: April 3rd., 2017
let CD n g =
Line 960 ⟶ 939:
CD [2;3;2] [3;5;7] -> Some 23
</pre>
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: math.algebra prettyprint ;
{ 2 3 2 } { 3 5 7 } chinese-remainder .</syntaxhighlight>
{{out}}
Line 968 ⟶ 946:
23
</pre>
=={{header|Forth}}==
Tested with GNU FORTH
<syntaxhighlight lang="forth">: egcd ( a b -- a b )
dup 0= IF
2drop 1 0
Line 1,020 ⟶ 997:
10 11 4 22 9 19 3 >>>crt<<< .
</pre>
=={{header|FreeBASIC}}==
Partial {{trans|C}}. Uses the code from [[Greatest_common_divisor#Recursive_solution]] as an include.
<syntaxhighlight lang="freebasic">
#include "gcd.bas"
function mul_inv( a as integer, b as integer ) as integer
Line 1,058 ⟶ 1,034:
print chinese_remainder(n(), a())</syntaxhighlight>
{{out}}<pre>23</pre>
=={{header|Frink}}==
This example solves an extended version of the Chinese Remainder theorem by allowing an optional third parameter <CODE>d</CODE> which defaults to 0 and is an integer. The solution returned is the smallest solution >= d. (This optional parameter is common in many/most real-world applications of the Chinese Remainder Theorem.)
Line 1,065 ⟶ 1,040:
Input is validated and useful error messages are emitted if the input data is invalid. If a solution cannot be found, this returns the special value <CODE>undef</CODE>.
<syntaxhighlight lang="frink">/** arguments:
[r, m, d=0] where r and m are arrays of the remainder terms r and the
modulus terms m respectively. These must be of the same length.
Line 1,111 ⟶ 1,086:
23
</pre>
=={{header|FunL}}==
<syntaxhighlight lang="funl">import integers.modinv
def crt( congruences ) =
Line 1,126 ⟶ 1,100:
23
</pre>
=={{header|Go}}==
Go has the Extended Euclidean algorithm in the GCD function for big integers in the standard library. GCD will return 1 only if numbers are coprime, so a result != 1 indicates the error condition.
<syntaxhighlight lang="go">package main
import (
Line 1,173 ⟶ 1,146:
23 <nil>
</pre>
=={{header|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">class ChineseRemainderTheorem {
static int chineseRemainder(int[] n, int[] a) {
int prod = 1
Line 1,225 ⟶ 1,197:
{{out}}
<pre>23</pre>
=={{header|Haskell}}==
{{trans|Erlang}}
<syntaxhighlight lang="haskell">import Control.Monad (zipWithM)
egcd :: Int -> Int -> (Int, Int)
Line 1,265 ⟶ 1,236:
No modular inverse for 418 and 11
23</pre>
=={{header|Icon}} and {{header|Unicon}}==
{{trans|Python}} with error check added.
Works in both languages:
<syntaxhighlight lang="unicon">link numbers # for gcd()
procedure main()
Line 1,302 ⟶ 1,272:
->
</pre>
=={{header|J}}==
'''Solution''' (''brute force''):<syntaxhighlight lang="j"> crt =: (1 + ] - {:@:[ -: {.@:[ | ])^:_&0@:,:</syntaxhighlight>
'''Example''': <syntaxhighlight lang="j"> 3 5 7 crt 2 3 2
23
11 12 13 crt 10 4 12
1000</syntaxhighlight>
'''Notes''': This is a brute force approach and does not meet the requirement for explicit notification of an an unsolvable set of equations (it just spins forever). A much more thorough and educational approach can be found on the [[j:Essays/Chinese%20Remainder%20Theorem|J wiki's Essay on the Chinese Remainder Thereom]].
=={{header|Java}}==
Translation of [[Chinese_remainder_theorem#Python|Python]] via [[Chinese_remainder_theorem#D|D]]
{{works with|Java|8}}
<syntaxhighlight lang="java">import static java.util.Arrays.stream;
public class ChineseRemainderTheorem {
Line 1,363 ⟶ 1,331:
<pre>23</pre>
=={{header|JavaScript}}==
<syntaxhighlight lang="javascript">
function crt(num, rem) {
let sum = 0;
Line 1,401 ⟶ 1,368:
23
</pre>
=={{header|jq}}==
This implementation is similar to the one in C, but raises an error if there is no solution, as illustrated in the last example.
<syntaxhighlight lang="jq"># mul_inv(a;b) returns x where (a * x) % b == 1, or else null
def mul_inv(a; b):
Line 1,442 ⟶ 1,408:
chinese_remainder([10,4,9]; [11,22,19])
# jq: error: nogo: p=36 mods[0]=10
=={{header|Julia}}==
{{works with|Julia|1.2}}
<syntaxhighlight lang="julia">function chineseremainder(n::Array, a::Array)
Π = prod(n)
mod(sum(ai * invmod(Π ÷ ni, ni) * (Π ÷ ni) for (ni, ai) in zip(n, a)), Π)
Line 1,455 ⟶ 1,420:
{{out}}
<pre>chineseremainder([3, 5, 7], [2, 3, 2]) = 23</pre>
=={{header|Kotlin}}==
{{trans|C}}
<syntaxhighlight lang="scala">// version 1.1.2
/* returns x where (a * x) % b == 1 */
Line 1,500 ⟶ 1,464:
23
</pre>
=={{header|Lobster}}==
<syntaxhighlight lang=
def extended_gcd(a, b):
Line 1,550 ⟶ 1,513:
ok 1219
</pre>
=={{header|Lua}}==
<syntaxhighlight lang="lua">-- Taken from https://www.rosettacode.org/wiki/Sum_and_product_of_an_array#Lua
function prodf(a, ...) return a and a * prodf(...) or 1 end
function prodt(t) return prodf(unpack(t)) end
Line 1,602 ⟶ 1,564:
=={{header|M2000 Interpreter}}==
{{trans|C}}
<syntaxhighlight lang=
Function ChineseRemainder(n(), a()) {
Function mul_inv(a, b) {
Line 1,629 ⟶ 1,591:
<pre>23
</pre>
=={{header|Maple}}==
This is a Maple built-in procedure, so it is trivial:
<syntaxhighlight lang=
23
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
Very easy, because it is a built-in function:
<syntaxhighlight lang=
23</syntaxhighlight>
=={{header|MATLAB}} / {{header|Octave}}==
<syntaxhighlight lang=
s = prod(m) ./ m;
[~, t] = gcd(s, m);
f = s .* t * r';</syntaxhighlight>
{{out}}
<syntaxhighlight lang=
ans = 23</syntaxhighlight>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE CRT;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 1,723 ⟶ 1,680:
{{out}}
<pre>23</pre>
=={{header|Nim}}==
{{trans|C}}
<syntaxhighlight lang="nim">proc mulInv(a0, b0: int): int =
var (a, b, x0) = (a0, b0, 0)
result = 1
Line 1,752 ⟶ 1,708:
Output:
<pre>23</pre>
=={{header|OCaml}}==
This is without the Jane Street Ocaml Core Library.
<syntaxhighlight lang="ocaml">
exception Modular_inverse
let inverse_mod a = function
Line 1,781 ⟶ 1,736:
</syntaxhighlight>
This is using the Jane Street Ocaml Core library.
<syntaxhighlight lang="ocaml">open Core.Std
open Option.Monad_infix
Line 1,830 ⟶ 1,785:
- : int option = None
</pre>
=={{header|PARI/GP}}==
<syntaxhighlight lang="parigp">chivec(residues, moduli)={
my(m=Mod(0,1));
for(i=1,#residues,
Line 1,844 ⟶ 1,798:
Pari's chinese function takes a vector in the form <tt>[Mod(a1,n1), Mod(a2, n2), ...]</tt>, so we can do this directly:
<syntaxhighlight lang="parigp">lift( chinese([Mod(2,3),Mod(3,5),Mod(2,7)]) )</syntaxhighlight>
or to take the residue/moduli array as above:
<syntaxhighlight lang="parigp">chivec(residues,moduli)={
lift(chinese(vector(#residues,i,Mod(residues[i],moduli[i]))))
}</syntaxhighlight>
=={{header|Pascal}}==
A console application in Free Pascal, created with the Lazarus IDE.
Follows the Perl examples: (1) expresses each solution as a residue class; (2) if the moduli are not pairwise coprime, still finds a solution if there is one.
<syntaxhighlight lang="pascal">
// Rosetta Code task "Chinese remainder theorem".
program ChineseRemThm;
Line 1,992 ⟶ 1,945:
[19, 0] mod [100, 23] --> 1219 mod 2300
</pre>
=={{header|Perl}}==
There are at least three CPAN modules for this: ntheory (Math::Prime::Util), Math::ModInt, and Math::Pari. All three handle bigints.
{{libheader|ntheory}}
<syntaxhighlight lang="perl">use ntheory qw/chinese/;
say chinese([2,3], [3,5], [2,7]);</syntaxhighlight>
{{out}}
Line 2,002 ⟶ 1,954:
The function returns undef if no common residue class exists. The combined modulus can be obtained using the <code>lcm</code> function applied to the moduli (e.g. <code>lcm(3,5,7) = 105</code> in the example above).
<syntaxhighlight lang="perl">use Math::ModInt qw(mod);
use Math::ModInt::ChineseRemainder qw(cr_combine);
say cr_combine(mod(2,3),mod(3,5),mod(2,7));</syntaxhighlight>
Line 2,011 ⟶ 1,963:
=== Non-pairwise-coprime ===
All three modules will also handle cases where the moduli are not pairwise co-prime but a solution exists, e.g.:
<syntaxhighlight lang="perl">use ntheory qw/chinese lcm/;
say chinese( [2328,16256], [410,5418] ), " mod ", lcm(16256,5418);</syntaxhighlight>
{{out}}
<pre>28450328 mod 44037504</pre>
=={{header|Phix}}==
{{trans|C}}
Uses the function mul_inv() from [[Modular_inverse#Phix]] (reproduced below)
<!--<syntaxhighlight lang=
<span style="color: #008080;">function</span> <span style="color: #000000;">mul_inv</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">n</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 2,059 ⟶ 2,010:
1219
</pre>
=={{header|PicoLisp}}==
<syntaxhighlight lang=
(let (B0 B X0 0 X1 1 Q 0 T1 0)
(while (< 1 A)
Line 2,090 ⟶ 2,040:
(bye)</syntaxhighlight>
=={{header|Prolog}}==
Created with SWI Prolog.
<syntaxhighlight lang="prolog">
product(A, B, C) :- C is A*B.
Line 2,135 ⟶ 2,084:
above. Therefore, I had to write another version of the
Chinese Remainder Therorem
<syntaxhighlight lang="prolog">
/* Chinese remainder Theorem: Input chinrest([2,3,2], [3,5,7], R). -----> R == 23
or chinrest([2,3], [5,13], R). ---------> R == 42
Line 2,211 ⟶ 2,160:
</pre>
=={{header|PureBasic}}==
<syntaxhighlight lang=
DisableDebugger
DataSection
Line 2,297 ⟶ 2,245:
[( 11 . 10 )( 22 . 4 )( 19 . 9 )]
x = Division by zero</pre>
=={{header|Python}}==
===Procedural===
====Python 2.7====
<syntaxhighlight lang="python"># Python 2.7
def chinese_remainder(n, a):
sum = 0
Line 2,331 ⟶ 2,278:
====Python 3.6====
<syntaxhighlight lang="python"># Python 3.6
from functools import reduce
def chinese_remainder(n, a):
Line 2,370 ⟶ 2,317:
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<syntaxhighlight lang="python">'''Chinese remainder theorem'''
from operator import (add, mul)
Line 2,585 ⟶ 2,532:
([3, 5, 7], [2, 3, 2]) -> 23
([2, 3, 2], [3, 5, 7]) -> 'No solution: no modular inverse for 6 and 2'</pre>
=={{header|R}}==
{{trans|C}}
<syntaxhighlight lang="rsplus">mul_inv <- function(a, b)
{
b0 <- b
Line 2,634 ⟶ 2,580:
{{out}}
<pre>23</pre>
=={{header|Racket}}==
This is more of a demonstration of the built-in function "solve-chinese", than
Line 2,641 ⟶ 2,586:
Take a look in the "math/number-theory" package it's full of goodies!
URL removed -- I can't be doing the Dutch recaptchas I'm getting.
<syntaxhighlight lang="racket">#lang racket
(require (only-in math/number-theory solve-chinese))
(define as '(2 3 2))
Line 2,648 ⟶ 2,593:
{{out}}
<pre>23</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|C}}
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang="raku" line># returns x where (a * x) % b == 1
sub mul-inv($a is copy, $b is copy) {
return 1 if $b == 1;
Line 2,680 ⟶ 2,624:
{{out}}
<pre>23</pre>
=={{header|REXX}}==
===algebraic===
<syntaxhighlight lang="rexx">/*REXX program demonstrates Sun Tzu's (or Sunzi's) Chinese Remainder Theorem. */
parse arg Ns As . /*get optional arguments from the C.L. */
if Ns=='' | Ns=="," then Ns= '3,5,7' /*Ns not specified? Then use default.*/
Line 2,718 ⟶ 2,661:
===congruences sets===
<syntaxhighlight lang="rexx">/*REXX program demonstrates Sun Tzu's (or Sunzi's) Chinese Remainder Theorem. */
parse arg Ns As . /*get optional arguments from the C.L. */
if Ns=='' | Ns=="," then Ns= '3,5,7' /*Ns not specified? Then use default.*/
Line 2,749 ⟶ 2,692:
say 'no solution found.' /*oops, announce that solution ¬ found.*/</syntaxhighlight>
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br><br>
=={{header|Ruby}}==
Brute-force.
<syntaxhighlight lang="ruby">
def chinese_remainder(mods, remainders)
max = mods.inject( :* )
Line 2,764 ⟶ 2,706:
Similar to above, but working with large(r) numbers.
<syntaxhighlight lang="ruby">
def extended_gcd(a, b)
last_remainder, remainder = a.abs, b.abs
Line 2,793 ⟶ 2,735:
p chinese_remainder([10,4,9], [11,22,19]) #=> nil
</syntaxhighlight>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn egcd(a: i64, b: i64) -> (i64, i64, i64) {
if a == 0 {
(b, 0, 1)
Line 2,836 ⟶ 2,777:
}</syntaxhighlight>
=={{header|Scala}}==
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/9QZvFht/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/njcaS3BFT6GtaWT2cHiwXg Scastie (remote JVM)].
<syntaxhighlight lang=
object ChineseRemainderTheorem extends App {
Line 2,880 ⟶ 2,820:
}</syntaxhighlight>
=={{header|Seed7}}==
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i";
include "bigint.s7i";
Line 2,911 ⟶ 2,850:
23
</pre>
=={{header|Sidef}}==
{{trans|Raku}}
<syntaxhighlight lang="ruby">func chinese_remainder(*n) {
var N = n.prod
func (*a) {
Line 2,929 ⟶ 2,867:
23
</pre>
=={{header|SQL}}==
{{works with|SQLite|3.34.0}}
<syntaxhighlight lang=
insert into inputs values (2, 3), (3, 5), (2, 7);
Line 2,997 ⟶ 2,934:
{{out}}
<pre>23</pre>
=={{header|Swift}}==
<syntaxhighlight lang="swift">import Darwin
/*
Line 3,108 ⟶ 3,044:
{{out}}
<pre>23</pre>
=={{header|Tcl}}==
{{trans|C}}
<syntaxhighlight lang="tcl">proc ::tcl::mathfunc::mulinv {a b} {
if {$b == 1} {return 1}
set b0 $b; set x0 0; set x1 1
Line 3,131 ⟶ 3,066:
{{out}}
<pre>23</pre>
=={{header|uBasic/4tH}}==
{{trans|C}}
<syntaxhighlight lang="text">@(000) = 3 : @(001) = 5 : @(002) = 7
@(100) = 2 : @(101) = 3 : @(102) = 2
Line 3,195 ⟶ 3,129:
0 OK, 0:1034
</pre>
=={{header|VBA}}==
Uses the function mul_inv() from [[Modular_inverse#VBA]]
{{trans|Phix}}<syntaxhighlight lang="vb">Private Function chinese_remainder(n As Variant, a As Variant) As Variant
Dim p As Long, prod As Long, tot As Long
prod = 1: tot = 0
Line 3,226 ⟶ 3,159:
fail
1219 </pre>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
Function ModularMultiplicativeInverse(a As Integer, m As Integer) As Integer
Line 3,271 ⟶ 3,203:
23 = 3 (mod 5)
23 = 2 (mod 7)</pre>
=={{header|Wren}}==
{{trans|C}}
<syntaxhighlight lang="ecmascript">/* returns x where (a * x) % b == 1 */
var mulInv = Fn.new { |a, b|
if (b == 1) return 1
Line 3,311 ⟶ 3,242:
23
</pre>
=={{header|zkl}}==
{{trans|Go}}
Using the GMP library, gcdExt is the Extended Euclidean algorithm.
<syntaxhighlight lang="zkl">var BN=Import("zklBigNum"), one=BN(1);
fcn crt(xs,ys){
Line 3,328 ⟶ 3,258:
return(X % p);
}</syntaxhighlight>
<syntaxhighlight lang="zkl">println(crt(T(3,5,7), T(2,3,2))); //-->23
println(crt(T(11,12,13),T(10,4,12))); //-->1000
println(crt(T(11,22,19), T(10,4,9))); //-->ValueError: 11 not coprime</syntaxhighlight>
=={{header|ZX Spectrum Basic}}==
{{trans|C}}
<syntaxhighlight lang="zxbasic">10 DIM n(3): DIM a(3)
20 FOR i=1 TO 3
30 READ n(i),a(i)
| |||