技術文章 » 網路空間安全數學基礎部分證明，篩法、貝祖等式的程式設計實現。

網路空間安全數學基礎部分證明，篩法、貝祖等式的程式設計實現。

2020-10-22 11:00:01

  • 證明：如果a是整數，a3-a被3整除

證：令a=3k，則3|3(3k-1)(3k+1)

令a=3k+1，則3|3(3k+1)(3k+2)

令a=3k+2，則3|(3k+1)(3k+2) (3k+3)=3(k+1) (3k+1)(3k+2)，

得證。

  • 證明：任意連續三個整數的乘積都被6整除

證：結合上題，

令a=6k，則6|6(6k-1)(6k+1)

令a=6k+1，則6|6(6k+1)(6k+2)

令a=6k+2，則6|(6k+1)(6k+2) (6k+3)=6(6k+1) (3k+1)(2k+1)，

得證。

  • 證明：對任意正整數k，必有k個連續正整數都是合數

證：令M=(k+1)!，則M+2，M+3，…，M+(k+1)一共k個數都是合數。

∵2|M，3|M，…，k+1|M

∴2|M+2，3|M+3，…，k+1|M+(k+1)

得證。

  • 用篩法求解500以內的全部素數

解答：使用C語言進行程式設計求解

程式碼：

#include "stdio.h"
#include "string.h"
#include "math.h"

void main(){    
    int i,j,a,b;
    for(j=500;j>1;j--){
        for(i=2;i<=(int)sqrt(500);i++){
            if(j%i==0&&j!=i)
                b=j;  
        }
        if(j!=b) printf("%d\t",j);
   }  
   printf("\n");
}

執行結果：

499 491 487 479 467 463 461 457 449 443 439 433 431 421 419 409 401 397 389 383 379 373 367 359 353 349 347 337 331 317 313 311 307 293 283 281 277 271 269 263 257 251 241 239 233 229 227 223 211 199 197 193 191 181 179 173 167 163 157 151 149 139 137 131 127 113 109 107 103 101 97   89 83   79   73   71   67   61   59   53   47   43   41   37   31   29   23   19   17   13  11   7     5     3     2    

 

  • 證明：形如4K+3的素數有無窮多個

證：反證法，假設只有有限個，設為n個，分別是

其中p1 =3，最小。則，是4k+3型的整數,

∵都不能整除p，2不能整除p

∴p的質因數分解只能是4k+1型素數，

又∵4k+1型整數乘積仍然是4k+1型整數，不可能等於4k+3型整數

∴p本身是素數，但p和p1~pn都不相等，

即找到了第n+1個4k+3型素數，與原假設矛盾

得證。

 

  • 貝祖等式及其程式設計實現

貝祖等式：

       設a，b是任意兩個正整數，則存在整數s，t使得 s*a+t*b=(a,b)

程式設計實現（Java）：      

public class BezoutsIdentity {
              static long s;
              static long t;
              public static void main(String[] args) {
                     get_s_t(7,12);
                     System.out.println(Main.s+" "+Main.t);
              }
              public static long get_s_t(long a,long b){
                     long d=get_gcd(a,b);
                     long n=1;
                     s=s*n;
                     t=t*n;
                     return d;
              }
              public static long get_gcd(long a,long b){         //greatest Common Divisor求最大公因數
                     if (b==0) {
                            s=1;
                            t=0;
                            return a;
                     }
                     long gcd=get_gcd(b,a%b);
                     long s1=s;
                     s=t;
                     t=s1-(a/b)*t;
                     return gcd;
              }
}