GMAT数学之光—余数的底层逻辑

数学之光—余数通解

高斯同余定理问题

所有的余数问题，从本质上来说，都是高斯同余定理问题。所以掌握高斯同余定理就是掌握了余数的通解。

为了方便讨论，我们将a除以m后求得的余数写为：

r(a) (mod m)

高斯同余定理的形式非常简单，分别是加，减，乘三项定理：

(1) r(a) ± r(b) = r(a ± b)

(2) r(a) * r(b) = r(a * b)

也就是说，两个数相加（或相减相乘）后除以某个数的余数，等于这两个数分别除以这个数后的余数再相加（或相减相乘）。

例如，如果我们想知道8除以3余几，那么，由于8=5+3，所以我们可以先求5除以3的余数，再求3除以3的余数，最后再相加。

r(8) = r(5+3) = r(5)+r(3) = 2 + 0 = 2 (mod 3)

又例如：

r(9) = r(5)+r(4) = 2+1 = 3 (mod 3)

请注意，当余数大于或等于除数时，可以继续除下去，直到得到真正的余数，即，除以3余3等于除以3余0。因此，r(9) = r(5)+r(4) = 2+1 = 3 = 0。

这个定理在很多“数学常识”中发挥着极其重要的作用。例如，请判断：

2134是否能被3整除？

咱们小学就学过，只要检查2134中的“各个数位相加的和”是否能被3整除即可。即，因为2+1+3+4 = 10，且10不能被3整除，所以2134也不能被3整除。

这个“常识”就是高斯同余定理的一个简单应用。

我们可以把2134先写成：

2000+100+30+4

根据高斯同余的加法定理，求2134除以3的余数，就是求这四个数分别除以3的余数之后再相加，即：

r(2000+100+30+4) = r(2000)+r(100)+r(30)+r(4)=r(2*1000)+r(1*100)+r(3*10)+r(4*1)

利用同余乘法定理：

r(2*1000)+r(1*100)+r(3*10)+r(4*1) = r(2)*r(1000)+r(1)*r(100)+r(3)*r(10)+r(4)*r(1)

无论10的多少次方除以3，它余数都为1，因此：

r(2)*r(1000)+r(1)*r(100)+r(3)*r(10)+r(4)*r(1) = r(2)+r(1)+r(3)+r(4)

再用一次高斯同余的加法定理，则有：

r(2)+r(1)+r(3)+r(4) = r(2+1+3+4)

由此我们利用高斯同余定理证明了，r(2134) = r(2+1+3+4)，即，2134除以3的余数和2+1+3+4除以3的余数相同。

因此，如果r(2+1+3+4) = 0，那么r(2134) =0，即，2134能被3整除。显然地，由于r(2+1+3+4) = r(10) = 1，所以2134除以3的余数为1，不能被3整除。

可以说，但凡题目中出现了divided，divisible，和remainder这样的词，其实都是在考查我们对于高斯同余定理的熟练使用。

例题1：

If n is a positive integer and r is the remainder when 4 + 7n is divided by 3, what is the value of r?

(1) n + 1 is divisible by 3.

(2) n > 20

(A) Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

(B) Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.

(D) EACH statement ALONE is sufficient.

(E) Statements (1) and (2) TOGETHER are NOT sufficient.

解：

题目问的是4+7n除以3的余数。根据高斯同余加法和乘法定理可知

r(4+7n) = r(4)+r(7n)= r(4)+r(7)*r(n) = 1+1*r(n) = 1+r(n)

因此，想知道4+7n除以3的余数，只需要知道n除以3的余数即可。

条件1：n+1是可以被3整除的，即，r(n+1) = r(n)+r(1) = r(n)+ 1 = 0。

r(n)+ 1 = 0 相当于 r(n)+ 1 = 3，即，r(n) = 2。充分。

条件2：n大于20，显然无法得知n除以3的余数，不充分。

综上，答案为A。

例题2：

If x is an integer greater than 0, what is the remainder when x is divided by 4?

(1) The remainder is 3 when x+1 is divided by 4.

(2) The remainder is 0 when 2x is divided by 4.

(A) Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

(B) Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.

(D) EACH statement ALONE is sufficient.

(E) Statements (1) and (2) TOGETHER are NOT sufficient.

解：

题目问的是，x除以4余几。

条件1：当x+1除以4的时候，余数为3。根据高斯同余定理中的加法定理，则有

r(x+1) = r(x)+r(1) = r(x)+1 = 3

则

r(x) = 2；充分。

条件2说，2x除以4余数为0，我们只能确定x是2的倍数，不能确定x是否是4的倍数，因此不充分。

综上，答案为(A)。

例题3

What is the remainder when the positive integer n is divided by 3?

(1) The remainder when n is divided by 2 is 1.

(2) The remainder when n + 1 is divided by 3 is 2.

(A) Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

(B) Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.

(D) EACH statement ALONE is sufficient.

(E) Statements (1) and (2) TOGETHER are NOT sufficient.

解：

题目问的是n除以3的余数。

条件1：n除以2余1。显然地，n除以2的余数和n除以3的余数无关。不充分。

条件2：n+1除以3余2。根据高斯同余的加法定理，

r(n+1)=r(n)+r(1)=2

由此可知，

r(n) = 1。充分。

综上，答案为B。

例题4

If x and y are positive integers, what is the remainder when 10^x + y is divided by 3?

(1) x = 5

(2) y = 2

(A) Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

(B) Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.

(D) EACH statement ALONE is sufficient.

(E) Statements (1) and (2) TOGETHER are NOT sufficient.

解：

题目问的是，10^x + y除以3的余数。根据高斯同余定理的加法定理可知，

r(10^x + y) = r(10^x)+r(y)

无论是10的多少次方，它除以3的余数一定为1。

关于这一点，也可以用高斯同余定理的乘法定理来证明。我们知道，10除以3余数为1，即，在除以3时，10和1的余数相同，可以写为：

r(10)=r(1)

让等式两边同时乘以自己，可得

r(10)* r(10)=r(1)* r(1)

根据同余乘法定理，则有：

r(10*10) = r(1*1)

r(100)=r(1)

以此类推，无论10的多少次方，永远和1同余。

因此，

r(10^x)+r(y) = 1+r(y)

也就是说，我们只需要知道y是几，既可以知道问题的答案。

综上，答案为B。

例题5

If t is a positive integer and r is the remainder when t^2+5t+6 is divided by 7, what is the value of r?

(1) When t is divided by 7, the remainder is 6.

(2) When t^2 is divided by 7, the remainder is 1.

(A) Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

(B) Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.

(D) EACH statement ALONE is sufficient.

(E) Statements (1) and (2) TOGETHER are NOT sufficient.

解：

题目问的是t^2+5t+6除以7的余数。

条件1：t除以7的时候，余数为6。显然地，根据高斯同余定理的乘法定理，知道r(t)等于知道r(t^2)。因此，t^2+5t+6除以7的余数可以分别计算出来。这个条件是充分的。

条件2：t^2除以7，余数为1。

这个条件有些难度，乍看之下，也是充分的，但我们需要仔细求证。根据高斯同余乘法定理，则有：

r(t^2)=r(t)*r(t) =r(1)=1

如果t除以7的余数为1，那么r(t)*r(t) =1；

如果t除以7的余数为2，那么r(t)*r(t) =r(4)=4；

如果t除以7的余数为3，那么r(t)*r(t) =r(9)=2，由于9比7大，所以实际的余数是2，下同；

如果t除以7的余数为4，那么r(t)*r(t) =r(16)=2；

如果t除以7的余数为5，那么r(t)*r(t) =r(25)=4；

如果t除以7的余数为6，那么r(t)*r(t) =r(36)=1。

显然地，t除以7余1和余6时，t^2除以7的余数均为1。因此，无法确定t除以7的余数。不充分。

综上，答案为A。

例题6

What is the remainder when the positive integer n is divided by the positive integer k, where k > 1?

(1) n = (k + 1)^3

(2) k = 5

(A) Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

(B) Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.

(D) EACH statement ALONE is sufficient.

(E) Statements (1) and (2) TOGETHER are NOT sufficient.

题目问的是，n除以k的余数为几。

由条件1可知，在除以k时，r(n) = r((k + 1)^3) 。根据高斯同余定理的乘法定理可知，

r((k + 1)^3) = r(k+1)* r(k+1)* r(k+1)

又因为r(k+1)=r(k)+r(1) = 0+1 = 1

因此，r(n) = r(k+1)* r(k+1)* r(k+1) = 1*1*1 = 1。充分。

条件2只给出了k的值，无法得知n除以k的余数，不充分。

综上，答案为A。

例题7

If x, y, and z are positive integers, what is the remainder when 100x + 10y + z is divided by 7?

(1) y = 6

(2) z = 3

(A) Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

(B) Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.

(D) EACH statement ALONE is sufficient.

(E) Statements (1) and (2) TOGETHER are NOT sufficient.

解：

题目问的是，100x + 10y + z除以7的余数。根据高斯同余定理：

r(100x + 10y + z) = r(100x)+r(10y)+r(z) = r(100)*r(x)+r(10)*r(y)+r(z) = 2*r(x)+3*r(y)+r(z)

依然需要知道x, y, z分别除以7的余数。

显然地，条件1加条件2都不够。综上，答案为E。

余数公式问题

余数公式的本质也是除法运算的本质。

除法的本质是“排队”。

例如，请问，如何将10个小球按照4个球一行的方式进行排队？

如果不出现意外的话，大家应该都是这么排的：

0 0 0 0

0 0

我们能排出两个完整行并且会余下两个小球。

因此，在除法运算中规定，能排成几个完整的行即是“商（quotient）”，还剩下的小球数为“余数（remainder）”。运用数学公式可以写为：

y = x*q + r （0=

y是被除数，x是除数，q是商，r是余数。

例如，10除以4，商为2，余数为2，即：

10 = 4*2+2

如果“被除数”比“除数”小，则商为0，余数等于被除数。

例如被除数是5，除数为7，则商为0，余数为5。

例题1

If r is the remainder when the positive integer n is divided by 7, what is the value of r?

(1) When n is divided by 21, the remainder is an odd number.

(2) When n is divided by 28, the remainder is 3.

(A) Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

(B) Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.

(D) EACH statement ALONE is sufficient.

(E) Statements (1) and (2) TOGETHER are NOT sufficient.

解：

题目问的是，n除以7，余数为几。两个条件给出的都是n除以其它数的余数。原则上，我们无法判断n除以不同数后的余数关系。但是，有一种情况例外，当除数之间是倍数关系时，利用余数公式和高斯同余定理，可以得到余数的关系。例如本题。

条件1：n除以21，余数是奇数。显然，只告诉我们余数是奇数，无法判断余数具体是几，不充分。

条件2：n除以28，余数是3。可以看到，28是7的倍数。由此，我们可以利用余数公式将n写为：

n = 28k+3

根据高斯同余定理

r(n) = r(28k)+r(3) = r(28)*r(k) + r(3)

因为28是7的倍数，所以r(28) = 0。

由此可知

r(n) = 0*r(k) + r(3) = 0+3 = 3

充分。

综上，答案为B。

例题2

When the integer n is divided by 17, the quotient is x and the remainder is 5. When n is divided by 23, the quotient is y and the remainder is 14. Which of the following is true?

(A) 23x+17y=19

(B) 17x-23y=9

(D) 14x+5y=6

(E) 5x-14y=-6

解：

依题意，n = 17x+5；n=23y+14。

联立两者可得

17x+5 = 23y+14

即

17x-23y = 9

答案为B。

特殊数字整除

根据高斯同余定理，我们很容易得出一些数字的整除规律。在第一部分中我们已经证明过除以3的规律了，其它整除规律的证明与之大同小异。为了能在考试种快速解题，可以熟记下列常见的特殊数字整除规律。

1. 2的倍数特征：个位数字是偶数。

2. 5的倍数特征：个位是0或者5。

3. 3或9的倍数特征：各个数位之和能被3或9整除。

4. 4的倍数特征：末两位数能被4整除。

5. 8的倍数特征：末三位数能被8整除。

6. 25的倍数的特征：末两位数能被25整除。

7. 125的倍数特征：末三位数能被125整除。

例题1

If a six digits 6ab11c is divisible by 8, c =?

(A) 1

(B) 2

(D) 4

(E) 5

解：

8的倍数的特征为“末三位数能被8整除”，112 = 8*14。因此，c = 2，答案为B。

例题2

What is the remainder when the two-digit, positive integer x is divided by 3?

(1) The sum of the digits of x is 5.

(2) The remainder when x is divided by 9 is 5.

(A) Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

(B) Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.

(D) EACH statement ALONE is sufficient.

(E) Statements (1) and (2) TOGETHER are NOT sufficient.

解：

题目问的是，两位数x除以3的余数。

条件1：x的两个数位相加是5。对于除以3来说，很容易证明，两位数除以3的余数和这个两位数的两个数位相加后除以3的余数相等。充分

。

条件2：x除以9的余数为5。x可以写为9k+5，除以3后的余数可以写为：

r(9k+5) = r(9k)+r(5) = r(9)*r(k)+r(5) = 0*r(k)+r(5) = 0+2 = 2。充分。

综上，答案为D。

大数求余

如果问，7除以10的余数是多少？相信大家能一定很快得出答案。但是，如果问，7^548除以10余几？想必大家都需要思考一阵子。这里的7^548就是我们谈到的“大数”。

在“大数求余”类的考题中，高斯同余的乘法定理会被反复使用。方法分为两步：

问：7^548除以10余几？

第一步：

先通过“试数”的方式，寻找7的多少次方除以10余1（原则上，可以通过费马定理求，但GMAT不会涉及很难的数字，所以直接试数即可）。

7^1除以10余7；7^2除以10余9；7^3除以10余3；7^4除以10余1。

因此，找到余1的情况，即，7的4次方，可以写为：

r(7^4) = r(1) (mod 10)

第二步：

等式两端同时乘以自己。

r(7^4)=r(1)

等式左边乘以r(7^4)，右边乘以r(1)，两者一定依然相等，即，

r(7^4) *r(7^4)=r(1) *r(1)

如果在等式左边乘以137个r(7^4)，要想让左右依然想等，则右边需乘137个r(1)，即：

r(7^4)…r(7^4) = r(1) …r(1)

根据高斯同余乘法定理，则有

r(7^4…7^4) = r(1…1)

即

r(7^548) = r(1) = 1

例子中548是恰好能被4整除，如果问7^549除以10余几该怎么办呢？

因为原理上完全相同，所以我们只需在两边继续同时乘以一个r(7)即可。

r(7^548) *r(7)= r(1)*r(7)

r(7^549) = r(7) = 7

例题1

What is the remainder when 3^24 is divided by 5?

(A) 0

(B) 1

(D) 3

(E) 4

解：

第一步：寻找3的多少次方除以5余1。

3^1除以5余3；3^2除以5余4；3^3除以5余2；3^4除以5余1。

第二步：等式两端同时乘以自己。

r(3^4) = r(1)

等式两边同时乘以自己，则有

r(3^24) =r(1)

因此，3的24次方除以5余1。

答案为B。

例题2

If n is a positive integer, what is the remainder when 3^(8n+3) + 2 is divided by 5?

(A) 0

(B) 1

(D) 3

(E) 4

解：

第一步：寻找3的多少次方除以5余1

3^1除以5余3；3^2除以5余4；3^3除以5余2；3^4除以5余1。

第二步：等式两端同时乘以自己。

r(3^4) = r(1)

根据高斯同余乘法定理，在除以5的时候，无论n等于几，r(3^8n)一定是1

r(3^8n) =r(1)

因此

r(3^(8n+3)) =r(3^8n) *r(3^3) = 1* r(3^3) = 1*r(27) = 2

根据高斯同余加法定理

r(3^(8n+3)+2) = r(3^(8n+3))+r(2) = 2+2 = 4

答案为E。

中国剩余定理

中国剩余定理，又叫“孙子定理”，这个名字起源于“韩信点兵”的历史故事。演化到如今的数学题目，变为：

有一个正整数n，这个数除以5余1且除以7余2，问这个数最小是几？

类似这样的考题，我们不必像小学奥数一样用一套“拼凑法”，而是直接试数即可。

我们先寻找到一系列除以7余2的数。最小的除以7余2的数就是2；第二小的是2+7；第三小的是2+7+7，以此类推即可。

这件事可以很容易的用高斯同余加法定理证明得出，假设一个数a除以m余n，则a + km （k是任意非负整数）依然除m余n。

找到这些除7余2的数后，只需从最小的开始判断是否能除5余1即可。

2除5余2；9除5余4；16除5余1。

因此，最小的正整数n为16。基于同余定理可知，任意16 + 35k（k是任意非负整数）均可除以5余1且除以7余2。此处，35刚好是能同时整除5和7的最小的数字（5和7的最小公倍数）。

例题1

When positive integer n is divided by 5, the remainder is 1. When n is divided by 7, the remainder is 3. What is the smallest positive integer k such that k + n is a multiple of 35?

(A) 3

(B) 4

(D) 32

(E) 35

解：

n除以5余1且n除以7余3，我们可以优先确定n的可能性

先寻找到一系列除以7余3的数。最小的除以7余3的数就是3；第二小的是3+7；第三小的是3+7+7。

再寻找这里哪个数可以除以5余1。

3除5余3；10除5余0；17除5余2；24除5余4；31除5余1。

因此，n可以写为31 + 35k（k是任意非负整数）。

题目要求k+n是35的倍数，所以31+k必须是35的倍数。k最小应为4，答案为B。

例题2

When positive integer x is divided by 5, the remainder is 3; and when x is divided by 7, the remainder is 4. When positive integer y is divided by 5, the remainder is 3; and when y is divided by 7, the remainder is 4. If x > y, which of the following must be a factor of x - y?

(A) 12

(B) 15

(D) 28

(E) 35

解：

x和y均可以写为18+35k。由于x大于y，所以x-y必为：

18+35m -18 -35n = 35(m-n) （m>n）

显然地，x-y必然为35的倍数。因此，35一定是x-y的因数，答案为E。

例题3

When positive integer n is divided by 3, the remainder is 2; and when positive integer t is divided by 5, the remainder is 3. What is the remainder when the product n*t is divided by 15?

(1) n - 2 is divisible by 5.

(2) t is divisible by 3.

(A) Statement (1) ALONE is sufficient, but statement (2) alone is not sufficient.

(B) Statement (2) ALONE is sufficient, but statement (1) alone is not sufficient.

(D) EACH statement ALONE is sufficient.

(E) Statements (1) and (2) TOGETHER are NOT sufficient.

解：

依题意，问题问的是n*t除以15的余数。

因此，要想知道问题答案，需要知道n和t的情况。

条件1：n-2能被5整除。这表明n除以5余2。不充分。

条件2：t可以被3整除，这表明t除以3余0。不充分。

条件1加条件2，因为n除以3余2，且n除以5余2，所以根据中国剩余定理，n可以写为2+15k；同理，t可以写为3+15m。此时n*t除以15的余数可以写为：

r(n*t) = r[(2+15k)*(3+15m)] = r(6)+r(30m)+r(45k)+r(225k*m) = 6+0+0+0 = 6

充分。

综上，答案为C。

万年历

实际上，万年历，算闰年，算日子等这类问题都属于余数问题。

首先是关于闰年问题，记住两个计算方式即可：

1. 普通年能被4整除且不能被100整除的为闰年。（如2004年就是闰年,1900年不是闰年）

2. 世纪年能被400整除的是闰年。(如2000年是闰年，1900年不是闰年)

其次是关于推算星期几的问题。例如，假设1989年7月1日是星期三，问1997年7月1日是星期几（也可能问换个日期问等等）。类似这样的问题，计算方式为：

普通年一年365天；闰年一年366天。一周有7天。

365/7余1，因此，每过一个普通年，同一日期的星期需向后推一天。

366/7余2，因此，每过一个闰年，同一日期的星期需向后推两天。

例题1

June 25, 1982, fell on a Friday. On which day of the week did June 25, 1987, fall? (Note: 1984 was a leap year.)

(A) Sunday

(B) Monday

(D) Wednesday

(E) Thursday

解：

1983，1985，1986，1987是普通年，同一日期的星期向后推一天；1984是闰年，同一日期的星期向后推两天，因此，如果1982年6月25日是星期五，则1987年6月25日是星期四（向后加6天）。答案为E。