整数

約数・倍数

互いに素

素因数分解の一意性，素数

連続する整数の積

整数解を求める

文字の範囲を絞る #

剰余類で分ける

個別に覚えておく

因数分解

約数・倍数 #

ユークリッド互除法

対称性，規則性

大小関係の導入→文字の統一

実数条件（平方完成）

必要条件＋約数・倍数 #

偶奇性

剰余の定理 $a = bq + r$

合同式

オイラー関数

$ n進法 $

ガウス記号

部屋割り論法

無限降下法

最大公約数・最小公倍数

素数

定義

1とその数以外を約数にもたない自然数 $ ( p \geq 2 ) $

素因数分解

約数のペア・積

素数は無限に存在する

約数の個数

$ a_1^{p_1} \times a_2^{p_2} \times \, \cdots \, \times a_m^{p_m} (a_kは素数) $

$ (p_1+1)(p_2+1) \, \cdots \, (p_m+1) $

約数の総和

$ a_1^{p_1} \times a_2^{p_2} \times \, \cdots \, \times a_m^{p_m} (a_kは素数) $

$ \left(1+a_1+a_1^2+ \, \cdots \ a_1^{p_1} \right) \left( 1+a_2+a_2^2 + \,\cdots \, a_2^{p_2} \right) \, \cdots \cdots \, \left(1+a_m+a_m^2+ \, \cdots \, +a_m^{p_m} \right) $

定義

1以外に公約数を持たない2つの自然数のこと

背理法で示す

$ a = Ga', b=Gb' (a', b'は互いに素，Gは最大公約数，Lは最小公倍数) $

性質

$ L=Ga'b' $

$ab = GL $

性質

$ 0 \leq r < b $

$ \textbf{自然数 N 以下の自然数で，Nと互いに素なものの個数} $

$ n! が m^k で割り切れる \Longleftrightarrow n! は m を因数としていくつ持つか？ $ #

2整数の積 $ n(n+1)は2の倍数 $

3整数の積 $ n(n+1)(n+2)は6の倍数 $

ユークリッドの互除法を使う

素因数は，$\sqrt{n} $以下について調べればよい

$ aA = bBでa,bが互いに素 \Rightarrow Aはbの倍数，Bはaの倍数 $

$ 2整数a,bが互いに素 \Longleftrightarrow a+b,abが互いに素 $

連続する整数は互いに素

背理法でよくある流れ

「互いに素でないとする」→「素数pを約数にもつ」で矛盾を示す

$ ax^2 + bxy +cy^2 + dx + ey +f =0 $

因数分解できる

$ (x, yの1次式) \times (x, yの1次式) = (整数) $

因数分解できない

$判別式D $

循環小数

循環節

差をとって消去

$ \textbf{変数を含む等式の必要十分条件} \Longrightarrow \\ \textbf{変数に具体的な値を代入して必要条件を求めよ.} $

中国剰余定理

分類

2つ

$ n = 2k-1, 2k \\ n = 2k,2k+1 $

3つ

$ n = 3k, 3k \pm 1 \\ n =3k, 3k+1, 3k+2 $

倍数の判定法

3の倍数，9の倍数

7の倍数

11の倍数

各位の数の和が3の倍数（9の倍数）

(偶数桁の位の和) - (奇数桁の位の和) が11の倍数

4の倍数，8の倍数

下2桁が4の倍数(00含む)，下3桁が8の倍数

不定方程式

1次不定方程式

$ N =a_1^{p_1} \times a_2^{p_2} \times \, \cdots \, \times a_m^{p_m} $

$ \phi(N) = N \left(1-\cfrac{1}{a_1}\right) \left( 1- \cfrac{1}{a_2} \right) \, \cdots \, \left(1- \cfrac{1}{a_m} \right) $

$ かけてnになるペアが存在する$

約数の積

$ \sqrt{n^m} (mは約数の個数) $

$ Ax+By = C (A, B, Cは整数) $

$ax = by $

$ (x, y) = (bk, ak) \, ( k は整数) $

$ a と b は互いに素 $

$ ax + by = c $

特殊解を見つける

カン

互除法

1つの文字について解く

$x, yは整数であることを利用 $

$ \left(\alpha の1次式 \right) \times \left( \beta の1次式 \right) = \left(整数 \right) を作る $

変換

$ n 進法 \Longrightarrow 10進法 $

$ 10進法 \Longrightarrow n進法 $

各位を分けて考える

$ \textbf{商が0になるまでnで割り算を続ける.} $

$ n\textbf{進法で表したとき，m桁となる自然数}a \Longleftrightarrow \, n^{m-1} \leq a < n^m $

$ 0, 1, \, \cdots \cdots, n-1 \, \textbf{のn種類の数字で表される自然数の列はn進法で考える} $

定義 $ \left( x, y \in \mathbb{R}, n \in \mathbb{Z} \right) $

$ n \leq x < n+1 \Longrightarrow [x] = n $

$ n \, は \, x \, の整数部分である. $

$ n \, は \, x \, を超えない最大の整数である. $

性質

$ x-1 < [x] \leq x $

$ [x] + [y] \leq [x+y] $

$ [x+n] = [x] + n $

具体的な数字で実験する

$ p と k は互いに素 (k = 1, 2, \, \cdots, p-1 ) $

$ x>y のとき，\begin{align} &x-y<1 \Longrightarrow [x]-[y]=0, 1 \\ &x-y \geq1 \Longrightarrow [x]-[y]\geq1 \end{align} $

$ x+nの整数部分は，xの整数部分にnを足したもの $

切り下げてから足すと，足してから切り下げたもの以下になる

定義

$ aをmで割った余りと，bをmで割った余りが等しい \\ \Longleftrightarrow aとbはmを法として合同である.$

$ a \equiv b \, (\mathrm{mod} \, m) $

$ 「素数でない」\Longleftrightarrow 「合成数または１」 $

2乗して4で割る問題

性質

$ a \equiv b \, ( \mathrm{mod} \, m), \, c \equiv d \, ( \mathrm{mod} \, m) $

$ a+c \equiv b+d \, ( \mathrm{mod} \, m) $

$a-c \equiv b-d \, ( \mathrm{mod} \, m) $

$ac \equiv bd \, ( \mathrm{mod} \, m) $

$ a^n \equiv b^n \, ( \mathrm{mod} \, m) $

フェルマーの小定理

$ n^p - n は pの倍数である (nは自然数，pは素数) $

$ a \equiv 1 \, ( \mathrm{mod} \, m) \textbf{のとき，} a^n \equiv1 \, ( \mathrm{mod} \, m) \textbf{の利用を考える} $

$ n+1人をn部屋に入れるとき，少なくとも1部屋は2人以上入る $

$ a \equiv b \, (\mathrm{mod} \, m) \Longleftrightarrow a-b = mk \left(a, b, k \in \mathbb{Z}, m \in \mathbb{N} \right) $

実際に書き並べてみる

不定方程式を用いる

合同式を用いる

絞る

文字の大小関係をうまく利用し，文字の範囲を絞り込む

互いに素である自然数の個数は，補集合の考えを利用せよ.

互いに素な2つの自然数の最大公約数は1

証明

$ k \cdot {}_p \mathrm{C}_k = p \cdot {}_{p-1} \mathrm{C}_{k-1} $

$ k = 1, 2, \, \cdots, \, p-1 より，kとpは互いに素なので{}_p \mathrm{C}_kはpの倍数 $

二項定理

$ {}_p \mathrm{C}_kがかかってない項がpの倍数と示す $

数学的帰納法

$ nとpが互いに素なとき， n^{p-1} \equiv 1 \, (\mathrm{mod} \, p) $

$ 整数\,n\,を整数\,m\,(m>0)で割ったときの商がq,余りがr $

$ n\,は\,x\,の切り捨てである. $

$ x = n + \alpha \, \left( 0 \leq \alpha < 1 \right) $

最小数を設定せよ

使用例

無理数の証明

$ x^n + 2y^n = 4z^n (nは3以上の自然数)は成立しない $

ディオファントス方程式

ペル方程式

$ x^2 - dy^2 =1 (d>0, dは平方数でない) $

$ x_k + y_k \sqrt{d} = \left(x+y\sqrt{d} \right)^n $と変形できる

自然数解 $ (x_0, y_0) $が無限に存在する