神马品牌网电影通往仙境观后感.:数学问题
来源：百度文库 编辑：神马品牌网 时间：2024/05/03 06:38:57
对于r,q,(互质)
在1,q,q^2,q^3....q^r中,至少有2个使q^i恒等于1(modr)
在1,q,q^2,q^3....q^r中,至少有2个使q^i恒等于1(modr)
如果q是素数(质数),那么可以知道 1和q^r mod r都是1
你去百度一下"费尔马小定理",
如果q不是素数,可以证明你的问题,也就是:
1,q,q^2,q^3....q^r中,至少有2个使 q^i≡1(mod r) .
这个"≡"在这里不是恒等于的意思,而是同余,也就是说被r除余1
要证明这个问题,只需要证 q,q^2,q^3....q^r 这r个数里至少有一个被r除余1 .
我们用反证法:
假设: q,q^2,q^3....q^r 这r个数被r除都不余1 .... (1)
那么,一共r个数,而出去1以外,余数只可能是2,3,4,…，r-1
一共r-2个抽屉，根据抽屉原理，q,q^2,q^3....q^r 中至少有其中2个同余，假设这2个数是q^m和a^n，不失一般性，不妨设m>n;
那么必定有q^m-q^n整除r .
也就是说 q^n * ( q^(m-n)-1 ) 整除 r .... (2)
因为显然q和r互质，因此 q^n也和r互质（你简单想想为什么）；
另一方面，因为前面的假设(1)已经假设了q^(m-n)被r除也不会余1，
因此 q^(m-n)-1 不能整除r （这个条件没有互质那么强，两个数可能有大于1的公因式，但是不能整除）
q^n和r互质，q^(m-n)-1 不能整除r
因此q^n * ( q^(m-n)-1 ) 也不能整除 r
这与前面由假设推出的推论(2)相矛盾
因此假设不成立，q,q^2,q^3....q^r 中至少有一个被r除余1 .
证毕