简明信息安全数学基础第一章

一，判断题

5，√
10，√
15，√
20，√
25，√
30，×
35，√
40，×
45，×
50，√

二，单选题

5.A

解：
30965=2*15482+1
15482=2*7741+0
7741=2*3870+1
3870=2*1935+0
1935=2*967+1
967=2*438+1
438=2*241+1
241=2*120+1
120=2*60+0
60=2*30+0
30=2*15+0
15=2*7+1
7=2*3+1
3=2*1+1
1=2*0+1
∴30965的二进制为111100011110101

10.B

解：
107=2*47+13
47=3*13+8
13=1*8+5
8=1*5+3
5=1*3+2
3=1*2+1
2=1*2+0

1=3-1*2
 =3-1*(5-(1*3))
 =2*3-5
 =2*(8-5)-5
 =2*8-3*(13-8)
 =-3*13+5*(47-3*13)
 ...
 =41*47-18*107

 ∴s=41,t=-18

15.C
20.A

三，多选题

5.AD
10.ABC

四，综合题

5.证明：对于任意给定的正整数K，必有K个连续正整数都是合数

解:
令a=(k+1)！
则 2|a+2，3|a+3，···，(k+1)|a+(k+1) 即这a+2到a+(k+1)都是合数
∴ k|a+k (k=2,3,...,(k+1))
所以k个连续正整数都是合数

10.给出判断一个整数是否被一个给定整数整除的算法

解：
if（a%b==0）{cout<<“a能被b整除” }//a为整数,b为给定整数.

(1).

证明：
(a,b)=1,
∴a,b互素
a的因数，a的倍数与b的因数，b的倍数也互素
a^n只有因数1，a的因数，a的倍数
b^n只有因数1，b的因数，b的倍数
∴（a^n,b^n）=1

(2).

证明：
∵a^n|b^n
当n=1时a|n

1.(1613,3589)

解：
3589=2*1613+363
1613=4*363+161
363=2*161+41
161=3*41+38
41=1*38+3
38=12*3+2
3=1*2+1
2=1*2+0

1=3-1*2
=3-1*(38-12*3)
=13*(41-38)-38
=13*41-14*38
=13*41-14*(161-3*41)
=-14*161+55*41
=-14*161+55*(363-2*161)
=-124*161+55*363
=-124*(1613-4*363)+55*363
=-124*1613+551*363
=-124*1613+551*(3589-2*1613)
=-1226*1613+551*3589

∴s=-1226,t=551

2.(2947,3772)

解：
3772=1*2947+825
2947=3*825+472
825=1*472+353
472=1*353+119
353=2*119+115
119=1*115+4
115=28*4+3
4=1*3+1
3=1*3+0

1=4-1*3 
 =4-1*(115-28*4)
 =-115+29*(119-1*115)          
 =29*119+(-30)*(353-2*119)
 =-30*353+89*(472-1*353)  
 =89*472+(-119)*(825-1*472)
 =(-119)*825+208*(2947-3*825)  
 =208*2947+(-743)*(3772-1*2947)
 =951*2947+(-743)*3772   
 
 ∴s=951,t=-743

证明：
∵(a,b)<=a<=[a,b]
  (a,b)<=b<=[a,b]
又∵（a,b)=[a,b]
∴a=b

证明：假设log210是有理数，则存在正整数p, q,使得log210=p/q,且(p,q)=1 
 log210=ln10/ln2=p/q 
 q*ln10=p*ln2     10^q=2^p    
 (2*5)^q=2^p   5^q=2^p-q
所以只有当q=p=0是成立，所以假设不成立             
 故原结论正确，log210是无理数。
 同理可证log37，log1521都是无理数。

625=5^4
2154=2*3*359 
2838=2*3*11*43
3288=2^3*3*137

F1=5
2<=√5  p=2不整除5
F2=17
4<=√17 p=3,2都不整除17
F3=257
16<=√257 p=13,11,7,5,3,2都不整除257
F4=2^16+1
2^8<=√(2^16+1)  p=2,3,5,……，253都不整除2^16+1
∴F1,F2,F3,F4都是素数

40.编写程序计算整数a,b的最大公因数(a,b)，sa+tb=(a,b)求s和t

欧几里得算法：https://www.jianshu.com/p/6a52e3f44f3e

#include<iostream>
using namespace std;
 
int exgcd(int a,int b,int &s,int &t)//扩展欧几里得算法
{
    if(b==0)
    {
        s=1;t=0;
        return a;  //到达递归边界开始向上一层返回
    }
    int r=exgcd(b,a%b,s,t);
    int temp=t;    //把x y变成上一层的
    t=s-(a/b)*t;
    s=temp;
    return r;     //得到a b的最大公因数
}
int main(){
int s,t;
cout<<"最大公因数："<<exgcd(21,14,s,t)<<endl;
cout<<"s="<<s<<endl;
cout<<"t="<<t<<endl;
} 

image.png

41.产生100000以内素数

#include<iostream> 
#include<cmath> 
using namespace std;
    int main(){
        int i,j;
    for( i=2;i<10000;i++){
        for(j=2;j<=sqrt(i);j++)
        if(i%j==0){
        break;
        }
        if(j>sqrt(i))
        cout<<i<<" ";
}
return 0;
}
方法二：
#include<iostream> 
#include<cmath> 
using namespace std;
    int main(){
        int i,j;
    for( i=2;i<10000;i++){
        for(j=2;j<=i;j++)
        if(i%j==0){//不是素数 
        break;
        }
        if(j==i)
        cout<<i<<" ";
}
return 0;
}

image.png

整数因式分解

#include<stdio.h>
int main()
{
        int n,i;
        printf("请输入一个整数:");
        scanf("%d",&n);
        printf("%d=",n);
        for(i=2;i<=n;i++)
        {
                while(n%i==0)
                {
                        printf("%d",i);
                        n/=i;
                        if(n!=1) printf("*");
                }
        }
        printf("\n");
        return 0;
}

image.png

判断素数

#include <stdio.h>
int main(){
    int a = 0;
    int num = 0;
    scanf("%d", &num);
    for (int i=2; i<num-1;i++){
        if (num % i == 0){
            a++;
        }
    }
        if (a==0){
            printf("素数\n");
        }else{
            printf("合数\n");
        }
} 

image.png