整数の性質

　本記事は整数についての個人的なメモまとめです。厳密性より自分へのわかりやすさを優先しています。

0. 整数

整数とは

..., -3, -2, -1, 0, 1, 2, 3, ...　といった数のこと。整数全体の集合はZで表す。
・-1, -2, -3, ...を負の整数という
・1, 2, 3, ...を正の整数という
・0, 1, 2, 3, ...を非負整数という
・自然数とは正の整数または非負整数のこと。(0を含むかどうかは定義によって変わるため、以後この記事では自然数という表現を使わないことにする)

以下では特に断りのない限り正の整数に限定して説明する。

1. 倍数

・倍数とは

　ある数aを整数倍したもの、つまりa, 2a, 3a, ...のことをaの倍数という。
　またaの倍数はaで割り切れる整数である。
例1　2の倍数　{2, 4, 6, 8, 10, ...}
例2　7の倍数　{7, 14, 21, 28, ...} 　

・最小公倍数

　aの倍数かつbの倍数となるものをaとbの公倍数といい、公倍数の中で最も小さいものをaとbの最小公倍数という。
例1　2と3の公倍数は{6, 12, 18, 24, ...}　最小公倍数は6　
例2　4と6の公倍数は{12, 24, 36, 48, ...}　最小公倍数は12　

・nの倍数の条件

・2の倍数……下一桁が2で割り切れる
・3の倍数……すべての桁の和が3で割り切れる
・4の倍数……下二桁が4で割り切れる
・5の倍数……下一桁が0または5
・6の倍数……2の倍数、3の倍数の両方の条件を満たす
・7の倍数……数を3桁ごとに区切り符号を変えながら順番に足したときの和が7で割り切れる
・8の倍数……下三桁が8で割り切れる
・9の倍数……すべての桁の和が9で割り切れる

簡単な説明 ・2の倍数……10は2で割り切れるので ・3の倍数……10ⁿ≡1 (mod 3)なので ・4の倍数……100は4で割り切れるので ・5の倍数……10は5で割り切れるので ・6の倍数……2と3の公倍数、明らか ・8の倍数……1000は8で割り切れるので ・9の倍数……10ⁿ≡1 (mod 9)なので

コメント　7の倍数、使う機会なさそう

2. 約数

・約数とは

　ある整数を割り切ることのできる整数のこと。 例　10の約数は{1, 2, 5, 10}

・最大公約数

　整数a, bをともに割り切ることのできる整数を公約数といい、最も大きな公約数を最大公約数という。aとbの最大公約数が1(公約数が1のみ)のとき、aとbは互いに素であるという。 例　24と32の公約数は{1, 2, 4, 8}　最大公約数は 8

・ユークリッドの互除法

　最大公約数を求める有名アルゴリズム。計算量は a, b(a>b)の最大公約数を求めるには割り算の余り(a%b)でbを割り、そのあまりでa%bを割り……をあまりがゼロになるまで繰り返す。

aとbの最大公約数G,としてa=AG, b=BG (AとBは互いに素), 商q, 余りr(0≦r<b)としたとき となるから
すなわち
であるからrはGの倍数である。

AとBが互いに素であるからBと(A-qB)も互いに素である。よってbとrの最大公約数はGである。
一方で0≦r<bであるから余りは明らかに単調減少するため0に収束し、その時の割る数がGとなる。

3. 素数

・素数とは

　素数とは1と自分自身以外の約数を持たない整数
　2, 3, 5, 7, 11, 13, ...
　なお、2以上の素数でない数は合成数という。

・素数判定

　√Nまでの数で割り切れなければNは素数。

　面積Nの長方形をイメージしてみよう。
　長辺と短辺があるから短辺は√N以下の長さになるし、最大でも正方形のとき√Nだから√Nまで調べて割り切れなければそれは素数だ。
　約数をすべて知りたいときも√Nまででよい。短辺が分かれば長辺もわかるから。

・エラトステネスの篩

　n以下の素数を見つけるアルゴリズム。計算量は
　素数判定を何度も行うなら、あらかじめ全て求めておく。

　2~Nまでの数に対して小さいほうから順に
1. 素数リストに移動 2. 倍数を削除
を繰り返し、√Nまで判定した時点で残ったものをすべて素数リストに移動する。

・素因数分解

　合成数を素数の掛け算に分解する。

4. 合同式(mod)

合同とは

　大雑把に言えば「整数nで割った余りが等しい」
　123≡3 (mod 12), 24≡3 (mod 7)

　合同式の性質として
　・足し算, 123+5≡3+5≡8 (mod 12)
　・引き算, 24-3≡3-3≡0 (mod 7)
　・掛け算(累乗含む), 123²≡15129≡3³≡9 (mod 12)
が普通の整数と同様に扱える。
ただし合同式の割り算は一般には成り立たないため逆数に相当する逆元を用いる(らしい)。
逆元を求めるにはフェルマーの小定理か拡張ユークリッドの互除法を用いる。

「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita

・フェルマーの小定理

aとpが互いに素のとき
a^p-1≡1 (mod p)
逆元を求めるときに使える。