Number theory

Greatest Common Divisor (factor) - Least Common Multiple

Keywords: Greatest Common Divisor (factor) - Least Common Multiple

Greatest Common Factor GCF

Greatest common factor of two integers m and n is:

GCF(m;n)=(m;n)=l

Eeuclidean algorithm for computing the greates common factor GCF

Example: GCF (246;132)=(246;132)=6

246=132·1+114132=114·1+18114=18·6+66=6·1+0

Least Common Multiple LCM

Least common multiple of two integers m and n is:

{formula_2329}

Connection between the greatest common divisor (GCD) and the least common multiple (LCM)

(m;n)·[m;n]=m·n

Example: LCM (246;132)=[246;132]=5412

246;132=246·132(246;132)=246·1326=5412

Relative Primes

Two integers m and n are relatively prime if they share no common positive factors (divisors) except 1. GCF(m;n)=[m;n]=1