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

费马小定理

      在17世纪，“业余”数学家费马（本职律师）发现了一个非常重要的定理：

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

              a^p-1≡1（mod p）.

也就是说a的（p-1）次幂被p除后余1，

              a^p-1÷p=q…1.

      我们来验证2个例子

例子1     10¹⁰≡1（mod 11）

已知

             10≡-1（mod 11）

利用同余性质可知

             10²≡1（mod 11）

             10⁴≡1（mod 11）

              10⁸≡ 1（mod 11）

              10¹⁰≡1（mod 11）.

例子2     5¹⁰≡1（mod 11）

利用同余性质可知

             5²≡3（mod 11）

             5⁴≡9（mod 11）

             5⁸≡4（mod 11）

             5¹⁰≡1（mod 11）

       费马本人并未给出定理的证明，其他数学家给出了证明，我们来看一看

费马小定理

定理  若p是任意一个不能整除整数a的素数，则

              a^p-1≡1（mod p）.

证明  

                                                    □

费马小定理的应用

问题      2¹⁰⁰的除以13的余数？

            2¹⁰⁰≡  2^12×8+4（mod 13）

            2¹⁰⁰≡（2¹²）⁸·2⁴（mod 13）

            2¹⁰⁰≡（1）⁸·16（mod 13）

            2¹⁰⁰≡  16（mod 13）

            2¹⁰⁰≡   3（mod 13）

故余数为3。