最小公倍數
定義：a1,...an(n≥2)，m 為a1,...an的公倍數，[a1,a2,...an]代表為a1,...an的最小公倍數
用數學公式表示為以下：
①ai|[a1,a2,...an],i≤1≤n
②?m,a1|m,a2|m,...an|m(m>=1),且m>=[a1,a2,...,an]
定理一：若a|m,b|m,則[a,b]|m
定理二：[a,b]=a*b/(a,b)
證明：設m=[a,b]*q+r,0≤r<[a,b]
∵a|m,∴a|[a,b]
∴a|r
同理可得，b|r,故[a,b]|r
若r>=1,則[a,b](最小公倍數)<=r(公倍數)
∵r<[a,b]，結論與實際相矛盾，故假設不成立，故r=0
又∵a=((a*b)/[a,b])*([a,b]/b)，故(a*b/[a,b])|a
同理可證(a*b/[a,b])|b
即(a*b/[a,b]) | (a,b)
得： a*b/[a,b]<=(a,b) ，，，①
又∵a*b/[a,b]=a*(b/[a,b])，故a|(a*b/[a,b])
同理可知，b|(a*b/[a,b]),即(a,b)|(a*b/[a,b])
故(a,b)<=(a*b/[a,b])，，，②
結合①和②可知，[a,b]=a*b/(a,b)
得證
定理二：設a1,a2,...,an(∈Z),n>=2，則[a1,a2,...an]=mn
證明：
[a1,a2]=m2,[m2,a3]=m3
故a1|m2,a2|m2 , m2|m3,a3|m3
∴a1|m3,a2|m3,a3|m3
故[a1,a2,a3]|m3
設a1|m,a2|m,a3|m，即m為a1,a2,a3的倍數
∵[a1,a2]=m2，故m2|m
∵[m2,a3]=m3，故m3|m
即m3<=m
故m3為公倍數中的最小值，以次類推至n種情況，得證
整數的唯一分解定理
素數定義：?d∈Z+,d|P
合數定義：?d,d1,1<d<C,1<d1<C,C=d*d1
引理1：若a∈Z,a≥2,q是a中≥2的最小因子，則q是素數，當a時合數時，q≤根號a
證明：
①假設q為合數，則q=d*d1,∴2≤d,d1<q
∴d|q又∵q|a,故d|a->d為a的因子且d<q,故此時q就不是a的最小因子，與q最小相矛盾，假設不成立
所以d為素數
②若a為合數，則a=q*q1
∵q<=q1
故q*q<=q*q1
即q*q<=a
所以q<根號a
引理2：若p為素數，?a∈Z,則p|a或(p,a)=1(整數與素數之間的關系)
引理3：若p為素數，p|a*b,則p|a或p|b
定理：?a=2，?p1≤p2≤...≤pn(pi均為素數)，使得a=p1*p2*...*pn,且若q1≤q2≤...≤qn是素數，且a=q1*q2*...*qm，則m=n,qi=pi(滿足這樣的素數唯一)
一次不定方程
二元不定方程：
a1*x+a2*y=n (a1,a2≠0) ①
定理1：①有解，當且僅當(a1,a2) | n
定理2：若(a1,a2)=1,則①的全部解為
x=x0+a2*t
y=y0-a1*t,其中x0,y0是①的一組解(t∈Z)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121943.html
標籤：其他
上一篇：0389. Find the Difference (E)
下一篇：給博客加上博客精靈——嗚米