GMAT數(shù)學(xué)考點解析：求余數(shù)

我在自己的討論稿文檔里，求余的時候，都會用到 mod 這個運算符。

mod：模。意思就是求余數(shù)。

比如說：5 mod 3=2， 100 mod 11=1

讀作：五模三余二，一百模十一余一

這是標(biāo)準(zhǔn)的公式化寫法，大家可能不太熟悉，但是知道意思了，其實也很簡單。引入Mod，主要是可以用數(shù)學(xué)公式來寫，而且可以把求余數(shù)的問題化簡成為普通的四則運算的問題，也比較容易表達。

在講如何求余之前，先來普及一下余數(shù)的一些性質(zhì)。

首先就是余數(shù)的加減法：比如說100除以7余2，36除以7余1。那么100+36除以7余幾呢?或者100-36除以7余幾呢?很顯然，只要用100除以7的余數(shù)2與36除以7的余數(shù)1進行加減就可以得到答案。通過這個例子可以很明顯的看出來，余數(shù)之間是可以加減的。

總結(jié)寫成書面的公式的話，就是：(M+N) mod q=((M mod q)+(N mod q)) mod q

然后我們再看余數(shù)的乘法：我們繼續(xù)來看上面這個例子，如果要求100*36除以7的余數(shù)是多少，該怎么求呢?

我們不妨來這樣做：

100=98+2=7*14+2，36=35+1=7*5+1;

這時100*36=(7*14+2)(7*5+1)=7*14*7*5 + 2*7*5 + 7*14*1 + 2*1

很明顯，100*36除以7的余數(shù)就等于2*1=2

于是我們可以得出這樣的一個結(jié)論：求M*N除以q的余數(shù)，就等于M除以q的余數(shù) 乘以 N除以q的余數(shù)。

類似的，如果是求N^m 除以q的余數(shù)呢?只要我們將N^m=N*N*N*...*N，也就是說分別地用每個N除以q的余數(shù)相乘，一共m個，得出的結(jié)果再對q求余數(shù)，即可求出結(jié)果。

舉例來說：求11^4除以9的余數(shù)�；�成公式即是：11^4 mod 9=?

11^4 mod 9 = (9+2)^4 mod 9 = 2^4 mod 9 =16 mod 9 = 7

于是我們可以總結(jié)出這樣的公式：

M*N mod q=(M mod q)*(N mod q) mod q

( M^n mod q = (M mod q)^n mod q )

那么，我們知道了這些性質(zhì)之后對解題又有什么幫助呢?

As we all know，如果一個數(shù)乘以1，還是等于原數(shù);而1的任意次方，還是等于1。

所以在解答這一類的問題的時候，只要我們盡量把計算中的余數(shù)湊成與1相關(guān)的乘式，結(jié)果顯然會好算很多的。(或者-1，2之類的比較容易進行計算的數(shù)字都可以，因題而異。)

舉例說明：求3^11除以8的余數(shù)。題目即是：3^11 mod 8=?

3^11 mod 8

=3^10 * 3^1　　　(mod 8)

=(3^2)^5*(3^1) (mod 8)

=9^5 * 3　　　 　(mod 8)

=(8+1)^5 *3　　　(mod 8)

=1^5 *3　　　　 (mod 8)

=3

發(fā)現(xiàn)沒有，甚至沒有去計算什么尾數(shù)的規(guī)律，答案就算出來了，而且只用了加減乘除。

那么再來看一道題目：求 (2^100)*(3^200) 除以7的余數(shù)

先化成計算公式：

(2^100)*(3^200)　　　　　　　　　mod 7

=[2^(3*33 + 1)] * [3^(3*66 + 2)]　　 mod 7

=[(2^3)^33 * 2] * [(3^3)^66 * 3^2]　mod 7

=(8^33 * 2) * (27^66 * 9)　　　　　　mod 7

=[(7+1)^33 * 2] * [(28-1)^66 * 9]　　mod 7

=(1^33 * 2)* [(-1)^66 * 9]　　　　　　mod 7

=2*9　　　　　　　　　　　　　　　　mod 7

=4

注意：如果余數(shù)有負號，就當(dāng)做負數(shù)一樣計算。

我步驟寫得很詳細，但其實只要是熟練了，基本上只要三四步答案一定就出來了，有沒有覺得很簡單呢?趕緊找一兩題來練練手吧，甚至隨便寫幾個數(shù)字來做做試試看，像我上面的例題都是臨時編的。

相信只要練習(xí)了三四道題目，以后再碰到這樣的余數(shù)題，就會會心地一笑：小樣，秒掉你!