费马小定理

费马小定理是数论中的一个定理：假如a是一个整数，p是一个质数，那么

是p的倍数，可以表示为

如果a不是p的倍数，这个定理也可以写成(同余式写法)

同余式

如果两个正整数 a和 b之差能被 n整除，那么我们就说 a和 b对模n同余，记作：

证明

任意取一个质数，比如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×12！≡12！mod 13。两边同时除以12！得312≡1 mod 13。如果用p代替13，用x代替3，就得到费马小定理xp－1≡1 mod p。

应用

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

2^100除以13的余数

• 证明对于任意整数a而言
  
  
  恒为2730的倍数。13减1为12，12的正因数有1, 2, 3, 4, 6, 12，分别加1，为2, 3, 4, 5, 7, 13，其中2, 3, 5, 7, 13为质数，
  根据定理，
  
  
  为2的倍数、为3的倍数、为5的倍数、为7的倍数、为13的倍数，即235713=2730的倍数。

Ignatius's puzzle

题目链接

代码实现

#include<iostream>
using namespace std;
int main(){
    int k,i,a;
    while(cin>>k){
        for(int i=1;i<66;i++){
            if(i*k%13==8&&i*k%5==2){
                a=i;
                break;
            }else{
                a=0;
            }
        }
        if(a){
                cout<<a<<endl;
            }else{
                cout<<"no"<<endl;
        }
    }
    return 0;
}

运行结果

运行结果

参考：

Ignatius's puzzle

费马小定理

费马小定理-维基百科

杭电1098Ignatius's puzzle