一，判断题

5，×
10，√
15，×
20，√
25，√
30，×
35，×

二，单选题

5.D
10.D
15.B
27.B

四，综合题

a1≡b1 (mod m),a2≡b2 (mod m)
a1+a2≡b1+b2 (mod m)
∴a1+a2+...+ak≡b1+b2+...+bk (mod m)
a1≡b1 (mod m),a2≡b2 (mod m)
a1*a2≡b1*b2 (mod m)
∴a1*a2*...*ak≡b1*b2*...*bk (mod m)

（1）2^32 (mod47)
2^32=2^32
2^1≡2 (mod47)
2^2≡4 (mod47)
2^4≡16 (mod47)
2^8≡16^2≡21 (mod47)
2^16≡21^2≡18 (mod47)
2^32≡18^2≡42 (mod47)
∴2^32≡42 (mod47)

（2）2^47（mod47）
2^46≡1（mod 47）
2^47≡2^46*2≡1*2(mod 47)

2^47=2^32*2^8*2^4*2^2*2
2^32=2^32
2^1≡2 (mod47)
2^2≡4 (mod47)
2^4≡16 (mod47)
2^8≡16^2≡21 (mod47)
2^16≡21^2≡18 (mod47)
2^32≡18^2≡42 (mod47)
2^47≡42*21*16*4*2≡2（mod47）
∴2^47≡2（mod47）

（3）2^200（mod47）
∵2^46≡1 （mod 47）
200=46*4+16
2^200=2^(46*4)*2^16
2^200≡1^4*2^16（mod47）
2^16≡18（mod47）

（1）1843581
1+8+4+3+5+8+1=30
3|30，9不整除30
∴3整除1843581

（2）184234081
1+8+4+2+3+4+0+8+1=31
3和9都不整除31
∴3和9都不整除184234081

（3）8937752744
8+9+3+7+7+5+2+7+4+4=56
3|56,9|56
∴3和9都不能整除8937752744

（4）4153768912246
4+1+5+3+7+6+8+9+1+2+2+4+6=58
3|58,9|58
∴3和9都不能整除4153768912246

编程题

1.编程输出n的Euler函数值φ(n)

image.png

#include<iostream>
#include<cmath>
using namespace std;
int euler(int n)
{    
    int ans=n;    
    for(int i=2;i<=sqrt(n);i++)//2~ √n 求素因子 
    {  
        if(n%i==0)// 求素因子
        {  
        ans=ans/i*(i-1); ///通项公式求解欧拉函数值 
        while(n%i==0) // 每个素因子只计算一次
        n/=i;  
        }  
    }  
       if(n>1) ans=ans/n*(n-1);  //当n为素数时 
       return ans;  
 } 
int main()
{
  int n;
    while(cin>>n)///测试
    {
        cout<<euler(n)<<endl;
    }
    return 0;
} 

2.编程实现模重复平方运算（求b^n (mod m)）

image.png

方法一：非递归（模幂算法）

#include<iostream>
#include<cmath>
using namespace std;
int euler(int n)//求n的欧拉值 
{    
    int ans=n;    
    for(int i=2;i<=sqrt(n);i++)//2~ √n 求素因子 
    {  
        if(n%i==0)// 求素因子
        {  
        ans=ans/i*(i-1); ///通项公式求解欧拉函数值 
        while(n%i==0) // 每个素因子只计算一次
        n/=i;  
        }  
    }  
       if(n>1) ans=ans/n*(n-1);  //当n为素数时 
       return ans;  
 } 
int powerMod(int b,int n,int m){//模平方算法 
    int r;
    r=n%euler(m);   
    n=r;
    int a=1;//存放计算结果，初始化为1
    int i,k=0,num=n;
    while(num){//计算指数二进制位数k 
        num=num>>1;//将num右移1位（也即除以2），然后再将结果赋值给num.等同 num=num/2;
        ++k;//num的二进制右移一位 
    }
     for(i=0;i<k;i++){
        if((n>>i)&1)//取二进制的第i位，然后和1进行与运算（判断i位是否为1） 
          {a=a*b%m;}//二进制位为1时操作 
           b=b*b%m;// 二进制位为1和0时操作 
     }
    return a;
}

int main(){
    int b,n,m;  
    cout<<"请分别输入底数b,指数n,模m：";
    cin>>b>>n>>m;
    cout<<"b^n(mod m)="<<powerMod(b,n,m);
    return 0;
} 

image.png

方法二：递归

递归公式： b^n(mod m)=b* (b^(n-1) (mod m)) (mod m)

#include<iostream>
using namespace std;
int powerMod(int b,int n,int m){ //递归公式： b^n(mod m)=b* (b^(n-1) (mod m)) (mod m)
    if(0==n)
    return 1;
    return b*powerMod(b,n-1,m)%m;
}

int main(){
    int b,n,m;
    cout<<"请分别输入底数b,指数n,模m：";
    cin>>b>>n>>m;
    cout<<"b^n(mod m)="<<powerMod(b,n,m);
    return 0;
} 

image.png