网络空间安全数学基础部分证明，筛法、贝祖等式的编程实现。

证明：如果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;               } }