跳去內容

同餘

出自維基百科,自由嘅百科全書
(由共餘跳轉過嚟)

同餘(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乘入去,得到

因為同餘嘅傳遞性,

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

應用

[編輯]

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

證明:

可以將寫成就係嘅數字。

因為,所以

睇埋

[編輯]