最大公約数
48 = 9 × 5 + 3 {\displaystyle 48=9\times 5+3} なので gcd ( 48 , 9 ) = gcd ( 9 , 3 ) {\displaystyle \gcd(48,9)=\gcd(9,3)} である。 9 = 3 × 3 + 0 {\displaystyle 9=3\times 3+0} なので gcd ( 9 , 3 ) = gcd ( 3 , 0 ) = 3 {\displaystyle \gcd(9,3)=\gcd(3,0)=3} であり、最大公約数が 3 {\displaystyle 3} であることがわかった。
このように最大公約数の定義や計算に素数や素因数分解などのような高級な概念は全く必要ないのだが、算術の基本定理が成り立つことを利用して最大公約数を明示的に表すこともできる。つまり、すべての素数から成る集合を P r i m e s {\displaystyle {\mathfrak {Primes}}} として、 a 1 , ... , a n {\displaystyle a_{1},\dots ,a_{n}} を
a i = ∏ p ∈ P r i m e s p e p ( i ) {\displaystyle a_{i}=\prod _{p\in {\mathfrak {Primes}}}p^{e_{p}(i)}}
と素因数分解すれば、次が成り立つ。
gcd ( a 1 , ... , a n ) = ∏ p ∈ P r i m e s p min { e p ( 1 ) , ...