arongnet 阅读(1080) 评论(21)

模p运算

给定一个正整数p,任意一个整数n,一定存在等式

          n = kp + r

其中k、r是整数,且 0 ≤ r < p,称呼k为n除以p的商,r为n除以p的余数。

对于正整数p和整数a,b,定义如下运算:

  • 取模运算:a mod p 表示a除以p的余数。
  • 模p加法:(a + b) mod p ,其结果是a+b算术和除以p的余数,也就是说,(a+b) = kp +r,则 (a+b) mod p = r。
  • 模p减法:(a-b) mod p ,其结果是a-b算术差除以p的余数。
  • 模p乘法:(a × b) mod p,其结果是 a × b算术乘法除以p的余数。

可以发现,模p运算和普通的四则运算有很多类似的规律,如:

规律 公式
结合率 ((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p
((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p
交换率 (a + b) mod p = (b+a) mod p
(a × b) mod p = (b × a) mod p
分配率 ((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p

简单的证明其中第一个公式:

 ((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p
 假设
 a = k1 p + r1
 b = k2 p + r2
 c = k3 p + r3
 
 a+b = (k1 + k2) p + (r1 + r2)
 如果(r1 + r2) >= p ,则
    (a+b) mod p = (r1 + r2) -p
 否则
    (a+b) mod p = (r1 + r2)
 再和c进行模p和运算,得到
     结果为  r1 +  r2 +  r3的算术和除以p的余数。
 对右侧进行计算可以得到同样的结果,得证。

模p相等

如果两个数a、b满足a mod p = b mod p,则称他们模p相等,记做

 a ≡ b mod p
可以证明,此时a、b满足 a = kp + b,其中k是某个整数。

对于模p相等和模p乘法来说,有一个和四则运算中迥然不同得规则。在四则运算中,如果c是一个非0整数,则

       ac = bc 可以得出  a =b

但是在模p运算中,这种关系不存在,例如:

 (3 x 3) mod 9 = 0
 (6 x 3) mod 9 = 0
 但是
 3 mod 9 = 3
 6 mod 9 =6

定理(消去律):如果gcd(c,p) = 1 ,则 ac ≡ bc mod p 可以推出 a ≡ b mod p

 证明:
 因为ac ≡ bc mod p
 所以ac = bc + kp,也就是c(a-b) = kp
 因为c和p没有除1以外的公因子,因此上式要成立必须满足下面两个条件中的一个
 1) c能整除k
 2) a = b
 如果2不成立,则c|kp
 因为c和p没有公因子,因此显然c|k,所以k = ck'
 因此c(a-b)kp可以表示为c(a-b) =ck'p
 因此a-b = k'p,得出a ≡ b mod p
 如果a = b,则a ≡ b mod p 显然成立
 得证

欧拉函数

欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数n,小于n且和n互质的正整数的个数,记做:φ(n),其中φ(1)被定义为1,但是并没有任何实质的意义。

定义小于n且和n互质的数构成的集合为Zn,称呼这个集合为n的完全余数集合。

显然,对于素数p,φ(p)= p -1.对于两个素数p、q,他们的乘积n = pq 满足φ(n) =(p-1)(q-1)

        证明:对于质数p,q,满足φ(n) =(p-1)(q-1)
        考虑n的完全余数集Zn = { 1,2,....,pq -1}
        而不和n互质的集合由下面三个集合的并构成:
        1) 能够被p整除的集合{p,2p,3p,....,(q-1)p} 共计q-1个
        2) 能够被q整除的集合{q,2q,3q,....,(p-1)q} 共计p-1个
        3) {0}
        很显然,1、2集合中没有共同的元素,因此Zn中元素个数 = pq - (p-1 + q- 1 + 1) = (p-1)(q-1)

欧拉定理

对于互质的整数a和n,有aφ(n) ≡ 1 mod n

        证明:
        首先证明下面这个命题:
        对于集合Zn={x1,x2,...,xφ(n)},考虑集合
        S = {ax1 mod n,ax2mod n,...,axφ(n)mod n}
        则S = Zn
        1) 由于a,n互质,xi也与n互质,则axi也一定于p互质,因此
        任意xi,axi mod n 必然是Zn的一个元素
        2) 对于Zn中两个元素xi和xj,如果xi ≠ xj
        则axi mod n ≠ axi mod n,这个由a、p互质和消去律可以得出。
        所以,很明显,S=Zn
        
        既然这样,那么
        (ax1 × ax2×...×axφ(n))mod n
         = (ax1 mod n × ax2mod n × ... × axφ(n)mod n)mod n
         = (x1 × x2 × ... × xφ(n))mod n
         考虑上面等式左边和右边
         左边等于(aφ(n) × (x1 × x2 × ... × xφ(n))mod n) mod n
         右边等于x1 × x2 × ... × xφ(n))mod n
         而x1 × x2 × ... × xφ(n))mod n和p互质
         根据消去律,可以从等式两边约去,就得到:
         aφ(n) ≡ 1 mod n
推论:对于互质的数a、n,满足aφ(n)+1 ≡ a mod n

费马定理

a是不能被质数p整除的正整数,则有ap-1 ≡ 1 mod p

证明这个定理非常简单,由于φ(p) = p-1,代入欧拉定理即可证明。

同样有推论:对于不能被质数p整除的正整数a,有ap ≡ a mod p


评论列表
LoveSong
re: 质数初步
好东西,收藏
Jasper
re: 质数初步
确实不错。
watchmoon
re: 质数初步
我有疑意,欧拉定理的证明,是建立在“无限”情况下的一种“理想”基础上的。由于无法确定“无限”情况的定义,所以欧拉定理必然产生概率分布问题。
事实上,欧拉所研究的数学并不完全包含可信性。如欧拉几何就被后人在实践中发现不足。但仍有一定推导价值。
re: 质数初步
这属于高中内容,还是大学内容啊
Z
re: 质数初步
有没有欧拉函数的公式和证明?
路人tourist
re: 质数初步
感觉楼主象是教数论的……
:)
yangyin
re: 质数初步
但如果当q==p时,好像有点问题
some pigs
re: 质数初步
  你可否举1个18位数看看!
xinz
re: 质数初步
清晰明了,谢谢楼主
QQ345780531
re: 质数初步
呵呵
好象中间有错误哦
楼主打字的时候不小心哦
QQ:284642340
re: 质数初步
o
证明:对于质数p,q,满足φ(n) =(p-1)(q-1)
        考虑n的完全余数集Zn = { 1,2,....,pq -1}
        而不和n互质的集合由下面三个集合的并构成:
        1) 能够被p整除的集合{p,2p,3p,....,(q-1)p} 共计q-1个
        2) 能够被q整除的集合{q,2q,3q,....,(p-1)q} 共计p-1个
        3) {0}
        很显然,1、2集合中没有共同的元素,因此Zn中元素个数 = pq - (p-1 + q- 1 + 1) = (p-1)(q-1)

我想以上证明中存在着问题:
 考虑n的完全余数集Zn = { 1,2,....,pq -1}
这句话中,显然0是不包括在ZN内的,且完全余数总个数是pq-1个.所以:
 3) {0}
是多余的.所以:
 很显然,1、2集合中没有共同的元素,因此Zn中元素个数 = pq - (p-1 + q- 1 + 1) = (p-1)(q-1)
这句话应写为:
很显然,1、2集合中没有共同的元素,因此Zn中元素个数 = pq-1-(p-1 + q- 1 ) = (p-1)(q-1)
lrt
re: 质数初步
你是对的,呵呵
re一下
偶尔过来
大家相互帮助
007
re: 质数初步
108=8(mod100)-8=92(mod100)  怎么算的?
lyb
re: 质数初步
大家研究过被一个质数整除的整数问题吗?我是一个中学教师,得了一个结论,也给出了严格证明,但文章发表不出.请联系rylyb01@126.com
彧彧
re: 质数初步
re: 质数初步 2007-03-07 14:04 007 
108=8(mod100)-8=92(mod100)  怎么算的? 

a=b(mod m)   <=>    m|(a-b)
luguo
re: 质数初步
定义小于n且和n互质的数构成的集合为Zn,称呼这个集合为n的完全余数集合。

小于n且和n互质的数构成的集合是n的余数化简集合。
安定法
re: 质数初步
总算了解了 ‘ ≡  ’运算符在这种公式中的意义了。原本还纳闷:怎么这 也能恒等呀 ap-1 ≡ 1 mod p 。
还有
2 | Φ(n)  中的 |   符号是不是说 2能整除 Φ(n) 呀。
这数论太高深了,光几个符号就叫俺大打退堂鼓了。
感谢 作者!

发表评论
切换编辑模式