Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Number Theory

All number-theory operations are available as both instance methods and free functions:

from decimo import BInt, gcd, lcm, extended_gcd, mod_pow, mod_inverse

GCD — Greatest Common Divisor

var a = BInt(48)
var b = BInt(18)
print(a.gcd(b))      # 6
print(gcd(a, b))      # 6 (free function)

LCM — Least Common Multiple

print(BInt(12).lcm(BInt(18)))    # 36
print(lcm(BInt(12), BInt(18)))   # 36

Extended GCD

Returns (g, x, y) such that a*x + b*y = g:

var result = BInt(35).extended_gcd(BInt(15))
# result = (5, 1, -2)   — since 35×1 + 15×(−2) = 5

Modular Exponentiation

Computes $(base^{exp}) \mod m$ efficiently without computing the full power:

print(BInt(2).mod_pow(BInt(100), BInt(1000000007)))
print(mod_pow(BInt(2), BInt(100), BInt(1000000007)))  # free function

Modular Inverse

Finds $x$ such that $(a \cdot x) \equiv 1 \pmod{m}$:

print(BInt(3).mod_inverse(BInt(7)))      # 5 (since 3×5 = 15 ≡ 1 mod 7)
print(mod_inverse(BInt(3), BInt(7)))      # 5