第九章 數論基礎.

Slides:



Advertisements
Similar presentations
渡黑水溝 郁永河. 2 戎克船:是明末清初時期往返兩岸的主要交通工具 ∗ 1. 關於台灣的開發歷史,我們到底了解多少呢?不妨試著說出 就我們所知有關台灣開發史的故事、小說、電影、音樂與大 家分享。 ∗ 2. 什麼是黑水溝?黑水溝為什麼會成為大陸移民渡海來臺時最 大的威脅? ∗ 3. 有聽過「六死三留一回頭」、「有唐山公,無唐山嬤」這兩.
Advertisements

生產排程報告 - 瓦城 泰國料理 導師 : 曾文宏 組員 : 4a 王昱堂 4a 鐘浩佑 4A 魏旭昇 4A 林昱翔 4A 汪宗翰.
金融一班 王亚飞 王亚飞 王浩浩 王浩浩 吴海玥 吴海玥 我 连云港 的 家 乡 连云港 连云港,位于东经118°24′~119°48′和北纬 34°~35°07′之间,古称郁洲、海州,民国时称 连云市,建国后称新海连市,别称“港城”。东 西长129公里,南北宽约132公里,水域面积 平方公里。连云港市也是我国于1984年.
配备计算机教室、多媒体教室、图书室、卫生室、 实验室、仪器室、音体美劳器材室、心理咨询室、少先 队活动室、教师集体备课室等专用教室。实验室、仪器 室全部按照省标准配备器材,演示实验开设率达 100% 。 学校现有图书 6050 册,生均 40 册。有一个 200 米环形跑 道的运动场地。 学校基本情况.
從「穹頂之下」電影看環境議題 第六小組 4a 黃士齊 4a 吳承翰 4a 洪濬森 4a 郭哲宇 0a40f226 湯思祺 林喬舜.
少年儿童营养配餐与饮食安全 科学饮食为孩子的未来积攒本钱.
幾米 作業 1 飛上天空 我想飛上天空 遨遊在無際的天空 美麗的天空 漂亮的天空 這終究只是夢…… (李高仰)
長得像的圖形 設計者:嘉義縣興中國小 侯雪卿老師 分享者:高雄市中山國小 江民瑜老師 高雄市勝利國小 許嘉凌老師.
课例评析—— 《回乡偶书》和《渔歌子》 评课人:冯琴.
就作文本身而言,题目堪称“眉目”,是作文的“眼睛”,从某种程度上说,它是作文材料和主题的浓缩或概括。
学习全国“两会”精神 常州工学院  理学院党总支 2014年3月.
乘势而上再谱发展新篇章 -2012全国两会精神解读
开启新征程 点燃中国梦 开启新征程 点燃中国梦 ——学习、领会2013年全国“两会”精神.
班級:四環工一A 姓名:王柏翰、劉豐宇 學號:4980N058、4980N069
文化创新的途径.
2009—2010学年第一学期 小学品德与社会课程教学监控情况分析 潘诗求 2010年3月
15世纪欧洲人绘制的世界地图.
手太阳小肠经.
课件制作 WangWenHao 第四章 随机变量的数字特征 §1 数学期望 特点: 分布函数 全面、详细、完整 §2 方差
离散随机变量及分布律 定义 个或可列个, 则称 X 为离散型随机变量 描述X 的概率特性常用概率分布或分布律 即 X 或 P §2.2
各位弟兄姐妹,主內平安! 請將手機關靜音,帶著敬虔的心來到上帝的面前!
第7课 新航路的开辟 第7课 新航路的开辟.
股票、债券、和保险 投资理财的话题.
游泳四式技術分析暨初級教法.
第一节 呼吸道对空气的处理.
十面“霾”伏 湖南长沙民政职业技术学院“思政”第九组 组员:李亮亮 许静 赵凯丽 何敏 张艳欣 付幻菱 陈京萍 王诗雨.
數學家:畢達哥拉斯 公元前580年至公元前500年.
高考考试说明解读 --政治生活.
如何对付脏空气.
杜甫(公元712—公元 770),汉族,河南巩 县(今巩义市)人。字子 美,自号少陵野老,盛 唐、中唐诗人,伟大的 现实主义诗人。世称杜 拾遗、杜工部。代表作 有“三吏”“三别”。他 忧国忧民,人格高尚, 诗艺精湛,被后世尊为 “诗圣”,其诗被称为“ 诗史”。
教師執行計畫案聘任助理說明會 (勞務型、學習型申請方式說明)
构建九年级物理 复习的课堂效率 邵武市明鸿中学 吴丽萍.
电阻 新疆兵团四师76团中学.
第十一章 真理与价值 主讲人:阎华荣.
外貌和能力哪个更重要.
水腫的原因 徐淑娟護理師 PM.
中国未成年人法制安全课程 雾霾哪里来? 初中段 第七讲.
第二讲 环境污染及其防治、环境管理.
从此,我不在沉默寡言 那一刻 就在这一刻 世上还有爸爸好 我 长 大 了 张绅 4 文苑芬芳
第七章 固 定 资 产.
从容行走,优雅为师 江苏省梁丰高级中学 任小文
[聚會時,請將傳呼機和手提電話關掉,多謝合作]
概率论与数理统计 2.1 随机变量与分布函数.
觀察內容: 時間 作息 觀察內容 9:30~9:40 角落分享
空間向量 朱泰吉 蔡宇翔 張力夫 莊孟霏.
天气和气候.
[聚會時,請將傳呼機和手提電話關掉,多謝合作]
导入 21世纪教育网经纬社会思品工作室制作 我们可以通过哪些媒介(途径)获知这些消息?.
何俊賢教學資料.
行政院國軍退除役官兵輔導委員會 嘉義榮民醫院.
Chapter 13 數論基礎.
奥林巴斯显微镜的维护保养.
第八章 欧氏空间 8.1 向量的内积 8.2 正交基 8.3 正交变换 8.4 对称变换和对称矩阵.
Chapter 2 密碼基礎數學I:模數算數、同餘 與矩陣.
公立學校教職員退休資遣撫卹條例重點說明 苗栗縣政府人事處編製 主講人:陳處長坤榮 107年5月2日.
学习中苦多?乐多? ——高二(1)班主题班会.
第二章 基本遗传算法(GA) 2.1 基本遗传算法描述 基本遗传算法的构成要素 (1) 染色体编码方法
算法与程序设计.
§2.2 离散型随机变量及其概率分布 离散随机变量及分布律 定义 若随机变量 X 的可能取值是有限多个
例題:某人由地面同時向空中拋出 A、B 兩球,A 球之初速為 vA,仰角為 θA,B 球則為 vB 及 θB,且 θA > θB。設兩球在同一水平面內運動,而且所達到的最大高度也相同,則下列敘述何者為正確? (A) vA > vB (B) A 球之水平射程較 B 遠 (C) 兩球同時到達最高點.
§ 5-1 電流的磁效應 磁學發展的歷史: 1820年 7月,厄司特發現,一載有電流的直導線,可使周圍的磁針產生偏轉。
問題解決與流程圖 高慧君 台北市立南港高中 2006年12月22日.
第二章 基本遗传算法(GA) 2.1 基本遗传算法描述 基本遗传算法的构成要素 (1) 染色体编码方法
第13课 东汉的兴亡.
第六章 样本及抽样分布 §2 抽样分布 4) 正态总体的样本均值与样本方差的分布: 定理1.
繁星推薦系統 楊曉婷 副理 教育的服務 是我們的責任.
第6课 我是共和国的公民.
單元主題名: 大家都是好朋友 設計者:柯淑惠、林雨欣.
104學年度第二學期 燈音開課 03/14燈光開課.
Presentation transcript:

第九章 數論基礎

9.2 質數的定義和性質 9.3 歐幾里得演算法 (Euclidean Algorithm) 9.4 中國餘式定理 (Chinese Remainder Theorem)

9.2 質數的定義和性質 本小節須學好下列重點:  質數的判別與性質  質數與合成數的關係

範例一 何謂質數? 有一個正整數 n, n>1 若 n 想寫成二個正整數的乘積只能唯一表示成 n=1n , 範例一 何謂質數? 有一個正整數 n, n>1 若 n 想寫成二個正整數的乘積只能唯一表示成 n=1n , 也就是說除了 n=1n 的表示方式外, 再沒有別的表示方式時, 我們稱 n 為質數. 例如:2 的乘積只能寫成 1 和本身的乘積, 所以 2 是質數 且是最小的質數. 注意!1 並不是質數

範例二 給一個很大的正整數n,如何判定是否為質數? 最蠻力的方法是將 n 除以2,若除得盡,則 n 不為質數。 假若 n 除以2後有非零餘數,則試試將 n 除以3, 若仍除不盡,則再往下試試,將 n 除以5、除以7、…、除以 n1 。 如果 n 除以這些數皆有非零餘數,則 n 必為質數。

範例三 是否有比 O(n) 更快的質數判定法? 有的! 令 n=61,則61除以2、3、5和7皆得非零的餘數, 那麼61並不需要除以11以判定其是否為質數, 原因是61=5×11+6,那意謂著61=11×5+6。 這隱含著61除以5有非零餘數時,也等同於61除以11有非零餘數。 不難感覺出判定 n 是否為質數,只需檢查2、3、5…和 是否可被 n 除盡即可。 最壞情況需花 的時間即可判定 n 是否為質數。  此種質數判定法也稱 埃拉托森(Eratosthenes)篩洗法

範例四 質數的個數是否為有限個? 利用反證法(By Contradiction) 範例四 質數的個數是否為有限個? 利用反證法(By Contradiction) 假設質數的個數為有限個,令這k個質數為P1 、P2 、P3 …和 Pk。 因為數列 P 中已包含了所有的質數,所以任何一個不在數列 P 內 的數必為合成數。我們現在找出一個合成數,其型式為 很容易可檢查出該合成數 C 必大於假設中的最大質數 且該合成數 C 除以任一個 Pi ,1ik 後的餘數必為1,這是矛盾的。

範例五 一個質數和下一個質數之間距離有多遠呢? 範例五 一個質數和下一個質數之間距離有多遠呢? 兩個相鄰的質數,其間隔可大到任意大。 只要保證數列中的任一元素皆為合成數, 即可將該相鄰兩質數推開得任意遠。 令該數列=<n!+2, n!+3, …,n!+n> , 這裡 n 為一任意大的正整數。 很容易可驗證 n!+2 可除盡2;n!+3 可除盡3;…;n!+n 可除盡 n。 以上的可除盡性我們用符號 k|(n!+k),2kn,表示之。

範例六 任何一個大於1的合成數可表示唯一連串的質數之積(Product)嗎? 可以的! 令C為該合成數,則C可表示為C=pq,1<pq。 針對第一種組合,因為p已是質數,只需將合成數q表示成 q=xy, 然後依照 x 和 y 的質數與合成數之四種組合仿照相同的討論即可。 上表中的第二種組合和第三種組合的討論也類似於第一種組合 之討論。 p q 質數 合成數 

 最大公因數(Greatest Common divisor),a 和 b 的最大公因數表示成 gcd(a,b) 範例七 對大一點的合成數,可有較好的算數運算式以求得其質數的連 乘積形式? 以長除法求120的質數連乘型式可如下表: 我們得120=2335 120 60 30 15 5 2 3  最大公因數(Greatest Common divisor),a 和 b 的最大公因數表示成 gcd(a,b)

範例八 證明 f (n)=32n+25n+1為4的倍數,其中n為非負整數 其中 t, p Ζ,故得證

範例九 令 S={2, 16, 128, 1024, 8192, 65536},若從S中取四個數來, 證明其中必有兩數的乘積為131072。 令S1={2, 65536}、S2={16, 8192}、S3={128, 1024}, 則在S中取四數, 根據鴿籠原理可知必有一集合Si中的兩數皆被取得, 其中i{1, 2, 3},而此兩數乘積為131072。 故得證!

9.3 歐幾里得演算法 本小節須學好下列重點:  最大公因數的求法  輾轉相除法的應用

最大公因數 假設給兩數 a=120、b=140 a=120=2335 b=140=2257 → gcd(120,140)=20

兩整數 gcd 的歐幾里得演算法即為中學時代所學的輾轉相除法! 上述的輾轉相除法可寫成下列的橫式算術式: 138=524+18 24=118+6 18=36

範例一 如何證明上述輾轉相除法求 gcd(a,b) 的演算法是對的?

範例二 請寫出輾轉相除法的演算法型式 Procedure GCD(a,b) v←a w←b while w0 r←v mod w v←w 範例二 請寫出輾轉相除法的演算法型式 Procedure GCD(a,b) v←a w←b while w0 r←v mod w v←w w←r End 最終的 gcd(a,b)結果存於最後的變數 v 中。

範例三 利用輾轉相除法求 gcd(a,b) 的過程是否可在有限步驟內被完成?

範例四 輾轉相除法的諸多除式中有特殊性質嗎? 範例四 輾轉相除法的諸多除式中有特殊性質嗎? …

範例五 輾轉相除法的過程中, 餘數和費氏數列有關係嗎?

範例七 試將 gcd(a,b) 表示成 a 和 b 的線性組合 (Linear Combination) 138=524+18 24=118+6 18=36 得到 6=gcd(138,24) =24118 =24  (138  524) =6 24 138 =6 24 1  138 =( 1) 138+6 24

9.4 中國餘式定理 本小節須學好下列重點:  何謂中國餘式定理及其典故  中國餘式定理的使用方法

中國餘式定理的典故為何? 在「孫子算經」中, 今有物不知數 三三數之剩二 五五數之剩三 七七數之剩二 問物幾何? 上面的描述寫成白話文就 現在有一個不知道的數 將該數除以3,則餘2 將該數除以5,則餘3 將該數除以7,則餘2 試問該數為何? 如何解出該數。

在上頁投影片中的描述,可否用較數學的形式表達。 解下列三個線性同構式(Linear Congruence): x2(3) x3(5) x2(7) 上式中的3, 5, 7也叫模數(Modulus), 這裡有一限制,3, 5, 7中任兩數互質

範例一 雖然可將滿足 x=3q1+2 的所有解 {2, 5, 8, 11, 14, 17, 20, 23, …} 中之每一個元素拿出來檢查, 看是否同時也滿足 x=5q2+3 和 x=7q3+2 , 但這太沒效率了. 是否有更快的方法? X  1(3) X  0(5) X  0(7) X  0(3) X  1(5) X  0(7) X  0(3) X  0(5) X  1(7) A B C 圖6.4.1 中國餘式定理的分割示意圖

從節點A中的三個特殊線性同構式:X  1(3)、X  0(5)、X  0(7), 不難解出 X = 35k1=70。 節點B也可解出X = 21k2=21為其中一解。 節點C也可解出X = 15k3=15為其中一解。 將節點A的 X  1(3) 調整回 X  2(3),X=70 需要修改成 X=140。 同樣的道理,對節點B而言,X=63,而對節點C而言,X=30。 這就是「演算法統宗」所說: 三人同行七十稀 五樹梅花廿一枝 七子團圓整半月 除百零五便得知

“三人同行七十稀”指的是滿足 X  1(3) 、 X  0(5) 和 X  0(7) 三個線性同餘式的解為70。 “五樹梅花廿一枝”的廿一枝指的是滿足 X  0(3) 、 X  1(5) 和 X  0(7) 的解21。 “七子團圓整半月”的整半月指的是滿足 X  0(3) 、 X  0(5) 和 X  1(7) 的解15。 令 x=140+63+30=223,很容易可檢定出 x 滿足最原始的三個線性同餘 式。其實 x=223+105k 即為通解。 當 k=2時,x=23 為得到的最小整數解。 所謂的“除百零五便得知”,指的就是將233除以105得到 x=23的 最後解。

範例四 範例三的解答似乎是針對特殊的三個線性同構式, 範例四 範例三的解答似乎是針對特殊的三個線性同構式, 可否給一個較一般的通解 假設有m個線性同構式如下所示: x  r1(P1) x  r2(P2) x  rm(Pm) (6.4.2) 這裡 gcd(Pi,Pj)=1,當ij x  0(P1) x  0(P2) x  1(Pi) x  0(Pm) (6.4.3) … … …

滿足式(6.4.3)所述m個同構式的解之形式為: (6.4.4) 式(6.4.4)中的bi可用嘗試法求得,將式(6.4.3)中的第 i 個式子調整回 x  ri(Pi) 則滿足調整後的 個同餘式之解為: x=riSibi 所要的通解,其型式如下: 將所求的通解再除以 即得到最小的正整數解,如下所示:

例題4.1 請找出滿足下列線性同餘式的最小整數解: 例題4.1 請找出滿足下列線性同餘式的最小整數解: X  1(3) X  4(5) X  2(7) 根據前面的中國餘式定理,可得到: x  184 (105) 故 x  184 + 105t ,tZ 當t=1時,可得最小正整數解184 105=79