同餘

兩個不同數字既同餘係一樣既話,姐係兩個數除同一個數字,所得餘數係一樣。
(由共餘跳轉過嚟)

同餘(Congruence Modulo)係指兩個整數除另一個整數,呢兩個數嘅餘數都係一樣。喺現代嘅數學基礎中,同餘係一個等價關係。數學上,同餘會以「」表達。

考慮澌所有整數,除數(即模數)相同下、餘數亦相同嘅一羣整數就叫做「同餘類」。一個簡單例子係,嘅同餘類就同啲整數嘅個位數對應(0: 10, 20... 1: 11, 21...)。

定義

編輯

如果兩個整數a、b係m嘅同餘既話,即係話a除m同b除m所得出嘅餘數係一樣。以數學表達嘅話即係:

 

同餘有一個等價嘅定義,就係m係可以整餘到 

例一

編輯

因為12同14除2都係餘0,所以可以寫成 

證明

編輯

證明同餘係等價關係。根據「 」嘅要求,就需要證明,自反性、對稱性、傳遞性。

  • 自反性:( ) 一個整數除另一個整數嘅餘數係不變,所以 
  • 對稱性:( ) 如果a同b係m嘅同餘, 

相對嘅定義係: 

抽因式,抽個負出嚟, 

最後得出, 

  • 傳遞性:( ) 如果a同b係m嘅同餘,同時b同c又係m嘅同餘,即係 

相對嘅定義係, 同埋 

將兩條式互相加埋得出, 

最後得出, 

因此,呢個係一個等價關係。

商餘計算

編輯

其實商餘同同餘嘅關係係密不可分。

計算規則

編輯
  1. 如果 ,有一個整數 ,會令到 
  2. 如果 ,有一個整數 ,會令到 

其實以上嘅規則係需要證明。呢兩條規則嘅意思係,同餘嘅方程係同普通嘅無分別,都係可以乘同埋除。不過有一點要注意嘅係 係整數,所以除法係唔存在。換句話嚟講,(2)係唔可以好似普通方程咁約簡。

同餘約簡

編輯

如果 ,而 嘅話,就會有一個整數 ,會令到 。變相將個n約走咗啦。

證明:利用比舒公式同埋輾轉相除法,知到會有整數 符合 

利用上面嘅公式,得知 

如果將上面嘅n乘入去 ,得到 

因為同餘嘅傳遞性, 

同餘約簡可以係一個解線性商餘方程嘅工具。有關計算例子可以睇線性商餘方程

應用

編輯

同餘可以證明一啲結果。例如:一個整數 係可以被 整除,咁佢每個數字都可以被 整除。「 

證明:

可以將 寫成  就係 嘅數字。

因為 ,所以 

睇埋

編輯