数学难题:若a是非零自然数,n是质数且与a互质,则a^(n-1)-1定能被n整除,试证之.在算术辞典(解题中心)第1749题:与完全数a互质之质数p得整除a^(P-1)-1。其证法简单明了,我的印象其证法没有一楼那样复杂,只可惜这本算术辞典的前面一百六十多页缺失了!

问题描述:

数学难题:若a是非零自然数,n是质数且与a互质,则a^(n-1)-1定能被n整除,试证之.
在算术辞典(解题中心)第1749题:与完全数a互质之质数p得整除a^(P-1)-1。其证法简单明了,我的印象其证法没有一楼那样复杂,只可惜这本算术辞典的前面一百六十多页缺失了!

二者对模P必同余,因此a^(p-1)同余1(否则设a^(p-1)同余1

这个是定理来着,找本书看一下欧拉定理证明过程(fermat-euler定理)。
为了习惯令p=n表示素数
A组取a 2a 3a ...........(p-1)a,它们两两不同余
B组取1 2 3 ..............(p-1),它们两两不同余,
所以A组 B组都是P的既约同余系
A组相乘得a^(p-1)*(p-1)!
B组相乘得 (p-1)!
二者对模P必同余,因此a^(p-1)同余1(否则设a^(p-1)同余1

费马小定理是数论中的一个重要定理,其内容为:假如p是质数,且(a,p)=1,那么 a^(p-1) ≡1(mod p) 假如p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1证明  一、准备知识:  引理1.剩余系定理2   若a...