§最大公約数(Greatest Common Divisor)

用語と表記の説明(Terms and Definitions)

絶対値(absolute value)

「何の」絶対値かという、絶対値の対象が、実数・複素数・ベクトルのそれぞれの場合に分けて定義されている。
実数の場合は、a が正(a > 0)なら a を、a が負(a < 0)なら -a を a の絶対値という。
実数または複素数またはベクトルの a にたいして、絶対値を |a| と表記する。

商(quotient), 余り(remainder), 割り切れる(exactly divisible)

a, b, q, r を整数とする。
b ≠ 0 であるような a, b の値を与えられたとき、

a = bq + r , 0 ≦ r < |b|
となる q, r はただ1通り必ず存在する。
そのときの q を商、r を余りという。
もし r = 0 ならば「a は b で割り切れる」という。このとき b は a の約数である。
a = 0 , b ≠ 0 のとき、
0 = b × 0 + 0
となり、 0 は b で割り切れる。
b = 0 のとき、
a = 0 × x + a
となり、 0 ≦ r < |b| = 0 の範囲にある余り r が存在できないから、解がない。

剰余(remainder)

割った余り。

倍数(multiple)

ある数 b に整数 q をかけた数 a を、b の倍数という。

約数(divisor,measure)

整数 aを割り切れることができる整数 b を、a の約数という。
b が a の約数ならば、a は b の倍数である。
「整数 a の約数」の中で最大の数は |a| である。
0 の約数は整数全体である。
1 の約数には 1 と -1 しかない。
経験上、ある問題を考えるとき、マイナスの約数を考慮しない場合が多い。

a | b

a が b の約数のとき、a | b と表す。
つまり、a, b, k を整数として、ka = b のことを、a|b と表す。
例: 4 | 12 , 5 | 20

公約数(common divisor)

少なくとも 1 つは 0 でない 2 つ以上の整数に共通な約数を、公約数という。
たとえば、 255 と 153 の2つの整数の公約数には、3, 17, 51 がある。
24, 48, 56 の公約数には、1, 2, 4, 8 がある。
0, 1 の公約数には、1 がある。

最大公約数(Greatest Common Divisor, Greatest Common Measure)

少なくとも 1 つは 0 でない 2 つ以上の整数に共通な約数のうち最大の数を、最大公約数という。
別の言い方をすれば、2 つ以上の整数の公約数のうち最大の数を、最大公約数という。

gcd( a1 , a2 , a3 , … , an )
を、a1 , a2 , a3 , … , an の最大公約数を返す関数とする。

たとえば、
gcd( 15 , 42 ) = gcd( 3 × 5 , 2 × 3 × 7 ) = 3
である。
15 , 42 をそれぞれ gcd( 15 , 42 ) の結果である 3 で割ると、 5, 14 になる。 5, 14 の最大公約数を調べると
gcd( 5 , 14 ) = gcd( 5 , 2 × 7 ) = 1 である。
またたとえば、
gcd( 1200 , 10500 )
= gcd( 2 × 2 × 2 × 2 × 3 × 5 × 5 , 2 × 2 × 3 × 5 × 5 × 5 × 7 )
= 2 × 2 × 3 × 5 × 5 = 300
である。
では、最大公約数を計算してみましょう。
整数を入れてください。
a =
b =

結果です。
gcd( a , b ) =
a =
b =

自然数 a を素因数分解した形を思い浮かべることは、最大公約数 (Greatest Common Divisor) を考えるときに理解の助けになる。
gcd( 1200 , 10500 ) を手で計算するとき、まず

1200 = 24 × 3 × 52
10500 = 22 × 3 × 53 × 7
と素因数分解する。2つの素因数分解の結果の中に、共通の素数を探す。
2, 3, 5 が共通の素数である。そして、2つの素因数分解の結果の中で、共通の素数が何乗されているかを調べて、累乗の数の小さいほうを採用する。
すると、
最大公約数の中間結果を掛け合わせると、 gcd( 1200 , 10500 ) が得られる。
gcd( 1200 , 10500 ) = 22 × 3 × 52 = 300

最大公約数に関する定理(theorem)

a, b, c, d を整数とする。 n, m を自然数とする。

ユークリッドの互除法(Euclidean Algorism)

定理

自然数 a , b に対し、
a を b で割った余りを r とする (つまり a = bq + r )
ならば gcd( a , b ) = gcd( b , r ) である。

この定理を何回も使って最大公約数を求める計算方法を、ユークリッドの互除法という。

a , b の約数を調べ上げて最大公約数を求めるよりずっと簡単な方法である。

では、ユークリッドの互除法を計算してみましょう。
整数を入れてください。
a =
b =

結果です。
gcd( a , b ) =
計算過程:

互いに素(relatively prime)

gcd( a , b ) = 1 のとき、a と b は互いに素であるという。
例えば、gcd( 10 , 21 ) = 1 だから、10 と 21 は互いに素である。
gcd( 1 , 1 ) = 1 だから、1 と 1 は互いに素である。
gcd( 57 , 39 ) = 3 だから、57 と 39 は互いに素でない。

ある整数 a が与えられたとき、 gcd( a , x ) = 1 となるような x は、必ず存在する。

§ディオファンタス方程式

ここで使われる用語と表記の説明(Terms and Definitions)

整数解

方程式の解のうち、整数のもの。

ディオファンタス方程式

y = 2x + 3 というような、解が無限にあるような方程式を一般に不定方程式 (Indeterminate Equation)という。
不定方程式の解のうち、整数解だけを求める問題が整数論で興味の対象になる。方程式の係数が整数であるような不定方程式の、整数解だけを求める不定方程式は、 ディオファンタス方程式、または ジオファンタス方程式 (Diophantine Equation)とも呼ばれる。ディオファンタス方程式の中でも特別なケースとして、未知数が2つの1次の不定方程式の解が整数となる場合は、次のような形になる。

a, b, c, x, y を整数として、 ax + by = c
どのような場合に整数解を持つかというと、
gcd( a , b ) | c のとき、かつそのときに限り、 ax + by = c を満たす整数解 x , y が存在する。

x , y の一組の整数解は、a , b の最大公約数を求めるユークリッドの互除法の計算過程を逆にたどって得ることができる。

では、
ax + by = c , c = gcd( a , b )
の場合の x , y の一組の整数解を求めてみましょう。

ax + by = gcd( a , b )
整数を入れてください。
a =
b =

結果です。
gcd( a , b ) =
x =
y =
計算過程:

ax + by = c , gcd( a , b ) | c の x , y の整数解のうちの一組は、上の結果の両辺を c / gcd( a , b )倍すれば得られる。

最小公倍数 (Least Common Multiple, LCM)

少なくとも 1 つは 0 でない 2 つ以上の整数に共通な倍数のうち最小の数を、最小公倍数という。

lcm( a1 , a2 , a3 , … , an )
を、a1 , a2 , a3 , … , an の最小公倍数を返す関数とする。

gcd( a1 , a2 , a3 , … , an ) lcm( a1 , a2 , a3 , … , an ) = a1a2a3 … an
である。