Greatest common denominator - saidai koyakusuu

For two or more positive integers, an integer (divisor) that divides all of them is called the common divisor of the first integers, and the largest of the common divisors is called the greatest common divisor. Greatest Common Measure is also abbreviated as GCM. All common divisors are divisors of the greatest common divisor. To find the greatest common divisor, you can use the idea of ​​prime factorization as follows.

One way to find the greatest common divisor of two numbers is to divide them by the remainder in turn. This is called Euclidean algorithm. For two integers, if their greatest common divisor is 1, then the two numbers are said to be relatively prime. For two integers a and b, if their greatest common divisor is g, then a = a'g and b = b'g, meaning that a' and b' are relatively prime.

[Tatsuro Miwa]

Source: Shogakukan Encyclopedia Nipponica About Encyclopedia Nipponica Information | Legend

二つ以上の正の整数について、そのどれをも割り切る整数（約数）を、初めの整数の公約数といい、公約数のうちで最大のものを最大公約数という。英語のGreatest Common Measureを略してG.C.M.とも書く。公約数はすべて最大公約数の約数になっている。最大公約数を求めるには、素因数分解の考えを基にして、次のようにすればよい。

　二つの数の最大公約数を求めるのに、順に余りで割っていくやり方がある。これをユークリッドの互除法という。二つの整数について、その最大公約数が1のとき、この2数は互いに素であるという。二つの整数a、bについて、最大公約数をgとすると、a＝a′g，b＝b′gと表すことができて、a′とb′は互いに素である。

［三輪辰郎］

出典　小学館　日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について　情報 | 凡例