商餘計算

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

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

可以利用「一個鐘」嚟理解商餘計算,朝早九點加五個鐘就係下晝兩點。喺個鐘上面會顯示由九變做二,呢個係常見又易明嘅一個例子。

等價關係

內文: 同餘

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

 
呢個定義可以滿足到呢三個運算。

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

例子:

 

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

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

同餘加法同乘法

內文: 同餘

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

  •  
  •  
  •  

注意:同餘關係係無除法。

餘數定理嘅應用

內文: 餘數定理

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

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

 

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

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

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

 
證明:

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

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

 
所以得出 

應用

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

睇埋