整数せいすうの性質せいしつの基本きほん

約数やくすうDivisor

$b\mid a$b \mid a（$b$b は $a$a を割わり切きる）とは、$a=bq$a = bq（$q$q は整数せいすう）が成立せいりつすることである。このとき $b$b を $a$a の約数やくすうDivisorという。

「約やく」の命名めいめい：約やくは「切きり詰つめる・縮ちぢめる」意味いみ。$a$a を縮ちぢめる因子いんしであることから命名めいめい。英語えいご divisor は「割わるもの」の意い。

倍数ばいすうMultiple

$a$a が $b$b の倍数ばいすうMultipleとは、$b\mid a$b \mid a が成立せいりつすることである。

「倍ばい」の命名めいめい：倍ばいは「2 倍ばい・3 倍ばい」の倍ばい。整数倍せいすうばいになっている数かずの全体ぜんたいの集合しゅうごうを指さす。英語えいご multiple は「複数ふくすうの」の意い。

最大公約数さいだいこうやくすうGreatest common divisor

$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,b)$\gcd(a, b) とは、$a$a と $b$b の共通きょうつう約数やくすうのうち最大さいだいのものである。

互たがいに素そCoprime

$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,b)=1$\gcd(a, b) = 1 のとき、$a$a と $b$b は互たがいに素そCoprimeであるという。

「素そ」の命名めいめい：共通きょうつう因子いんしが「素もと（1）」しかない、という意い。英語えいご coprime（co = 共ともに、prime = 素そ）。

素数そすうPrime number

2 以上いじょうの整数せいすうで、1 と自分自身じぶんじしんしか正せいの約数やくすうを持もたない数かずを素数そすうPrime numberという。

「素そ」の命名めいめい：因数分解いんすうぶんかいの最小単位さいしょうたんいであることから命名めいめい。英語えいご prime（原初げんしょの）。

1. 余あまりで見みる（偶奇ぐうき）

整数せいすう $n$n を 2 で割わると余あまりは 0 か 1 である：

これが偶数ぐうすうと奇数きすうの基本形きほんけいである。$n^2$n^2 が偶数ぐうすうなら $n$n も偶数ぐうすう、$n^2$n^2 が奇数きすうなら $n$n も奇数きすう—これは対偶たいぐうとして頻出ひんしゅつ。

2. 倍数ばいすう判定はんていの整理せいり

3. 最大公約数さいだいこうやくすうと最小公倍数さいしょうこうばいすう

これは素因数分解そいんすうぶんかいの指数しすうを $\min$\min（gcd）と $\max$\max（lcm）で処理しょりすることから直接ちょくせつ導みちびかれる。

4. 素因数分解そいんすうぶんかいの一意性いちいせい（算術さんじゅつの基本定理きほんていり）

2 以上いじょうの任意にんいの整数せいすうは、素数そすうの積せきとして本質的ほんしつてきに一意いちいに分解ぶんかいできる：

一意性いちいせいの保証ほしょうがなければ「因数分解いんすうぶんかいする」という操作そうさは意味いみを失うしなう。

5. 互たがいに素その性質せいしつ

$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,b)=1$\gcd(a, b) = 1 のとき：

• $a\mid bc⟹a\mid c$a \mid bc \implies a \mid c（互たがいに素そな性質せいしつのみを使つかう）
• $ax+by=1$ax + by = 1（一次いちじ不定方程式ふていほうていしきの解かいが存在そんざい）
• $ab\mid c$ab \mid c かつ $a\mid c$a \mid c かつ $b\mid c$b \mid c のとき相互そうごに利用りようできる

6. 合同式ごうどうしきへ

$a-b$a - b が $n$n の倍数ばいすうなら、$a$a と $b$b は $n$n で割わった余あまりが同おなじである。この「余あまりが同おなじ」という同値関係どうちかんけいから

という記法きほうが生うまれ、整数せいすうを余あまりごとの塊かたまり（剰余じょうよ類るい）として代数的だいすうてきに扱あつかえる。