Documentation

>>> powMod 2 0 1000000007
1
>>> powMod 0 0 1000000007
1
>>> powMod 2 1000000005 1000000007
500000004
>>> powMod 2 (-1) 1000000007
500000004
>>> powMod 123456789 998244353 998244353
123456789
>>> powMod (-2) 2 1000000007
4
>>> powMod (-2) 3 1000000007
999999999

>>> recipMod 2 1000000007
500000004
>>> recipMod 10 1000000007
700000005
>>> recipMod 0 1000000007
0

\x m -> not (m >= 1) || mod (x * recipMod x m) m == mod (gcd x m) m

+++ OK, passed 100 tests.

Extended Euclidean algorithm

(x, y, g) = extGCD a b (a * x + b * y = g)

>>> extGCD 3 5
(2,-1,1)
>>> extGCD 4 6
(-1,1,2)

\a b -> not (a > 0 && b > 0) || let (_, _ , g) = extGCD a b in g == gcd a b

+++ OK, passed 100 tests.

\a b -> not (a > 0 && b > 0) || let (x, y, g) = extGCD a b in a * x + b * y == g

+++ OK, passed 100 tests.

\a b -> not (a > 0 && b > 0) || let (x, y, g) = extGCD a b in abs x <= div b g && abs y <= div a g

+++ OK, passed 100 tests.

Solve a * x + b * y == c

If multiple solutions exists then return the minimum non-negative x.

If a /= 0, b /= 0, a * x + b * y == c then a (x - k * b / g) + b * (y + k * a / g) == c

>>> linearDiophantine 3 5 1
Just (2,-1)
>>> linearDiophantine 3 5 3
Just (1,0)
>>> linearDiophantine 4 6 2
Just (2,-1)
>>> linearDiophantine 4 6 3
Nothing
prop> \a b c -> maybe True (\(x, y) -> a * x + b * y == c) $ linearDiophantine a b c
+++ OK, passed 100 tests.

Chinese Remainder Theorem

x = r0 (mod m0), x = r1 (mod m1) ==> x (mod (lcm m0 m1))

>>> crt (10, 20) (10, 30)
Just (10,60)
>>> crt (10, 20) (10, 20)
Just (10,20)
>>> crt (10, 20) (11, 20)
Nothing

• p0, p1 are prime
• p0 /= p1 or r0 == r1

>>> crt' (2,3) (3,5)
8
>>> crt' (3,5) (3,7)
3
>>> crt' (3,7) (3,7)
3

>>> crts [(20,30),(30,50),(20,70)]
Just (230,1050)
>>> crts []
Just (0,1)
>>> crts [(1, 10), (2, 20), (3, 30)]
Nothing

x (mod m) (x = r[i] (mod m[i]))

gcd m[i] m[j] == 1

O(n^2)

>>> garner [(2, 3), (3, 5), (2, 7)] 999
23
>>> garner [(2, 3), (3, 5), (2, 7)] 10
3