商餘計算

將一個數除一個數得出既餘數

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

時鐘記時就係用商餘12運算。

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

等價關係

內文:同餘

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

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

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

例子:

 

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

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

同餘加法同乘法

內文:同餘

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

  •  
  •  
  •  

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

餘數定理嘅應用

內文:餘數定理

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

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

 

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

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

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

 
證明:

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

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

 
所以得出 

應用

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

睇埋