同余（八）——欧拉定理

往期文章

同余（一）

同余（二）

同余（三）

同余（四）—书籍书号的小秘密

同余（五）——费马小定理

同余（六）——斐波那契数列

同余（七）——密码学中的应用

整数与整除问题  

导读

   之前我们已经介绍了费马小定理，

  若p是一个不能整除整数a的素数，则

              a^p-1≡1（mod p）

费马本人并没有给出证明，幸好有欧拉，他研究费马提出的很多问题。在1960年，欧拉证明了一个更强的结果，被后人称为欧拉定理。

欧拉函数

      欧拉函数φ(n)是定义在正整数n上的函数，它的取值是小于或等于n的正整数中与n互素的数的个数。

      例如，φ(1)=φ(1)=1，φ(3)=2。

欧拉定理

定理  设m是任意大于1的整数，（a,m）=1,则

              a^φ(m)≡1（mod m）.

证明  

                                                    □

      显然有欧拉定理可以直接推导出费马小定理（因为φ(p)=p-1）,由费马小定理也可以推出欧拉定理，请读者思考如何证明。

      1909年，德国数学家维夫瑞奇提出是否存在素数p,满足

               2^p-1≡1（mod p²）

       这样的素数被称为维夫瑞奇素数，但是至今在不超过6.7×10¹⁵的数中只发现了1093和3511。