GMAT考試數學求余數題型

第第頁GMAT考試數學求余數題型

略微補充一個定理：

歐拉定理(也稱費馬-歐拉定理)是一個關于同余的性質。歐拉定理說明，假設n,a為正整數，且n,a互素，(a,n)=1，那么

a^(n)1(modn)

假如n是質數那么(n)=n-1，這個定理就變成了GMAT數學費馬小定理。

余數是1，意味著可以(n)的倍數可以徑直清除!

定理不用記憶，我們徑直做GMAT考試題目：

題一：

7^50除以15的余數

15分解為3和5兩個質數3-1=2、5-1=4

根據費馬小定理，7平方除3的時候余數是1;7的4次方去除5的余數是1

所以7的4次方除15的時候余數是也是1

7^50((7^4)^12)*7^27^2=494(mod15)

題二：

3^50除以8的余數(8)=4

3^503^21(mod8)

題三：

13^50除以8的余數(8)=4

13^5013^21(mod8)

題四：

10006的10003次方，除17的余數1000610(mod17)

100033(mod16)

10006^1000310^3=100014(mod17)

關于GMAT入門歐拉函數的運用

GMAT可能考到的狀況中，除數確定是小于20的。但是歐拉函數是靠數數數出來的(數數,數)，數數是考場上最簡單出錯的計算步驟!比如8的歐拉函數，就是比8小而且和8互質的數字(1,3,5,7)，一共4個，就是4。但是數的時候很簡單把1給漏了!

那就先分析一下吧：

除數1-4不可能考，選項都不夠放呀

56710111314151719這些數字，要么是質數，要么是兩個質數的乘積，所以都不需要求歐拉函數。

剩下來8912161820(這些數是4的倍數或者9的'倍數)，對應的歐拉函：

84

96

124

168

208

記住了就可以了，特別是前3個?；蛘弋攬鰯档怯涀?，數出來確定是4、6或者8。

我再出個簡明操作手冊

A的B次方，除以C，余數是多少?

附加條件：A，C互質

解法：

1第一步：假如A比C大，那么徑直用A除以C求出余數A，把A替換掉。

2第二部：求C的歐拉函數，假如C是質數，歐拉函數就是C-1;假如C是幾個不同的質數相乘，那么就取這些質數各自減一之后的那組數的最小公倍數;假如是8912161820，那么對應是464868。求出了的歐拉函數值為o。不需要記住歐拉函數，可以做題的時候數出來。

3第三部：假如B比o大，那么B徑直除以o求出余數B，把B替換掉。

4第四部：徑直算吧，數字已經很小了。

舉個例子：10006的10003次方，除17的余數

5第一步：10006除以17余10，用10替換10006

6第二部：17的歐拉數是16

7第三部：10003除以16余3，用3替代10003

8第四部：求出10的3次方，除以17，余數是14

歐拉函數的定義：正整數N的歐拉函數，就是比N小，而且和N互質的正整數的個數。

舉個例子10，和1,3,7,9互質，10的歐拉函數就是4。

(數的時候不要忘了把1數進去!)

20以內的歐拉函數(或替代歐拉函數)表：

54質數，后面質數都不標了

626=2*3,1和2的公倍數，事實上也是6的歐拉數

76

84歐拉函數

96歐拉函數

10410=2*5,1和4的公倍數，事實上也是10的歐拉數

1110

124歐拉函數

1311

14614=2*7，1和6的公倍數，事實上也是14的歐拉數

15415=3*5，2和4的公倍數，可替代歐拉數，而15真正歐拉數是8

168歐拉函數

1716

186歐拉函數

1918

208歐拉函數

不用記住，有個印象就可以，做題的時候數就可以。20以內，非質數的歐拉函數全都是4、6、8，除了6的歐拉數是2以外。

最末，假如超出歐拉定理的適用范圍,a和n不互質,該怎么辦呢?

約分!約到互質不就可以了!不過別忘了最末要把余數再乘以被約掉的數。

求：3^7除以15的余數

除數和被除數都除以3，約分以后，先求