情報安全数学の基礎第1編-数論の基礎-第1章の整除
3425 ワード
文書ディレクトリ第一章 を除く1整数の除算 2算数基本定理 3素数 4 Euclidアルゴリズム 第一章整理
1整数の除算
a b ∈ Z , b ≠ 0 , ab\in Z,be 0, ab∈Z,b̸=0であり、整数cが存在し、a=bcとする場合、bはaを除去し、b|aと記す.
b ≠ 0 , a ∣ b ⟹ ∣ a ∣ ≤ ∣ b ∣ be 0,a|b\Longrightarrow |a|\le|b| b̸=0,a∣b⟹∣a∣≤∣b∣
a ∣ b , b ∣ a ⟹ b = ± a a|b,b|a\Longrightarrow b=\pm a a∣b,b∣a⟹b=±a
a ∣ b , b ∣ c ⟹ a ∣ c a|b,b|c\Longrightarrow a|c a∣b,b∣c⟹a∣c
a∣b,a∣c⟺対任意t,s∈Z,a∣t b+s c a|b,a|cLongleftrightarrow対任意t,sin Z,a|tb+sc a∣b,a∣c⟺対任意t,s∈Z,a∣tb+sc a∣b+sc
$me0,a|b\Longleftrightarrow ma|mb $
[x]はxを超えない最大整数である
実数xの小数部
a,bは2つの整数であり,b≠0 be 0 b̸=0であると、a=q b+r,0≦rdはa,bの最大公約数であり,(a,b),またはgcd(a,b)と記す.
(a,b)=1である、a,b相互素は、公約数±1pm 1±1のみである.
mはa,bの最小公倍数である,[a,b],またはlcm(a,b)と記す.
(a,b)=(b,a)=(-a,b)=(a,-b)=(-a,-b)
[a,b]=[b,a]=[-a,b]=[a,-b]=[-a,-b]
a|bであれば(a,b)=|a|,[a,b]=|b|
任意の整数xに対して、(a,b)=(a,b+ax)
任意の整数d|aに対して、[a,b]=[a,b,d]
a|c,b|c ⟺\Longleftrightarrow ⟺[a,b]|cd |a,d|b ⟺\Longleftrightarrow ⟺d|(a,b)
(a,b,c)=((a,b),c) [a,b,c]=[[a,b],c]
mが正の整数であれば、
m(a,b)=(ma,mb) m[a,b]=[ma,mb]
(m,a)=1 ⟹\Longrightarrow ⟹(m,ab)=(m,b)
(m,a)=1,m|ab ⟹\Longrightarrow ⟹m|b
(a,b)=d ⟹ ( a d , b d ) = 1\Longrightarrow (\frac{a}{d},\frac{b}{d})=1 ⟹(da,db)=1
[a,b]= ∣ a b ∣ ( a , b )\frac{|ab|}{(a,b)} (a,b)∣ab∣
a,bは不完全が0の整数⟹(a,b)=m i n{s:s=a x+b y,x,y∈Z,s>0}Longrightarrow(a,b)=min{s:s=ax+by,x,yin Z,s>0}⟹(a,b)=min{s:s=ax+by,x,y∈Z,s>0}
(a,b)=1の場合、任意の整数nはn=ax+by、x,yはいずれも整数と表すことができる.
( a , b ) = 1 , ⟹ { s : s = a x + b y , x , y ∈ Z } = Z (a,b)=1,\Longrightarrow\{s:s=ax+by,x,y\in Z\}=Z (a,b)=1,⟹{s:s=ax+by,x,y∈Z}=Z
2算数の基本定理
算数の基本定理は唯一の分解定理とも呼ばれ、理論の中心内容の一つであり、初等数論において重要である.
正の整数は3種類に分けられます:1、素数、合数.
pは素数,a 1,a 2,.,a n a_1,a_2,...,a_n a1,a2,...,anは整数であり,n≧2,b∈Z nge 2,bin Z n≧2,b∈Zの場合,p{k=1}^na_k p∣k=1∏n akであれば、∃i,1≦i≦nとなり、p∣a iexists i,1le ile nとなり、p|a_i∃i,1≦i≦nでp∣aiとする.
算数の基本定理:整数n>1,それは必ずn=∏i=1 m p i,p i(1≦i≦m)n=prodlimits_がある{i=1}^mp_i,p_i(1le ile m)n=i=1∏m pi、pi(1≦i≦m)は素数である.因子順序を問わず,この分解式は唯一である.
a = p 1 α 1 . . . p s α s , b = p 1 β 1 . . . p s β s a=p_1^{\alpha_1}...p_s^{\alpha_s},\qquad b=p_1^{_\beta1}...p_s^{\beta_s} a=p1α1...psαs,b=p1β1...psβs,
a|b ⟺ α i ≤ β i ( 1 ≤ i ≤ s )\Longleftrightarrow\alpha_i\le\beta_i(1\le i\le s) ⟺αi≤βi(1≤i≤s)
( a , b ) = p 1 e 1 . . . p s e s , e i = m i n { α i , β i } (a,b)=p_1^{e_1}...p_s^{e_s},e_i=min\{\alpha_i,\beta_i\} (a,b)=p1e1...pses,ei=min{αi,βi}
[ a , b ] = p 1 d 1 . . . p s d s , d i = m a x { α i , β i } [a,b]=p_1^{d_1}...p_s^{d_s},d_i=max\{\alpha_i,\beta_i\} [a,b]=p1d1...psds,di=max{αi,βi}
(a,b)[a,b]=ab
3素数
素数は無限である.
π(x)pi(x)π(x)はxを超えない素数の個数を表し、xは任意の正実数である.
lim x → + ∞ π ( x ) x = 0\lim\limits_{x\to+\infty}\frac{\pi(x)}{x}=0 x→+∞limxπ(x)=0
lim x → + ∞ π ( x ) x ln x = 1\lim\limits_{x\to+\infty}\frac{\pi(x)}{\frac{x}{\ln_x}}=1 x→+∞limlnxxπ(x)=1
整数n≧2,nge 2,n≧2である、nが合数であれば、必ず素数p∣n,p≦n p|n,plesqrt{n}p∣n,p≦nがある.
Fermat数Fn＝2 2 n＋1 F＿n=2^{2^n}+1 Fn=22 n+1であり,Fermat素数が無限であるかどうかは不明である.
形は、M p=2 p−1 M_p=2^p−1 Mp=2 p−1の素数をMersenne素数と呼ぶ.
n%4=3,nをブルーム素数,2つのブルーム素数の積をブルーム整数と呼ぶ.
4 Euclidアルゴリズム
ユークリッドアルゴリズムは転がり相殺法とも呼ばれる.
1整数の除算
a b ∈ Z , b ≠ 0 , ab\in Z,be 0, ab∈Z,b̸=0であり、整数cが存在し、a=bcとする場合、bはaを除去し、b|aと記す.
b ≠ 0 , a ∣ b ⟹ ∣ a ∣ ≤ ∣ b ∣ be 0,a|b\Longrightarrow |a|\le|b| b̸=0,a∣b⟹∣a∣≤∣b∣
a ∣ b , b ∣ a ⟹ b = ± a a|b,b|a\Longrightarrow b=\pm a a∣b,b∣a⟹b=±a
a ∣ b , b ∣ c ⟹ a ∣ c a|b,b|c\Longrightarrow a|c a∣b,b∣c⟹a∣c
a∣b,a∣c⟺対任意t,s∈Z,a∣t b+s c a|b,a|cLongleftrightarrow対任意t,sin Z,a|tb+sc a∣b,a∣c⟺対任意t,s∈Z,a∣tb+sc a∣b+sc
$me0,a|b\Longleftrightarrow ma|mb $
[x]はxを超えない最大整数である
実数xの小数部
a,bは2つの整数であり,b≠0 be 0 b̸=0であると、a=q b+r,0≦rdはa,bの最大公約数であり,(a,b),またはgcd(a,b)と記す.
(a,b)=1である、a,b相互素は、公約数±1pm 1±1のみである.
mはa,bの最小公倍数である,[a,b],またはlcm(a,b)と記す.
(a,b)=(b,a)=(-a,b)=(a,-b)=(-a,-b)
[a,b]=[b,a]=[-a,b]=[a,-b]=[-a,-b]
a|bであれば(a,b)=|a|,[a,b]=|b|
任意の整数xに対して、(a,b)=(a,b+ax)
任意の整数d|aに対して、[a,b]=[a,b,d]
a|c,b|c ⟺\Longleftrightarrow ⟺[a,b]|cd |a,d|b ⟺\Longleftrightarrow ⟺d|(a,b)
(a,b,c)=((a,b),c) [a,b,c]=[[a,b],c]
mが正の整数であれば、
m(a,b)=(ma,mb) m[a,b]=[ma,mb]
(m,a)=1 ⟹\Longrightarrow ⟹(m,ab)=(m,b)
(m,a)=1,m|ab ⟹\Longrightarrow ⟹m|b
(a,b)=d ⟹ ( a d , b d ) = 1\Longrightarrow (\frac{a}{d},\frac{b}{d})=1 ⟹(da,db)=1
[a,b]= ∣ a b ∣ ( a , b )\frac{|ab|}{(a,b)} (a,b)∣ab∣
a,bは不完全が0の整数⟹(a,b)=m i n{s:s=a x+b y,x,y∈Z,s>0}Longrightarrow(a,b)=min{s:s=ax+by,x,yin Z,s>0}⟹(a,b)=min{s:s=ax+by,x,y∈Z,s>0}
(a,b)=1の場合、任意の整数nはn=ax+by、x,yはいずれも整数と表すことができる.
( a , b ) = 1 , ⟹ { s : s = a x + b y , x , y ∈ Z } = Z (a,b)=1,\Longrightarrow\{s:s=ax+by,x,y\in Z\}=Z (a,b)=1,⟹{s:s=ax+by,x,y∈Z}=Z
2算数の基本定理
算数の基本定理は唯一の分解定理とも呼ばれ、理論の中心内容の一つであり、初等数論において重要である.
正の整数は3種類に分けられます:1、素数、合数.
pは素数,a 1,a 2,.,a n a_1,a_2,...,a_n a1,a2,...,anは整数であり,n≧2,b∈Z nge 2,bin Z n≧2,b∈Zの場合,p{k=1}^na_k p∣k=1∏n akであれば、∃i,1≦i≦nとなり、p∣a iexists i,1le ile nとなり、p|a_i∃i,1≦i≦nでp∣aiとする.
算数の基本定理:整数n>1,それは必ずn=∏i=1 m p i,p i(1≦i≦m)n=prodlimits_がある{i=1}^mp_i,p_i(1le ile m)n=i=1∏m pi、pi(1≦i≦m)は素数である.因子順序を問わず,この分解式は唯一である.
a = p 1 α 1 . . . p s α s , b = p 1 β 1 . . . p s β s a=p_1^{\alpha_1}...p_s^{\alpha_s},\qquad b=p_1^{_\beta1}...p_s^{\beta_s} a=p1α1...psαs,b=p1β1...psβs,
a|b ⟺ α i ≤ β i ( 1 ≤ i ≤ s )\Longleftrightarrow\alpha_i\le\beta_i(1\le i\le s) ⟺αi≤βi(1≤i≤s)
( a , b ) = p 1 e 1 . . . p s e s , e i = m i n { α i , β i } (a,b)=p_1^{e_1}...p_s^{e_s},e_i=min\{\alpha_i,\beta_i\} (a,b)=p1e1...pses,ei=min{αi,βi}
[ a , b ] = p 1 d 1 . . . p s d s , d i = m a x { α i , β i } [a,b]=p_1^{d_1}...p_s^{d_s},d_i=max\{\alpha_i,\beta_i\} [a,b]=p1d1...psds,di=max{αi,βi}
(a,b)[a,b]=ab
3素数
素数は無限である.
π(x)pi(x)π(x)はxを超えない素数の個数を表し、xは任意の正実数である.
lim x → + ∞ π ( x ) x = 0\lim\limits_{x\to+\infty}\frac{\pi(x)}{x}=0 x→+∞limxπ(x)=0
lim x → + ∞ π ( x ) x ln x = 1\lim\limits_{x\to+\infty}\frac{\pi(x)}{\frac{x}{\ln_x}}=1 x→+∞limlnxxπ(x)=1
整数n≧2,nge 2,n≧2である、nが合数であれば、必ず素数p∣n,p≦n p|n,plesqrt{n}p∣n,p≦nがある.
Fermat数Fn＝2 2 n＋1 F＿n=2^{2^n}+1 Fn=22 n+1であり,Fermat素数が無限であるかどうかは不明である.
形は、M p=2 p−1 M_p=2^p−1 Mp=2 p−1の素数をMersenne素数と呼ぶ.
n%4=3,nをブルーム素数,2つのブルーム素数の積をブルーム整数と呼ぶ.
4 Euclidアルゴリズム
ユークリッドアルゴリズムは転がり相殺法とも呼ばれる.
int t;
while(b)
{
t = a%b;
a = b;
b = t;
}
return a;