hdu-1098 Ignatius's puzzle（费马小定理）费马小定理同余式证明应用Ignatius's puzzle运行结果

费马小定理

费马小定理是数论中的一个定理：假如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，乘积就是312×12！。对于模13来说，这两个乘积都同余于1,2,3,…,12系列，尽管顺序不是一一对应，即312×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