Please enable JavaScript.
Coggle requires JavaScript to display documents.
整数 (個別に覚えておく (オイラー関数 (\( N =a_1^{p_1} \times a_2^{p_2} \times \, \cdots \,…
整数
個別に覚えておく
オイラー関数
\( \textbf{自然数 N 以下の自然数で，Nと互いに素なものの個数} \)
\( 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進法 \)
変換
\( 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 \, を超えない最大の整数である. \)
\( n\,は\,x\,の切り捨てである. \)
\( x = n + \alpha \, \left( 0 \leq \alpha < 1 \right) \)
性質
\( x-1 < [x] \leq x \)
\( [x] + [y] \leq [x+y] \)
切り下げてから足すと，足してから切り下げたもの以下になる
\( [x+n] = [x] + n \)
\( x+nの整数部分は，xの整数部分にnを足したもの \)
\( x>y のとき，\begin{align} &x-y<1 \Longrightarrow [x]-[y]=0, 1 \\ &x-y \geq1 \Longrightarrow [x]-[y]\geq1 \end{align} \)
具体的な数字で実験する
部屋割り論法
\( n+1人をn部屋に入れるとき，少なくとも1部屋は2人以上入る \)
無限降下法
最小数を設定せよ
使用例
無理数の証明
\( x^n + 2y^n = 4z^n (nは3以上の自然数)は成立しない \)
整数解を求める
因数分解
\( ax^2 + bxy +cy^2 + dx + ey +f =0 \)
因数分解できる
\( (x, yの1次式) \times (x, yの1次式) = (整数) \)
因数分解できない
\(判別式D \)
\( \left(\alpha の1次式 \right) \times \left( \beta の1次式 \right) = \left(整数 \right) を作る \)
約数・倍数
#
\( aA = bBでa,bが互いに素 \Rightarrow Aはbの倍数，Bはaの倍数 \)
倍数の判定法
3の倍数，9の倍数
各位の数の和が3の倍数（9の倍数）
7の倍数
11の倍数
(偶数桁の位の和) - (奇数桁の位の和) が11の倍数
4の倍数，8の倍数
下2桁が4の倍数(00含む)，下3桁が8の倍数
フェルマーの小定理
\( n^p - n は pの倍数である (nは自然数，pは素数) \)
\( nとpが互いに素なとき， n^{p-1} \equiv 1 \, (\mathrm{mod} \, p) \)
証明
\( 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の倍数と示す \)
数学的帰納法
ユークリッド互除法
不定方程式
1次不定方程式
\( Ax+By = C (A, B, Cは整数) \)
\(ax = by \)
\( (x, y) = (bk, ak) \, ( k は整数) \)
\( a と b は互いに素 \)
\( ax + by = c \)
特殊解を見つける
カン
互除法
1つの文字について解く
\(x, yは整数であることを利用 \)
ディオファントス方程式
ペル方程式
\( 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) \)が無限に存在する
絞る
文字の大小関係をうまく利用し，文字の範囲を絞り込む
文字の範囲を絞る
#
対称性，規則性
循環小数
循環節
差をとって消去
大小関係の導入→文字の統一
実数条件（平方完成）
必要条件＋約数・倍数
#
\( \textbf{変数を含む等式の必要十分条件} \Longrightarrow \\ \textbf{変数に具体的な値を代入して必要条件を求めよ.} \)
約数・倍数
互いに素
最大公約数・最小公倍数
\( a = Ga', b=Gb' (a', b'は互いに素，Gは最大公約数，Lは最小公倍数) \)
性質
\( L=Ga'b' \)
\(ab = GL \)
ユークリッドの互除法を使う
定義
1以外に公約数を持たない2つの自然数のこと
背理法でよくある流れ
「互いに素でないとする」→「素数pを約数にもつ」で矛盾を示す
性質
\( 2整数a,bが互いに素 \Longleftrightarrow a+b,abが互いに素 \)
連続する整数は互いに素
互いに素な2つの自然数の最大公約数は1
素因数分解の一意性，素数
素数
定義
1とその数以外を約数にもたない自然数 \( ( p \geq 2 ) \)
素数は無限に存在する
背理法で示す
\( p と k は互いに素 (k = 1, 2, \, \cdots, p-1 ) \)
\( 「素数でない」\Longleftrightarrow 「合成数または１」 \)
素因数分解
約数のペア・積
素因数は，\(\sqrt{n} \)以下について調べればよい
\( かけてnになるペアが存在する\)
約数の積
\( \sqrt{n^m} (mは約数の個数) \)
約数の個数
\( 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) \)
\( n! が m^k で割り切れる \Longleftrightarrow n! は m を因数としていくつ持つか？ \)
#
連続する整数の積
2整数の積 \( n(n+1)は2の倍数 \)
3整数の積 \( n(n+1)(n+2)は6の倍数 \)
剰余類で分ける
偶奇性
剰余の定理 \( a = bq + r \)
\( 0 \leq r < b \)
中国剰余定理
実際に書き並べてみる
不定方程式を用いる
合同式を用いる
分類
2つ
\( n = 2k-1, 2k \\ n = 2k,2k+1 \)
2乗して4で割る問題
3つ
\( n = 3k, 3k \pm 1 \\ n =3k, 3k+1, 3k+2 \)
\( 整数\,n\,を整数\,m\,(m>0)で割ったときの商がq,余りがr \)
合同式
定義
\( aをmで割った余りと，bをmで割った余りが等しい \\ \Longleftrightarrow aとbはmを法として合同である.\)
\( a \equiv b \, (\mathrm{mod} \, m) \)
\( a \equiv b \, (\mathrm{mod} \, m) \Longleftrightarrow a-b = mk \left(a, b, k \in \mathbb{Z}, m \in \mathbb{N} \right) \)
性質
\( 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) \)
\( a \equiv 1 \, ( \mathrm{mod} \, m) \textbf{のとき，} a^n \equiv1 \, ( \mathrm{mod} \, m) \textbf{の利用を考える} \)