1-數(shù)論初步(已修改)
2025-08-05 03:07 本頁(yè)面
【正文】 2022年浙江省隊(duì)培訓(xùn) 第 1講 數(shù)論初步 劉汝佳 目錄 一、基本概念 二、進(jìn)位制 三、模算術(shù)與方程 四、雜題 一、基本概念 基本概念 ? 整除與約數(shù)、倍數(shù) . 注意負(fù)數(shù) ? 可整除性的基本性質(zhì) –若 a|b, a|c, 則 a|(b+c) –若 a|b, 那么對(duì)所有整數(shù) c, a|bc –若 a|b, b|c, 則 a|c ? 整除關(guān)系具有傳遞性 . 它是偏序關(guān)系 (partial order), |,Z是一個(gè)格 素?cái)?shù)和合數(shù) ? 如果大于 1的正整數(shù) p僅有的正因子是 1和 p, 則稱 p為素?cái)?shù) (prime) ? 大于 1又不是素?cái)?shù)的正整數(shù)稱為合數(shù)(pound) ? 如果 n是合數(shù) , 則 n必有一個(gè)小于或等于 n1/2的素因子 算術(shù)基本定理 ? 每個(gè)正整數(shù)都可以惟一地表示成素?cái)?shù)的乘積，其中素?cái)?shù)因子從小到大依次出現(xiàn)（這里的“乘積”可以有 0個(gè)、 1個(gè)或多個(gè)素因子）。 ? 換句話說(shuō) , 任意正整數(shù) n可以寫(xiě)成 n=2a1*3a2*5a3*…,其中 a1,a2,a3等為非負(fù)整數(shù) ? 這個(gè)定理也叫做 惟一分解定理 。它是一個(gè)定理而不是公理！雖然在大多人看來(lái)，它是“顯然成立”的，但它的確是需要證明的定理 除法和同余 ? 令 a為整數(shù)， d為正整數(shù)，那么有惟一的整數(shù) q和 r，其中 0≤rd，使得 a=dq+r ? 可以用這個(gè)定理來(lái)定義除法： d叫除數(shù)，a叫被除數(shù)， q叫商， r叫余數(shù)。如果兩個(gè)數(shù) a,b除以一個(gè)數(shù) c的余數(shù)相等，說(shuō) a和 b關(guān)于模 c同余，記作 a≡b(mod c) 同余 ? 為什么有同余 ? ? 13241234…1+432435..2=24….7 ? 余數(shù)可以作為原數(shù)的一個(gè) signature(標(biāo)記 ). ? 如果標(biāo)記下的運(yùn)算錯(cuò)誤 , 一定錯(cuò)誤 ? 如果標(biāo)記下的運(yùn)算正確 ? 最大公約數(shù)和最小公倍數(shù) ? 令 a和 b是不全為 0的兩個(gè)整數(shù)，能使 d|a和d|b的最大整數(shù)稱為 a和 b的最大公約數(shù)，用gcd(a,b)表示，或者記為 (a,b)。 ? 令 a和 b是不全為 0的兩個(gè)整數(shù)，能使 a|d和b|d的最小整數(shù)稱為 a和 b的最小公倍數(shù)，用lcm(a,b)表示，或者記為 [a,b] ? 定理 : ab = gcd(a,b) * lcm(a,b) 定理的證明 ? 使用惟一分解定理 . 設(shè) ? 則有 : ? 容易驗(yàn)證定理成立 nn bnbbanaa pppbpppa ?? 2121 2121 , ??),m i n (),m i n (2),m i n (1 2211),g c d( nn banbaba pppba ??),m a x (),m a x (2),m a x (1 2211),(lcm nn banbaba pppba ??例題：佳佳的困惑 ? 給出一個(gè)數(shù) N，含數(shù)字 4，把 N的所有數(shù)字重新排列一下組成一個(gè)新數(shù)，使它是 7的倍數(shù)。 分析 ? 把數(shù)字 4從中抽出，然后把其他數(shù)字按照原順序排列（事實(shí)上，怎么排列都無(wú)所謂）組成自然數(shù) w ? w*10,000整除 7取余有 7種可能，即是為 0、 6。這時(shí)如果能用數(shù)字 4排列出 7個(gè)數(shù)，使它們整除 7取余的值分別為 0、 6，把這個(gè) 4位數(shù)接在 w后面即為問(wèn)題的解。 例題：街道數(shù) ?找所有的 (n, k), 滿足 : ? 1+2+..+(n1)=(n+1)+(n+2)…+k ?輸出按 k排序的前 10個(gè) 分析 ? 整理得 : n(n1)=(kn)(n+k+1) ? 化簡(jiǎn)得 : k2+k2n2=0, 即 n2=k(k+1)/2 ? 由于 k和 k+1互素 , 因此 –要么 k是完全平方數(shù) –要么 k/2是完全平方數(shù) ? 分別設(shè) k=m2和 2m2, 枚舉 m 例題：齒輪 ? 假設(shè)有三種齒輪： 6齒， 12齒， 30齒。想要實(shí)現(xiàn) 4 : 5的比例，一種可行方案如下： ? 給定可用的齒輪（每種均有無(wú)窮多），設(shè)計(jì)一系列傳輸 c1 : d1, c2 : d2, …, cm : dm，使得其綜合比例(c1c2c3…c m)/(d1d2d3…d m)為給定值 a:b。 ? 給定齒輪的齒數(shù)為 5到 100， a和 b不超過(guò) 10000。 分析 ? 使用惟一分解定理 , 單獨(dú)考慮各個(gè)素因子 ? c1 = p1a1*p2*a2*… ? c2 = p1b1*p2*b2*… ? … ? 則 c1x*c2y=p1(x*a1+y*b1) *p2(x*a2+y*b2) ? 目標(biāo) a:b = p1z1 * p2z2 … ? x*a1+y*b1=z1。 x*a2+y*b2=z2 分析 ? 第 i個(gè)齒輪的使用情況用 xi表示， xi0表示用在分子 xi次， xi0表示用在分母 xi次。 ? 由于 ai=100，只需要考慮 100
化學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1