任意取一个质数,比如13。考虑从1到12的一系列整数1,2,3,4,5,6,7,8,9,10,11,12,给这些数都乘上一个与13互质的数,比如3,得3,6,9,12,15,18,21,24,27,30,33,36。对于模13来说,这些数同余于3,6,9,12,2,5,8,11,1,4,7,10。这些余数实际上就是原来的1,2,3,4,5,6,7,8,9,10,11,12,只是顺序不同而已。
把1,2,3,…,12统统乘起来,乘积就是12的阶乘12!。把3,6,9,…,36也统统乘起来,并且提出公因子3,乘积就是3 12 ×12!。对于模13来说,这两个乘积都同余于1,2,3,…,12系列,尽管顺序不是一一对应,即3 12 x12!≡12!mod 13。两边同时除以12!得3 12 ≡1 mod 13。如果用p代替13,用x代替3,就得到费马小定理x p -1≡1 mod p。

  • 计算2^100除以13的余数
  •