Fix division

2 files changed, 15 insertions, 3 deletions

diff --git a/test b/test
index 4b426c2..d80dc2b 100755
--- a/test
+++ b/test
@@ -141,6 +141,16 @@ public:
                 assert_equal(p, 92);
         }
 },
+{
+        .name = "4 / 2 mod 6",
+        .f = []() {
+                Zmod<6> four = 4;
+                Zmod<6> two = 2;
+                auto d = four / two;
+                assert_equal(d.has_value(), true);
+                assert_equal(d.value(), 2);
+        }
+},
 };
 
 int main() {
diff --git a/zmodn.h b/zmodn.h
index fdb1ee6..890fb0e 100644
--- a/zmodn.h
+++ b/zmodn.h
@@ -40,13 +40,15 @@ public:
         bool operator!=(const Zmod& z) const { return value != z.value; }
 
         std::optional<Zmod> inverse() const {
-                auto [g, a, _] = extended_gcd(value, N);
+                auto [g, a, b] = extended_gcd(value, N);
                 return g == 1 ? Zmod(a) : std::optional<Zmod>{};
         }
 
         std::optional<Zmod> operator/(const Zmod& d) const {
-                auto i = d.inverse();
-                return i ? (*this) * i.value() : i;
+                auto [g, x, y] = extended_gcd(value, d.toint());
+                auto [a, b] = std::pair<Zmod, Zmod>{value / g, d.toint() / g};
+                auto i = b.inverse();
+                return i ? a * i.value() : i;
         }
 
         std::optional<Zmod> operator/=(const Zmod& d) {