2 files changed, 23 insertions, 1 deletions
diff --git a/stdlib/source/lux/data/number/int.lux b/stdlib/source/lux/data/number/int.lux
index 8d24d729d..e5b753725 100644
--- a/stdlib/source/lux/data/number/int.lux
+++ b/stdlib/source/lux/data/number/int.lux
@@ -127,7 +127,25 @@
   (-> Int Int Int)
   (case b
     +0 a
-    _ (gcd b (..mod b a))))
+    _ (gcd b (..% b a))))
+
+(def: #export (co-prime? a b)
+  (-> Int Int Bit)
+  (..= +1 (..gcd a b)))
+
+## https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
+(def: #export (extended_gcd a b)
+  {#.doc "Extended euclidean algorithm."}
+  (-> Int Int [[Int Int] Int])
+  (loop [x +1 x1 +0
+         y +0 y1 +1
+         a1 a b1 b]
+    (case b1
+      +0 [[x y] a1]
+      _ (let [q (/ b1 a1)]
+          (recur x1 (- (* q x1) x)
+                 y1 (- (* q y1) y)
+                 b1 (- (* q b1) a1))))))
 
 (def: #export (lcm a b)
   {#.doc "Least Common Multiple."}
diff --git a/stdlib/source/lux/data/number/nat.lux b/stdlib/source/lux/data/number/nat.lux
index b1504f048..267846c89 100644
--- a/stdlib/source/lux/data/number/nat.lux
+++ b/stdlib/source/lux/data/number/nat.lux
@@ -129,6 +129,10 @@
     0 a
     _ (gcd b (..% b a))))
 
+(def: #export (co-prime? a b)
+  (-> Nat Nat Bit)
+  (..= 1 (..gcd a b)))
+
 (def: #export (lcm a b)
   {#.doc "Least Common Multiple."}
   (-> Nat Nat Nat)