定義 1.1. ''m'', ''n''を整数とする。''m'' =''an''となる整数''a''が存在する時、''m''は''n''の倍数であり、
''n''は''m''の約数であるといい、''n''|''m''と記す。
定理 1.2. ''l'', ''m'', ''n''を整数とする。
a) ''l''|''m'', ''m''|''n'' ならば ''l''|''n''。
b) ''l''|''m'', ''l''|''n'' ならば ''l''|(''m''+''n'')。
c) ''l''|''m'', ''l''|''n'' で ''a'', ''b'' が整数ならば ''l''|(''am''+''bn'')。
証明
a) ''m''=''al'', ''n''=''bm'' を満たす整数''a'', ''b''が存在する。よって''n''=''abl''であるから ''l''|''n'' 。
b) ''m''=''al'', ''n''=''bl'' を満たす整数''a'', ''b''が存在する。よって''m''+''n''=(''a''+''b'')''l''であるから ''l''|(''m''+''n'') 。
定義 1.3. ''m'', ''n''を0と異なる整数とする。
a) 整数''l''が ''m''|''l'' かつ ''n''|''l'' を満足する時 ''l'' を''m''と''n''の公倍数であるといい、整数''l''が ''l''|''m'' かつ ''l''|''n'' を満足する時 ''l'' を''m''と''n''の公約数であるという。
b) ''m''と''n''の最小の公倍数を [''m'', ''n''] と書き、''m''と''n''の最大の公約数を (''m'', ''n'') と書く。
注意. [''m'', ''n''] および (''m'', ''n'') という記法は別の意味に用いることもある。
定理 1.4. ''m'', ''n''を正の整数とする。このとき次の性質を満たす整数''a'', ''b''が存在する:
0\le b < n。
証明.
a=\lfloor m/n\rfloor, b=m-anとおく。このとき、''a'', ''b''は整数である。
また、a\le m/n < a+1 だから、an\le m < an+nである。よって
0\le b < nである。（証明終）
定理 1.5. ''m'', ''n''を0と異なる整数とし、''a''=(''m'', ''n'') とおく。このとき、
mx+ny=aを満たす整数''x'', ''y''が存在する。
証明.
''m'', ''n''は正の整数として差し支えない。max{''m'', ''n''}に関する帰納法で証明する。
m=n=1のときはx=1, y=0とおけばよい。
max{''m'', ''n''}≦''k''に対して定理が証明され、max{''m'', ''n''}=''k''+1と仮定する。
このときk+1=m\ge nと仮定しても差し支えない。
''n''|''m''ならばx=0, y=1とおけばよい。
''n''|''m''でなければ、定理 1.4よりm=an+b, 0\le b < nを満たす整数''a'', ''b''が存在する。
b \le n-1 \le kよりnu+bv=(n, b)を満たす整数''u'', ''v''が存在する。
定理 1.2 c)より(''n'', ''b'')|''m''だから、(''n'', ''b'')|(''m'', ''n'')である。よって
nw+bz=(m, n)を満たす整数''w'', ''z''が存在する。''b''=''m''-''an''より、
mb+n(w-ab)=(m, n)である。（証明終）