商餘計算

出自維基百科,自由嘅百科全書
跳去: 定向搵嘢

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

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

等價關係[編輯]

內文: 同餘

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

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

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

例子:

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

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

同餘加法同乘法[編輯]

內文: 同餘

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

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

餘數定理嘅應用[編輯]

內文: 餘數定理

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

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

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

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

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

證明:

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

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

所以得出

應用[編輯]

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

睇埋[編輯]