【7】整除性與余數(shù)

定義7.1 a,b是整數(shù)a\ne 0,若存在整數(shù)k使b=ka,則稱整數(shù)a整除整數(shù)b,或稱b能被a整除,記作:a\mid b。否則,稱整數(shù)a不能整除整數(shù)b,或稱b不能被a整除,記作:a\nmid b。
請根據(jù)以上定義判斷以下每對數(shù)是否整除:

表7.1.1

題7.2 以下說法是否正確:
(1) 一個(gè)數(shù)同時(shí)能被3與7整除,它一定能被21整除。
(2)一個(gè)數(shù)同時(shí)能被6與9整除,它一定能被54整除。

定義7.3 a,b是整數(shù)且a>0,如果存在整數(shù)q,r,滿足0\le r<ab=qa+r,則稱rb除以a余數(shù),記作r=b\%a。其中q為商。
根據(jù)以上定義,求:
(1) 89188\%17
(2) 3^{2022}\%10
(3) (3^{2022}+2^{2022})\%5

題7.4 證明:
(1) 3個(gè)除以5余3的整數(shù)相乘,其積除以5余2。
(2) 一個(gè)整數(shù)的平方,除以4不能余2。
證明 (1) 設(shè)這三個(gè)數(shù)為x,y,z,根據(jù)題意,存在a,b,c\in \mathbb Z,滿足:
x=5a+3\\ y=5b+3\\ z=5c+3
所以,xyz=(5a+3)(5b+3)(5c+3)=(25ab+15a+15b+9)(5c+3)\\ =125abc+75ab+75bc+75ca+45a+45b+45c+27\\ =5(25abc+5ab+5bc+5ca+9a+9b+9c+5)+2
所以,xyz\%5=2
(2) 討論奇偶性:(a) 如果此數(shù)為偶數(shù),它的平方被4除余0;(b)如果此數(shù)是奇數(shù),它的平方被4除余1。綜上,任意的整數(shù)的平方被4除不余2。

定理7.5 a,b,c\in \mathbb Z,c|a,c|b,那么對于任意的整數(shù)m,n,有c|(ma+nb)
證明 因?yàn)? a,b,c\in \mathbb Z,c|a,c|b,所以存在k_1,k_2滿足:
a=k_1c\\b=k_2c
所以ma+nb=mk_1c+nk_2c=(mk_1+nk_2)c
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=mk_1%2Bnk_2%5Cin%20%5Cmathbb%20Z" alt="mk_1+nk_2\in \mathbb Z" mathimg="1">,所以c|(ma+nb)
\blacksquare

題7.6 對于任意的整數(shù)x,若2|x^2,那么2|x。
證明 以下使用反證法:
假設(shè)命題不成立,則x是奇數(shù),即存在整數(shù)k,使x=2k+1,所以:
x^2=(2k+1)^2\\ =4k^2+4k+1\\ =2(2k^2+2k)+1
可見x^2 \%2 =1,與條件矛盾。所以假設(shè)不成立,命題成立。\blacksquare

題7.7 n\in \mathbb Z,證明:
(1) 6|n(n+1)(n+2)
(2) n(n+1)(n+2)(n+3)+1是平方數(shù)。
證明 (1) n,n+1,n+2中,必有一個(gè)偶數(shù),所以2|n(n+1)(n+2);
n,n+1,n+2中,必有一個(gè)是3的倍數(shù),所以3|n(n+1)(n+2)。
綜上,6|n(n+1)(n+2)

(2) n(n+1)(n+2)(n+3)+1=(n^2+3n+1)^2

評注7.8 題7.7(2)的思路如下:
b_n=n(n+1)(n+2)(n+3)+1=a_n^2,可以驗(yàn)證:
b_1=5^2\\ b_2=11^2\\ b_3=19^2\\ b_4=29^2\\...
所以,a_1=5,a_2=11=a_1+6,a_3=19=a_2+8,...,a_n=a_{n-1}+2(n+1),所以:
a_2-a_1=6\\ a_3-a_2=8\\ ...\\

題7.9 (1) 1000之內(nèi),能被3整除的正整數(shù)有多少個(gè)?
(2) 2022之內(nèi)的正整數(shù)中,既是8的倍數(shù),又是18的正倍數(shù)有多少個(gè)?
(3) 2022之內(nèi)的正整數(shù)中,3的倍數(shù)、8的倍數(shù)、18的倍數(shù)共有多少個(gè)?
(1) \frac{1000}3 = 333....1,所以1000之內(nèi),能被3整除的正整數(shù)有333個(gè)。
(2) [8,18]=72,且2022/72=28...6,所以它們共同的倍數(shù)有28個(gè)。
(3) 根據(jù)容斥原理計(jì)算:
\lfloor2022/3\rfloor+\lfloor2022/8\rfloor+\lfloor2022/18\rfloor-\lfloor2022/[3,8]\rfloor-\lfloor2022/[8,18]\rfloor-\lfloor2022/[18,3]\rfloor+\lfloor2022/[3,8,18]\rfloor\\ =674+252+112-84-28-112+28=842
所以,滿足條件的整數(shù)有842個(gè)。
\blacksquare

題7.10 9000的所有因數(shù)有_________個(gè),它們的和是___________
9000=2^3\times 3^2\times 5^3,所以,它的因數(shù)有4\times 3\times 4=48個(gè),其和為(1+2+4+8)(1+3+9)(1+5+25+125)=15\times 13\times 156=30420
\blacksquare

定理7.11 整除有如下性質(zhì):
(1) a|b,b|c\rightarrow a|c
(2) a|b,a|c\rightarrow\forall m,n\in \mathbb Z,a|(mb+nc)
(1) 由條件得,存在整數(shù)k_1,k_2,滿足b=k_1a,c=k_2b,所以c=k_1k_2a,所以a|c。
(2) 由條件得,存在整數(shù)k_1,k_2,滿足b=k_1a,c=k_2a,所以mb+nc=mk_1a+nk_2a=(mk_1+nk_2)a\\
所以,a|(mb+nc)
\blacksquare
定義7.12(a,b)a,b的最大公約數(shù),[a,b]a,b的最小公倍數(shù)。
(30,45)=_____,[30,45]=_____,(30,45)\times[30,45]=_____,30\times45=_____

定義7.13 如果a,b的最大公約數(shù)是1,那么稱a,b互質(zhì)數(shù)

定理7.14
(1) (a,b)=d,則自然數(shù)na,b的公約數(shù),當(dāng)且僅當(dāng)n|d
(2) [a,b]=m,則自然數(shù)na,b的公倍數(shù),當(dāng)且僅當(dāng)m|n

定理7.15 a,b是整數(shù),(a,b)=d當(dāng)且僅當(dāng)\left(\frac{a}d,\fracd\right)=1
證明 (1)先證必要性:假設(shè)命題不成立,則設(shè)\left(\frac{a}d,\fracd\right)=d'>1。則存在q_1,q_2\in \mathbb Z,滿足\frac{a}d=q_1d'\\\fracd=q_2d'
即得a=q_1dd',b=q_2dd',所以(a,b)\ge dd'>d矛盾。所以假設(shè)不成立,命題成立。
(2) 再證充分性:假設(shè)命題不成立,則存在比d大的公約數(shù)d'=kd,其中k\in \mathbb Z,k>1。此時(shí)又有k_1,k_2\in \mathbb Z滿足:a=k_1d'=k_1kd\\b=k_2d'=k_2kd
于是:\left(\frac{a}d,\fracd\right)=(k_1k,k_2k)\ge k>1矛盾。所以假設(shè)不成立,命題成立。
\blacksquare

定理7.16 a,b是整數(shù),[a,b]=m當(dāng)且僅當(dāng)\left(\frac{m}a,\frac{m}b\right)=1
證明 (1)先證必要性:假設(shè)命題不成立,設(shè)\left(\frac{m}a,\frac{m}b\right)=d>1\\
于是存在k_1,k_2\in \mathbb Z,滿足:m=k_1da=k_2db
m'=m/d\in \mathbb Z_+,則m'=k_1a=k_2b,即m'a,b的公倍數(shù)且小于m,矛盾。所以假設(shè)不成立,命題成立。
(2)再證充分性:假設(shè)命題不成立,則令[a,b]=m',則存在k\in\mathbb Z,k>1,m=km'
\exists k_1,k_2\in \mathbb Z,m'=k_1a=k_2b,所以m=kk_1a=kk_2b,于是:\left(\frac{m}a,\frac{m}b\right)=(kk_1,kk_2)\ge k>1\\矛盾。所以假設(shè)不成立,命題成立。
\blacksquare

定理7.17 (a,b)[a,b]=ab
證明 設(shè)(a,b)=d,則存在整數(shù)k_1,k_2,滿足a=k_1d\\b=k_2d\\(k_1,k_2)=1
所以\tag{7.17.1}ab=k_1k_2d^2
另外,令m=k_1k_2d,則 k_1=\frac{m}b,k_2=\frac{m}a,所以\left(\frac{m}a,\frac{m}b\right)=(k_1,k_2)=1\\
根據(jù)定理7.16得m=[a,b],再由(7.17.1)得(a,b)[a,b]=ab。
\blacksquare

推論 a,b互素,[a,b]=ab

題7.18 求以下各數(shù)的所有因數(shù):
(1) 468的所有因數(shù):________________________
(2) 37^{3}的所有因數(shù):________________________
(3) 3^2 19^4的所有因數(shù):________________________
(4) 15^2 20^3的所有因數(shù):________________________
(3) 因?yàn)?,19都是因數(shù),所以3^2 19^4的所有因數(shù)是下式展開后不合并的各項(xiàng):(1+3+3^2 )(1+19+19^2+19^3+19^4)=1+19+19^2+19^3+19^4\\+3+3\times19+3\times19^2+3\times19^3+3\times19^4\\+3^2+3^2\times19+3^2\times19^2+3^2\times19^3+3^2\times19^4
所以,其因數(shù)有:1,19,19^2,19^3,19^4,\\3,3\times19,3\times19^2,3\times19^3,3\times19^4,\\3^2,3^2\times19,3^2\times19^2,3^2\times19^3,3^2\times19^4

題7.19 求以下各組數(shù)的所有公因數(shù):
(1) 170,68的所有公因數(shù):________________________
(2) 2^3 5^{10},2^{20}5^2的所有公因數(shù):________________________
(3) 2^3 3^4 5^8 20^3,630的所有公因數(shù):________________________

定理7.20 a,b,c是自然數(shù),(a,b)=1,a,b\ne 0,且a|c,b|c,那么ab|c.
定理7.21 a,b,c是自然數(shù),a,b\ne 0,且a|c,b|c,那么[a,b]|c.

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡書系信息發(fā)布平臺,僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容