模算數






這個時鐘計時方式使用了模數為12的模算數


模算數（modular arithmetic）是一個整数的算术系統，其中數字超過一定值後（稱為模）後會「捲回」到較小的數值，模算數最早是出現在卡爾·弗里德里希·高斯在1801年出版的《算术研究》一書中。


模算數常見的應用是在十二小時制，將一天分為二個以十二小時計算的單位。假設現在七點，八小時後會是三點。用一般的算術加法，會得到7 + 8 = 15，但在十二小時制中，超過十二小時會歸零，不存在「十五點」。類似的情形，若時鐘目前是十二時，二十一小時後會是九點，而不是三十三點。小時數超過十二後會再回到一，為模12的模算數系統。依照上述的定義，12和12本身同餘，也和0同餘，因此12:00的時間也可以稱為是0:00，因為模12時，12和0同餘。




目录






  • 1 同餘關係


  • 2 應用


  • 3 參考資料


  • 4 相關條目





同餘關係



Disambig gray.svg  本章節介紹的是mod n的表示法。關於二元的mod運算，請見“模除”。

模算數可以在導入整數的同餘關係後，以數學的方式處理，同餘關係和整數的加法、減法及乘法相容。針對正整數n，二個整數a和b對於模n同餘




a≡b(modn),{displaystyle aequiv b{pmod {n}},,}{displaystyle aequiv b{pmod {n}},,}

若二數的差值a − b為n的整數倍數（若n整除a − b）。數字n稱為同餘關係的模。


例如


38≡14(mod12){displaystyle 38equiv 14{pmod {12}},}{displaystyle 38equiv 14{pmod {12}},}

因為38 − 14 = 24，是12的倍數。


上述的概念也對負數有效：


−8≡7(mod5)2≡−3(mod5)−3≡−8(mod5).{displaystyle {begin{aligned}-8&equiv 7{pmod {5}}\2&equiv -3{pmod {5}}\-3&equiv -8{pmod {5}}.end{aligned}}}{displaystyle {begin{aligned}-8&equiv 7{pmod {5}}\2&equiv -3{pmod {5}}\-3&equiv -8{pmod {5}}.end{aligned}}}

而a ≡ b mod n也可以用計算带余除法的余数時，a和b除以n的余数相同來表示。例如


38≡14(mod12){displaystyle 38equiv 14{pmod {12}},}{displaystyle 38equiv 14{pmod {12}},}

因為38和14除以12時，餘數都為2。這是因為38 − 14 = 24是12的整數倍，符合之前同餘關係的定義。


因為常常會考慮不同模數的同餘關係，因此表示同餘關係時會用a ≡ b mod n的表示法。除去三元的表示法不論，同餘關係其實是二元关系，用a ≡nb就可以看出此一特性。


同餘關係可以和加法、減法及乘法一起使用時。若


a1≡b1(modn){displaystyle a_{1}equiv b_{1}{pmod {n}}}{displaystyle a_{1}equiv b_{1}{pmod {n}}}

及


a2≡b2(modn),{displaystyle a_{2}equiv b_{2}{pmod {n}},}{displaystyle a_{2}equiv b_{2}{pmod {n}},}

則



  • a1+a2≡b1+b2(modn){displaystyle a_{1}+a_{2}equiv b_{1}+b_{2}{pmod {n}}}{displaystyle a_{1}+a_{2}equiv b_{1}+b_{2}{pmod {n}}}

  • a1−a2≡b1−b2(modn).{displaystyle a_{1}-a_{2}equiv b_{1}-b_{2}{pmod {n}}.}{displaystyle a_{1}-a_{2}equiv b_{1}-b_{2}{pmod {n}}.}


若模算數延伸到包括所有实数，上式也成立，也就是說a1, a2, b1, b2, n不一定都是整數，不過以下的關係在不都是整數時可能會不成立：


  • a1a2≡b1b2(modn).{displaystyle a_{1}a_{2}equiv b_{1}b_{2}{pmod {n}}.,}{displaystyle a_{1}a_{2}equiv b_{1}b_{2}{pmod {n}}.,}


應用


模算數在数论、群论、环论、紐結理論、抽象代数、電腦代數（英语：computer algebra）、密码学、计算机科学及化學中都有使用，也出現在視覺藝術及音乐。


模算數是数论的基礎之一，也提供了群论、环论及抽象代数中一些重要的範例。


模算數也常作為識別碼的校验码。例如国际银行账户号码（IBAN）就用模97的餘數來避免輸入編號時的錯誤。


在密碼學中，模算數是 RSA及迪菲-赫爾曼等公开密钥加密系統的基礎，也提到了和 椭圆曲线有關的有限域，用在許多的系統化鑰演算法（英语：symmetric key algorithm）中，包括高级加密标准（AES）、國際資料加密演算法（IDEA）、及RC4。RSA和迪菲-赫爾曼密鑰交換用到了模冪（英语：modular exponentiation）。


在電腦代數中，模算數常用來限制中間計算的整數係數大小，也限制計算中用到的資料。模算數用在多項式分解（英语：polynomial factorization）中（其中所有已知有效率的演算法都用到了模算數），而針對整數及有理數的多項式最大公因式（英语：polynomial greatest common divisor）、线性代数及Gröbner基（英语：Gröbner basis），最有效率解法都用到了模算數。


計算機科學中，模算數會以位操作的方式表示，也和其他定長度、循環式的数据结构有關。許多编程语言及计算器中都有模除，而XOR是二個位元在模2下的和。


化學中，表示化合物編號的CAS号，最後一碼是校验码，是將CAS号前二位數乘以1、下一位乘以2，再下一位乘以3……，最後對10取餘數而得。


音樂上，模12的模算數用在十二平均律的系統中，其中有純八度及異名同音的情形（，例如升音符的C音和降音符的D音會視為是同一個音）。


去九法是徒手計算時快速的檢查工具，是以模9的模算數為基礎，而且其中最重要的性質是 10 ≡ 1 (mod 9)。


模7的模算數在許多計算特定日期是星期幾的演算法中出現，特別是蔡勒公式及判决日法则（英语：doomsday algorithm）中。


模算數也用在像法律（像分配數（英语：Apportionment (politics)））、经济学（像博弈论），若一些社会科学的分析會強調資源的比例分割（英语：Proportional (fair division)）及分配，也會用到模算數。



參考資料





相關條目




  • 布尔环

  • 環形緩衝區

  • 同餘關係

  • 除法

  • 有限域

  • 勒让德符号

  • 模冪（英语：modular exponentiation）

  • 模反元素

  • 模除

  • 数论


  • 皮萨诺周期（模n下的斐波那契序列）

  • 原根

  • 二次互反律

  • 二次剩余

  • 两元素布尔代数

  • 和模算數有關的群論主題：

    • 循環群

    • 整数模n乘法群



  • 其他和模算數有關的重要定理：

    • 卡邁克爾函數

    • 中国剩余定理

    • 欧拉定理 (数论)

    • 费马小定理

    • 拉格朗日定理 (群論)











Comments

Post a Comment

Popular posts from this blog

Information security

Image
This article is part of a series on Information security Related security categories Internet security Cyberwarfare Computer security Mobile security Network security Threats Computer crime Vulnerability Eavesdropping Malware Spyware Ransomware Trojans Viruses Worms Rootkits Bootkits Keyloggers Screen scrapers Exploits Backdoors Logic bombs Payloads Denial of service Defenses Computer access control Application security Antivirus software Secure coding Secure by default Secure by design Secure operating systems Authentication Multi-factor authentication Authorization Data-centric security Encryption Firewall Intrusion detection system Mobile secure gateway Runtime application self-protection (RASP) v t e Information security , sometimes shortened to InfoSec , is the practice of preventing unauthorized access, use, disclosure, disruption, modification, inspection, recording or destruction of information. Th...
Read more

Volkswagen Group MQB platform

Image
The Volkswagen Group MQB platform is the company's strategy for shared modular design construction of its transverse, front-engine, front-wheel-drive layout (optional front-engine, four-wheel-drive layout) automobiles. Volkswagen spent roughly $60bn [1] developing this new platform and the cars employing it. The platform underpins a wide range of cars from the supermini class to the mid size SUV class. MQB allows Volkswagen to assemble any of its cars based on this platform across all of its MQB ready factories. This allows the Volkswagen group flexibility to shift production as needed between its different factories. Beginning in 2012, Volkswagen Group marketed the strategy under the code name MQB , which stands for Modularer Querbaukasten , translating from German to "Modular Transversal Toolkit" or "Modular Transverse Matrix". [2] [3] MQB is one strategy within VW's overall MB (Modularer Baukasten or modular matrix) program which also includes th...
Read more

刘萌萌

Image
body.skin-minerva .mw-parser-output table.infobox caption{text-align:center} 刘萌萌 女演员 罗马拼音 Liu Meng Meng 英文名 Cya 国籍   中国 民族 汉族 出生 ( 1989-10-16 ) 1989年10月16日 （ 29歲）   中国辽宁省大连市 职业 演员、艺人 语言 汉语 教育程度 沈阳音乐学院 北京电影学院表演系进修班 活跃年代 2011年至今 唱片公司 浙江永乐影视制作有限公司 经纪公司 浙江永乐影视制作有限公司 网站 刘萌萌 官方微博 刘萌萌 （1989年10月16日 － ），汉族，中国演员，2010年参加湖南卫视《芒果训练营》而出道至今，凭借电视剧《爱情公寓》“诺澜”一角走红。北京电影学院10级表演系（进修班）毕业。 目录 1 主要经历 2 影视作品 2.1 电视剧 2.2 电影 2.3 综艺节目 3 参考文献 4 外部链接 主要经历 1989年，出生于辽宁省大连市一个工人家庭； 2006年，考入沈阳音乐学院舞蹈系本科班学习； 2010年，参加湖南卫视《芒果训练营》演艺新秀比赛而出道 [1] ；進入北京电影学院表演系进修班 2011年，出演电视剧《隋唐演义》“琼花公主”一角色； 2012年，担任电视剧《爱情公寓》“诺澜”一角并开始走红 [2] ； 2013年，担任电视剧《利箭纵横》《利剑行动》 [3] 女主角“林筱雨” 2014年，参加江苏卫视真人秀栏目《花样年华》 [4] 备受瞩目 [5] 。 影视作品 电视剧 首播年份 剧名 角色 备注 2012 《爱情公寓3》 诺澜 2012 《利箭行动》 林筱雨 2013 《隋唐演义》 琼花公主 2013 《决战燕子门》 马晓婉 2014 《利箭纵横》 林筱雨 2014 《屌丝日记》 林洛霏 網絡劇 2014 《爱情公寓4》 诺澜 ...
Read more