1、数论中的程序设计 -培训沈云付上海大学计算机工程与科学学院主要内容1. 最大公因数与最小公倍数2. 求整系数一次不定方程 ax+by=c的解3. 求解模线性方程4. 求模 m的逆元素算法5. 模线性方程组与中国剩余定理6. 模取幂运算与素数测试7. 欧拉定理与 费马小定理8. 公钥密码与 RSA7. 实例研究1. 最大公因数与最小公倍数1 公约数和最大公约数的概念2 最大公约数的一种求法 分解因子3 最大公约数性质与欧几里德转辗相除法4 欧几里德转辗相除法5 欧几里德算法实现实例 求最大公因数问题描述：从输入文件中读取一组数据，求最大公因数。输入：输入有若干行。每一行上有两个整数 x， y，是
2、一组测试数据，他们之间用一个空格隔开。输出：对每一组测试数据，每行输出这两个整数的最大公因数。如无最大公因数，则标明 “no GCD”。输出样例：(6,11)=1(0,0) no GCD(5,0)=5输入样例： 6 110 05 01.1 公因数和最大公因数的概念公因数：如果 d是 a的因数并且也是 b的因数，则 d是 a与 b的公因数例： 30的正因数：1， 2， 3， 5， 6， 10， 15、 30；24的正因数： 1， 2， 3， 4， 6， 12， 24；24与 30的正公因数有： 1、 2、 3、 6。1是任意两个整数的公因数；最大公因数：两个不同时为 0的整数 a与 b的最大公因
3、数是其值为最大的公因数，记作 gcd(a, b)。gcd(24, 30) 6。 最大公约数的一种求法 分解因子因为 gcd(a， b) gcd(|a|， |b|)，所以可考虑非负整数的情况。通过求因数，可求 a和 b的素数因子分解：a= ， b=于是整数 a和 b的最大公因数为：gcd(a， b) 最大公因数性质性质：（ 1） gcd(a， b) gcd( a， b)（ 2） gcd(a， b) gcd(a + kb， b)， k为任何整数（ 3） gcd(a， b) gcd(b， a mod b)（ 4）如 a是非零整数，那么 gcd(a， 0) |a| 欧几里德转辗相除法的依据：gcd(a
4、， b) gcd(b， a mod b) 可 求整数 a和 b的最大公因数 1.2 最小公倍数 公倍数：如果 m是 a的倍数并且也是 b的倍数，那么称 m是 a与 b的公倍数。 最小公倍数：两个非零整数 a与 b的最小公倍数是 a与 b的公倍数中数值最小正的数，记作 lcm(a， b)（或简写为 a， b）。 lcm(a， b) lcm(|a|， |b|) 通过 a和 b的标准分解，可以求出整数 a和 b的最小公倍数：lcm(a， b)=最小公倍数与最大公因数关系 1.3 欧儿里德算法 给定任意两个正整数 a和 b gcd(a， b)=结论：求最大公因数的递归程序用欧几里德转辗相除法构造一个求最大公因数的递归程序。输入：非负整数 a、 b返回： a和 b的最大公因数long gcd(long a, long b)long m;if (b=0) if (b=0) return a;else m=gcd(b, a%b);return m;
