自然数にを含める.を自然数全体の集合,を整数全体の集合とする.
定義 1.
整数に対してとなる整数が存在するとき,をの倍数とよび,をの約数とよぶ.に共通する倍数のことをの公倍数という.の正の公倍数のうち,最も小さなものをの最小公倍数という.また,に共通する約数のことをの公約数という.の公約数のうち,最も大きなものをの最大公約数という.整数の最大公約数がであるとき,は互いに素であるという.
定理 1 (除法の定理).
整数と正の整数に対してを満たす整数が一意的に存在する.
の部分集合に対して,は空でないので,最小元が存在する.の最小性よりより小さな元はの元ではない.より.よりあるが存在してと表せる.このとき,だが,はより小さいので,の元ではない.ゆえに.よって,すなわち.以上より.次に一意性を示す.とすると,より,はの倍数である.よりが成り立つ. より大きくより小さいの倍数はしかないので ,すなわち.また,かつより.
定義 2.
整数と正の整数に対し,前命題によって定まるををで割ったときの商,を余りという.余りがのとき,はで割り切れるといい,で表す.
定理 2 (公倍数は最小公倍数の倍数).
の最小公倍数をとする.をの公倍数とするとき,はの倍数である.
をで割る.すなわち,を満たす整数をとる.において,とはの公倍数だから,もの公倍数である.であり,が最小の公倍数であることより,が成り立つ.すなわち,はの倍数である.
定理 3 (公約数は最大公約数の約数).
の最大公約数をとする.をの公約数とするとき,はの約数である.
の最小公倍数をとする.を示せば,はの倍数,すなわち,はの約数であることが示せる.公倍数の定義より.また,はの倍数かつの倍数より,の公倍数である.よって,前命題よりはの倍数.同様にすればはの倍数.したがって,はの公約数.は最大公約数だから,.ゆえに.
定理 4.
整数に対してをの最大公約数とすると,整数を用いてと表せる.このとき,は互いに素である.
の公約数をとすると,はの公約数になる.は最大の公約数だから,.ゆえに,は互いに素.
定理 5.
整数 に対して,をの最小公倍数,をの最大公約数とするとき,が成り立つ.
前命題より,互いに素な整数を用いてと表せる.このとき,とすると,より,はの公倍数である.公倍数は最小公倍数の倍数だから,を満たす整数が存在する. よりであり,はで割り切れるので,はで割り切れる.同様によりであり,はで割り切れるので,はで割り切れる.すなわち,はの公約数である.は互いに素だから.すなわち,.ゆえに .以上よりが成り立つ.
定理 6.
整数が互いに素でかつがで割り切れるとき,はで割り切れる.
が互いに素であることより, はの最小公倍数.また,はで割り切れるから,の公倍数.したがって,はの倍数.ゆえに,はで割り切れる.
定義 3 (素数).
より大きい整数がと以外に約数を持たないとき,を素数とよぶ.
定理 7.
を素数とする.整数がで割り切れないならば,は互いに素である.
対偶を示す.が互いに素でないとすると,はより大きい公約数をもつ.は素数だからその約数はまたはなので,.よってはで割り切れる.
定理 8 (数の元素).
を整数,を素数とする.がで割り切れるならば,がで割り切れるか,がで割り切れる.
がで割り切れるとする.がが割り切れるならば,主張は正しい.がで割り切れないとき,前命題より,とは互いに素である.がで割り切れるので,定理 6よりがで割り切れる.
定理 9.
を正の整数とする.個の整数の積が素数で割り切れるとき,そのどれかはで割り切れる.
についての帰納法.個の整数の積がで割り切れれば,そのつの整数がで割り切れている.個未満の整数の積がで割り切れると,そのどれかがで割り切れるとする.個の整数に対してがで割り切れるとする.がで割り切れるならば主張は正しい.がで割り切れないとき,前命題よりはで割り切れる.帰納法の仮定よりのどれかはで割り切れる.
定理 10 (素因数分解の可能性).
より大きい任意の正の整数は,素数の積である.ここで,素数そのものも素数の積とみなす.
についての帰納法.のとき,は素数なので主張は正しい.として,より大きくより小さな整数が素数の積であると仮定する.が素数のとき主張は正しい.が素数でないとき,より大きくより小さい正の整数が存在してと表せる.帰納法の仮定より,は素数の積だからも素数の積である.
定理 11 (素因数の存在).
より大きい整数に対して,ある素数と整数が存在してと表せる.
前命題よりは素数の積で表せるので,主張は正しい.
定義 4 (素因数リスト).
より大きい正の整数に対して,を満たす素数の列を,の素因数リストと呼ぶ.素因数分解の可能性より,素因数リストは少なくとも1つ存在する
定理 12 (素数の素因数リスト).
素数に対して,の素因数リストはであり,一意的である.
がの素因数リストだとするとと表せる.各はの約数なので,かである.しかし,は素数なので.すなわち.よってとなり,の素因数リストはしかありえない.
定理 13 (素因数分解の一意性).
をより大きい整数とする.の素因数リストは一意的である.すなわち,2つの列が共にの素因数リストのとき,これらは等しい.つまり,かつ任意のに対してが成り立つ.
のときは前命題より素因数リストはしかない.として,より大きくより小さい整数の素因数リストが一意的だと仮定する.が素数の場合は,前命題よりが唯一つの素因数リストになる.が素数でないとき,をの最小の素因数とすると,を満たすより大きくより小さな正の整数が存在する.の素因数リストを任意にとると,と表せて,は素数だから定理 8より,はのいずれかを割り切り,が最小の素因数であることより,である.よって,の素因数リストを任意にとると,必ず最初の素数はになる.次にをの素因数リストとすると,かつはの素因数リストだから,帰納法の仮定よりこれらは等しい.以上よりのつの素因数リストは等しい.