D。
87=3(mod 7)
36=729=1(mod 7)
所以87100=3100=(36)16*34=1*81=4(mod
7)
发表于 2015-01-04 21:50:57
回复(1)
同余：如果两个数a,b除以一个数m的余数相同，就说a和b对模数m同余,记为`a≡b(mod m)`
。例子：比如16-10=6能够被3整除，16和10对3同余(余数都是1)
同余的等价性：即同余满足3个性质：
(1)自反性：设a对m的余数为k，显然a和a对m的余数相同，都为k，由定义可知a和a同余，即具有自反性
(2)对称性和(3)由定义也容易证明
性质(1):如果：`a≡b(mod m)` 且`x≡y(mod m)` ,那么`a+x≡b+y(mod m)`
证明：由同余的条件我们可知，存在p和q是的a-mp=b-mq,也存在s,t使得x-mr=y=ms.于是：a-mp+x-mr=b-mq+y-ms,即：a+x-m(p+r)=b+y-m(r+s).可知同余
性质(2):如果`a≡b(mod m)` ，`x≡y(mod m)` ，则`ax≡by(mod m)` 。
性质(3):`(a + b)%m = (a%m + b%m)%m`
证明：存在s,t使得：a%m+b%m = a-sm+b-tm,故(a%m + b%m)%m=(a+b-m(s+t))%m=(a+b)%m -(m(s+t))%m=(a+b)%m
性质(4):`(a * b)%m = ((a%m)*(b%m))%m`
存在s,t使得：a%m * b%m = (a-ms)*(b-mt)=ab - m(as + bt).
故(a%m + b%m) % m = (ab - m(as + bt)) % m = ab % m
性质(5):`a^b%m = ((a%m)^b)%m`
由性质(4)归纳可得
因此：
```
87^100 % 7 = (87%7)^100 % 7 = 3^100 % 7 = (9^50) % 7 =
(9%7)^50 % 7 = 2^50 % 7 = (4 * 8^12) % 7 =
(4%7 * 8^12 % 7) % 7 = 4 % 7 = 4
```
同余的等价性：即同余满足3个性质：
- 自反性：自己和自己同余
- 对称性：a和b同余，b和a也同余
- 传递性：a和b同余，b和c同余，那么a和c也同余。
(1)自反性：设a对m的余数为k，显然a和a对m的余数相同，都为k，由定义可知a和a同余，即具有自反性
(2)对称性和(3)由定义也容易证明
性质(1):如果：`a≡b(mod m)` 且`x≡y(mod m)` ,那么`a+x≡b+y(mod m)`
证明：由同余的条件我们可知，存在p和q是的a-mp=b-mq,也存在s,t使得x-mr=y=ms.于是：a-mp+x-mr=b-mq+y-ms,即：a+x-m(p+r)=b+y-m(r+s).可知同余
性质(2):如果`a≡b(mod m)` ，`x≡y(mod m)` ，则`ax≡by(mod m)` 。
性质(3):`(a + b)%m = (a%m + b%m)%m`
证明：存在s,t使得：a%m+b%m = a-sm+b-tm,故(a%m + b%m)%m=(a+b-m(s+t))%m=(a+b)%m -(m(s+t))%m=(a+b)%m
性质(4):`(a * b)%m = ((a%m)*(b%m))%m`
存在s,t使得：a%m * b%m = (a-ms)*(b-mt)=ab - m(as + bt).
故(a%m + b%m) % m = (ab - m(as + bt)) % m = ab % m
性质(5):`a^b%m = ((a%m)^b)%m`
由性质(4)归纳可得
因此：
```
87^100 % 7 = (87%7)^100 % 7 = 3^100 % 7 = (9^50) % 7 =
(9%7)^50 % 7 = 2^50 % 7 = (4 * 8^12) % 7 =
(4%7 * 8^12 % 7) % 7 = 4 % 7 = 4
```
发表于 2016-12-07 10:45:45
回复(2)
公式 (A*B)%C = (A%C)*(B%C)
所以 87 % 7 = 3
87^2 % 7 = 9 % 7 = 2
87^3 % 7 = 6 % 7 = 6
87^4 % 7 = 18 % 7 = 4
87^5 % 7 = 12 % 7 = 5
87^6 % 7 = 15 % 7 = 1
87^7 % 7 = 3 % 7 = 3.........
发表于 2015-07-29 16:35:12
回复(2)
其实想用普通数学知识理解的话就是将87不断拆多项式87100=（80+7）100，每一次提取除不开7的地方，第一次转化为80100，继续分分分也可以变成32/7
发表于 2023-08-14 23:43:58
回复(0)
原理：
1. (A*B)%C = (A%C)*(B%C)%C
2.
A
n
%C=((A-A%C)+A%C)
n
%C=(
A%C)
n
%C
发表于 2016-06-03 19:18:47
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
