商餘計算

出自維基百科,自由嘅百科全書
時鐘記時就係用商餘12運算。

商餘計算英文Modular Arithmetic),或者叫做商餘數學,書面語可能叫做「模數學」,係數學入面一套特別嘅整數計算,早係1801年就已經喺高斯本書Disquisitiones Arithmeticae入面記載。

可以利用「時鐘」嚟理解商餘計算,朝早9點加5個鐘就係下晝2點,喺個鐘上面會顯示由9變做2,其實就係因為9+5=14,而14除以12餘2。呢個就一個常見又易明嘅例子。

等價關係[編輯]

內文:同餘

商餘計算主要集中喺同餘關係上面,而同餘係一個等價關係。用數字式嚟定義同餘呢個關係可以寫成:

呢個定義同呢三個運算都係兼容(compatible)嘅,用加法嚟做例子,就係如果有同埋,咁就可以推導出

假設揀定咗一個正整數。「嘅同餘」,數學式會寫做

例子:

從普通角度了解就係,同埋。由此可見,佢哋嘅同餘都係1,所以喺同餘呢個關係上面,佢哋係一樣。

從定義嘅角度嚟睇,。而40係可以被5除盡,即係。因此符合定義。

同餘加法同乘法[編輯]

內文:同餘

假設有兩個同餘關係, 同埋 。可以得出:

注意:同餘關係入面嘅除法同平時做嘅除法好唔同。

餘數定理嘅應用[編輯]

內文:餘數定理

舉個例,利用餘數定理將16除3,得出。因而得知,16除3嘅餘數係1。數學上會將「16除3嘅餘數係1」呢件事叫做商餘(mod),數學式會寫

再舉多個例,因為。如果跟返上面嘅定義,得知

由此可見「」可以解做「」,但係因為數學上唔止一個等價關係,所以會寫做「」嚟區別。而從同一個例子可以見到:

注意:左面嘅係「」,而右面嘅係「」。

由上面嘅性質推斷落去,可以得知

證明:

,利用餘數定理即係有某啲整數符合,

,利用餘數定理即係有某啲整數符合,

所以得出

應用[編輯]

如果係兩個整數,係質數,咁

睇埋[編輯]