MOD(同餘符號)

MOD，同餘符號，在數學上，兩個整數除以同一個整數，若得相同餘數，則二整數同餘（英文：Modular arithmetic；德文：Kongruenz）。同餘理論常被用於數論中。最先引用同餘的概念與符號者為德國數學家高斯。

定義

同餘理論是初等數論的重要組成部分,是研究整數問題的重要工具之一,利用同餘來論證某些整除性的問題是很簡便的.同餘是數學競賽的重要組成部分.

兩個整數a，b，若它們除以整數m所得的餘數相等，則稱a，b對於模m同餘

記作 a ≡ b (mod m) 　讀作a同餘於b模m，或讀作a與b關於模m同餘。

比如 26 ≡ 14 (mod 12)

性質

下列運算中的a、b、c、d均為整數，x為正整數

(1)若a≡b (mod x)，則a±c≡b±c (mod x)

(2)若a≡b (mod x)，則a±by≡b±ay (mod x)

(3)若a≡b (mod x)，則a±cx≡b±dx (mod x)

若有一個f進制的l位的數e，從低到高的位數依次為c0、c1、c2、c3、c4、...、cl，即e=cl*f^l+c(l-1)*f^(l-1)+...+c0*f^0則

(4)a^e(mod x)≡

關於MOD的例題

例題1

（2^2011+1）是否為質數？

解：2^2011+1≡(-1)^2011+1≡-1+1≡0 (mod 3)，故3|(2^2011+1)，即(2^2011+1)不是質數.

例題2

證明：數列11,111,1111……中沒有完全平方數

解：易知該數列中若有完全平方數，則為奇數的平方，設該數為n，則n≡1 (mod 4)<=>n-1≡0 (mod 4)，則該數減去1後能被4整除，但該數列中任何一個數減去1後末兩位都是10，這導致4|10，矛盾。

例題3

設p是素數，q=4^p+p^4+4也是素數，求p+q的值。

例題4

試求：最小的素數，使得對於某個整數n，這個素數能整除n^2+5n+23.