Search Results

3 results for “gcd”

Formulae (3)

\gcd(a,b) = \gcd(b, a \bmod b)

Recursively finds the greatest common divisor.

a^{p-1} \equiv 1 \pmod{p}

Holds when p is prime and gcd(a,p)=1.

\text{lcm}(a,b) = \frac{|a b|}{\gcd(a,b)}

Least common multiple via the greatest common divisor.