(証明) a, b の最大公約数を d , b, r の最大公約数を d ′ とする. d = d ′ を示せばよい.
まず, a = bq + r において, b, r は d ′ の倍数なので, a は d ′ の倍数である.つまり, a, b とも d ′ の倍数な
ので, d ′ は a, b の公約数である.よって, d ′ ≦ d ( ······· · ⃝) 1 である.
次に, a = bq + r ⇔ r = a − bq であり, a, b は d の倍数なので, r も d の倍数である.つまり, b, r とも d
1. a = gA, b = gB としたとき, 2 数 a, b の最小公倍数 d = gAB である.
2. gd = ab である.つまり, 2 数 a, b の最小公倍数・最大公約数の積は,積 ab に等しい.
(証明)最大公約数の定義より a = gA, b = gB について, A, B は互いに素である.
互いに素な 2 数 A, B の最小公倍数は AB なので, gA, gB の最小公倍数は gAB であり, a, b の最小公倍 数は d = gAB となり 1. が示された.
(証明) a, b の最大公約数を d , b, r の最大公約数を d ′ とする. d = d ′ を示せばよい.
まず, a = bq + r において, b, r は d ′ の倍数なので, a は d ′ の倍数である.つまり, a, b とも d ′ の倍数な
ので, d ′ は a, b の公約数である.よって, d ′ ≦ d ( ······· · ⃝) 1 である.
次に, a = bq + r ⇔ r = a − bq であり, a, b は d の倍数なので, r も d の倍数である.つまり, b, r とも d