数論 - center_math @ ウィキ - atwiki（アットウィキ）

数論

数の種類

種類	記号	例
自然数	N	1,2,3,...
整数	Z	0,±1,±2,...
有理数	Q	1.5,2/3,...
無理数	なし	π,e, $\sqrt{2}$ ,...
実数	R	0,π, $\sqrt{2}$ ,...
複素数	C	1±i,3±2i,...

N∈Z∈Q∈R∈C

整数の組

有界

実数の部分集合Aに対し、
Aのどの元よりも大きい実数が存在するとき
Aは上に有界であるという。
Aのどの元よりも小さい実数が存在するとき
Aは下に有界であるという。

また、関数 $f(x)$ について、
定義域をA、値域を $f(A)=\{f(x)|x\in A\}$ とすると、
$f(A)$ が有界のとき、 $f(x)$ を有界関数という。

上限下限

範囲

証明

漸化式がらみの証明

(1)漸化式を解いて一般化する
(2)漸化式を漸化式のまま変形してa_1の状態まで示して用いる
(２つの漸化式がある場合はそのままで示せる場合多し)
(3)どうしても無理なら数学的機能法で処理する
(２つの仮定があるのなら、これらは同時に示さないと解けない場合多し)

存在証明

(1)数式で表して証明
(2)一般的に表せない場合は背理法で矛盾を示す

不等式証明

(a)相加相乗
$a&gt;0,b&gt;0$ のとき、 $a+b\ge 2\sqrt{ab}$
(b)平均値の定理
$\frac{f(b)-f(a)}{b-a}=f'(c)(a<c<b)$
(c)微積分
(d)二項定理

例
(1)帰納法
$a_{n+1}=\frac{{a_n}^2+1}{2a_n}(a_1>1)$
これの範囲を証明する。
数学的帰納法より、
$a_{k}>1 \Longleftrightarrow~ a_{k}-1>0$ とすると、
$a_{k+1}-1= \frac{{a_k}^2+1}{2a_k}-1 = \frac{(a_k-1)^2}{2a_k}>0$
なので $a_n&gt;1$ は証明される。
(2)帰納法強化版
$a_1,\frac{2^n}{n!}=\sum_{k=1}^{n+1}a_ka_{(n+1)-(k-1)}\iff a_n=\frac{1}{(n-1)!}$
これの証明では帰納法を用いるが、 $n\le l$ 以下全てこの仮定が成り立つとして計算する。
すると、
$\frac{2^l}{l!} = 2a_{l+1} + \sum_{k=2}^{l+1} \frac{1}{(k-1)!} \cdot \frac{1}{(l-k+1)!}$
$\frac{2^l}{l!} = 2a_{l+1} + \sum_{k=1}^{l-1} \frac{1}{k!} \cdot \frac{1}{(l-k)!}$
$\frac{2^l}{l!} = 2a_{l+1} + \frac{1}{l!}\sum_{k=1}^{l-1} \frac{l!}{(l-k)!k!} = 2a_{l+1} + \frac{1}{l!}\sum_{k=1}^{l-1} _lC_k = 2a_{l+1} + \frac{1}{l!}(2^{l}-2)$
$\Longleftrightarrow~ a_{l+1}=\frac{1}{l!}$

偶数であることを証明

a,bは整数とする。
abの少なくとも一つが偶数であることを証明
⇔ab=2Nを示せばよい。

無限数存在することを証明

漸化式を作り、これが単純増加であることを示す。
数の組の場合は、どれか一つの要素で示せればよい。

互いに素の証明

kan+kb+1とan+b(nは任意の整数)は互いに素。
なぜならば、 $\frac{kan+kb+1}{an+b}=k+\frac{1}{an+b}$ より
1とan+bは互いに素であるから、kan+kb+1とan+bも互いに素である

また、 $\frac{a}{b}=\frac{a}{c}+d$ が成り立つ時、
aとcが互いに素ならaとbも互いに素である。(a=km,b=knとおいて背理法で矛盾)

互いに素の活用

互いに素な整数a,bを考えると、
ある整数n,mについて、
$an=bm\iff n=kb,m=ka$
がいえる。

一般化

素数

p≧5のとき、
pは2の倍数でも3の倍数でもないことから、
一般的にp=6±1 の範囲としてあらわされる。
また、素数がp=(a+b)(a-b)であらわされるとき、
a-b=1となる。

奇数

奇数は累乗しても奇数である
$f(x)=\frac{1}{2}x^p$ において、
xが基数のとき、f(x)は必ず分数になる。
(例)
$2n=a^2+7$ が成り立つ時、 $a$ は奇数である

偶数

ある偶数 $a_1$ は
必ず他の数 $a_2$ を用いて、
$a_1=2a_2$ とあらわされる
したがって、任意の偶数 $a_k$ について
$a_k=2a_{k+1}$ が成り立つわけであるが、
これを延々と繰り返せばある奇数に帰着する。

素数倍

素数をsとして、xを有理数とする。
$sx^2=N$ ならば、
$s\frac{p^2}{q^2}=N$
よって、 $q^2=1,s$
だと分かるが、 $\sqrt{s}$ は整数でない。
よって、q=1よりxは整数だと分かる。

有理数

有理数は必ず、二つの互いに素な整数p,qを用いて、
$n=\frac{p}{q}$ とあらわせる。

倍数証明

$a$ が $b$ の倍数であることを証明するには、
$a=bN$ の形を導いて、 $N$ が整数であることを示せばよい。

対数

$\log_b a=\frac{1}{\log_a b}$

積と差の大小

a,bは0<a≦bを満たす自然数であるとすると、
a+b>ab⇔a=1
a+b=ab⇔(a,b)=(2,2)
a+b<ab⇔a≧2,b≧3
証明
3つめについて、b≧3とするとき、
ab-(a+b)≧2b-(2+b)=b-2>0

2つの文字式の関係

$x^2+xy+x^2$ と $x-y$
$(x^2+xy+x^2)-(x-y)^2=3xy$
より3の倍数になる。

ガウス記号

正確に表せない数値はガウス記号で表す。
[3]=3,[3.5]=3,[4]=4
が成り立つような式である。
このとき、
[x]≦x＜[x]+1
⇔x-1<[x]≦x
ガウス記号の極限はこの挟み込みで行う。

不定方程式

文字数を減らす
(　)(　)=　の形に持ち込む。

分数型

$\frac{a}{x}+\frac{b}{y}=\frac{q}{p}$
$\iff qxy-pay-pbx=0$
$\iff \left(x-\frac{pa}{q}\right)\left(y-\frac{pb}{q}\right)=\frac{p^2ab}{q^2}$

三乗数型

$a^3-b^3=mn$
$\iff (a-b)(a^2+ab+b^2)=mn$
$\iff m=a-b,n=a^2+ab+b^2$
故に、
$n=(m+b)^2+(m+b)b+b^2$
$\iff 3b^2+3mb+m^2-n=0$
このbは解の一つなので、
$D=-3m^2+12n \ge 0$
$m^2 \le 4n$
したがって、この条件を満たすようにm,nを選択したものには、
a,bの実数解が存在する。

今、 $a-b=p,a^2+ab+b^2=q$ が
上の条件によって求められたとすると、
$3ab=-p^2+q$
だとわかる。したがって、
$3ab=-p^2+q,a-b=p$
より、
$a=\frac{3p \pm \sqrt{-3p^2+12q}}{6}$

例
(1)
$m^3+1^3=n^3+10^3$
$\iff (m-n)(m^2+mn+n^2)=3^3\times 37$
(2)
$\frac{2}{x}+\frac{1}{y}=\frac{1}{4}$
$\iff xy-4x-8y=0$
$\iff (x-8)(y-4)=2^5$
(3)
$a+b+c+d=0,ad-bc+p=0,a\ge b\ge c\ge d$ ,pは素数
$d=-a-b-c$ より、
$p=(a+b)(a+c)=p×1$
(4)
$b(b+1)-(a-1)a=mn$
$\iff (b+a)(b-a+1)=mn$
(5)p,q素数,r整数
$\frac{1}{p}+\frac{1}{q}=\frac{1}{r}$
$\iff (p+q)r=pq$ より
rが整数である限り、成立しえない
(6)p,q素数,r整数
$\frac{1}{p}-\frac{1}{q}=\frac{1}{r}$
$\iff (q-p)r=pq$
よって、 $q-p=1 \iff p=2,q=3,r=6$ のときのみ成立

素数倍証明

共通因数を持つのであれば、kl,ml(lは素数)などと置いて考える。

因数

$x!$ を $p$ で割れる回数
$p^n<x<p^{n+1}$ とするとき、
＝ $1,2,3,..,x$ の中に、 $p^k$ (k=1～n)で割れる数が何個ずつあるかをそれぞれのkで調べ、
　それをまとめて足す。

数値の切り抜き

平均値の定理

$\frac{f(b)-f(a)}{b-a}=f'(c)(a<c<b)$
また、
$\lim_{a\to b}\frac{f(b)-f(a)}{b-a}=f'(b)$

$a_nb_n+a_{n+1}b_{n+1}$ の分断は、
$a_nb_n+a_{n+1}b_{n+1}=(a_n+a_{n+1})\frac{a_nb_n+a_{n+1}b_{n+1}}{a_n+a_{n+1}}=AB$

困難な大小比較

$a&gt;0,b&gt;0$ がわかっているとき、
$a&gt;b$ (n,m>0)を示すことは、
$a^2&gt;b^2$ を示すことに等しいので、
$a^2-b^2&gt;0$ を示せばよい。

総乗

累乗で式が与えられている場合は、
logで解体する。
$\prod f(x)=\sum \log f(x)$

二数による整数表現

互いに素な二つの自然数p,q(p<q)と整数a,bを用いると、
全ての整数Nは
$N=ap+bq$
で表せる。また、 $a\ge 0,b\ge 0$ のとき、
a=mとすると、
b=0でN=pmより、pの倍数の数を全てを表せる。
b=1でN=pm+qより、pの倍数+qの数を全てを表せる
b=2でN=pm+2qより、pの倍数+2qの数を全て表せる
...
a=p-1でN=pm+(p-1)qより、pの倍数+(p-1)qの倍数を全て表せる
以上より、この条件下では、 $N\ge q(p-1)$ を満たす整数の全てを満たせる。

ax+by=1

互いに素な整数a,bに対してこのようになる整数x,yが必ず存在する。

証明
(1)x≠yとする。x-y=kA(Aは特定の整数、kは不特定の整数)であれば、xとyをAで割ったあまりは等しい。
これは、 $x=AQ_1+R,y=AQ_1+R$ と変形できることからもわかる。
いま、Aと互いに素な数nを考えると、 $nx=A(nQ_1)+nR,ny=A(nQ_2)+nR$ より、
n(x-y)=kAとなる。このとき、nとAは互いに素より、x-y=k'Aとなる。
以上より、R(nx)=R(ny)⇒R(x)=R(y)

(2)(1)の対偶より、R(x)≠R(y)⇒R(nx)≠R(ny)
ここで、 $x=Ap+r_x,y=Aq+r_y$ を考えると、
$(0\le r_x\le A-1),(0\le r_y\le A-1)$ を満たしており、
それぞれ0～A-1までの全ての値をとりうる。
また、その過程において $r_x \ne r_y$ であれば
$r_x \ne r_y$ ⇒ $R(nx)\ne R(ny)$ と書きかえることができる。
よって、R(0),R(n),R(2n),...,R((a-1)n)は全て異なり、
したがって、この中のいずれか一つが、仮にそれをx=kとおけば、
R(kn)=1を満たす。

(3)(2)より、xがx=Ap+1 を満たすA、つまり、互いに素であるAで割った時、
nx=Aq+1 を満たすn,qが必ず存在する。

乗数と1桁の数

$x^n:a,b,c,...$ とする。
2:2,4,8,6
3:3,9,7,1
4:4,6
5:5
6:6
7:すべて
8:8,4,2,6
9;9,1
10:0

したがって、 $4^n-1>\frac{3}{2}\cdot 10$ は、
左辺の一の桁は3,5で、右辺は0なので、左辺に+1しても差支えがないとわかる。
よって、 $4^n>\frac{3}{2}\cdot 10$ を調べれば十分である。

タグ：

+ タグ編集

「数論」をウィキ内検索

最終更新：2013年04月13日 15:31

ツールボックス

下から選んでください:

新しいページを作成する

ヘルプ / FAQ もご覧ください。

center_math @ ウィキ

数論