初等数论不定方程.ppt

1、什么是不定方程？ 顾名思义即方程的解不定.一般地有 第二章 不定方程 定义：不定方程是指未知数的个数多于方程 的个数，或未知数受到某种限制(如整数 ， 正整数等）的方程和方程组。 2、主要研究问题 a.不定方程有解的条件 b.有解的情况下，解的个数 c.有解的情况下，如何解 3、本章学习内容 (1）二元一次不定方程 （2）多元一次不定方程 （3）勾股数组 （4)费马大定理简介 (5)几类特殊的不定方程 1 二元一次不定方程 定义：形如 其中 ( )a,b,c为整数的方程称为二元 一次不定方程。 例：2X+3Y=5 5U+6V=21 定理： 有解的充要条件是 (a,b)|c 证：设方程有解 则有 因为（a,b)|a, (a,b)|b ,因而 (a,b)|c 反之，设(a,b)|c,则 由最大公因数 的性质存在s,t 使得as+bt=(a,b) 令 即为方程的解 3、二元一次不定方程有解的情况下解的结构 定理：设 是方程的一组解，则不定方 程有无穷解，其一切解可表示成 其中 证：把 代入不定方程成立，所以 是方程的解。 又设 是不定方程的任一解，又因为 是一特解 则有 ,即有 有 因为 令 即得到了方程的解。 方程有解情况下不定方程的解法 （1）观察法：当a,b的绝对值较小时可直接观 察不定方程的一组特解 ，然后用 得到其所有解。 2、公式法：当a,b的绝对值较小时，可用公 式 得到特解 然后用公式写出一切解。 为a,b作辗转相 除时不完全商(见书) 3、整数分离法：当a,b中系数不同时，用绝对 值较小的系数后的变量表示另一个变量，通 过变量替换得到一个新的不定方程。如此反 复，直到一个参数的系数为1.从而得到不定方 程的解。 4、化为同余方程 （同余方程中再讲） 注:方法(1)(3)(4)用得较多,(2)不太实用. 例1：求解不定方程 解：因为（9，21）=3，3|144所以有解 ； 化简得 考虑 , 有解 所以原方程的特解为 ， 所以方程的解为 注：解的表达式是不惟一的 例2、用整数分离法解 解：因为（107，37）=1，所以有解；故 故 2 多元一次不定方程 2.1定义：形如 的不定方程多元一次不定方程。 2.2 定理 有解 的充要条件是 证：必要性，若不定方程有解 , 则有 由 。 充分性：用数学归纳法 (n=2）时已证 假设对n-1时条件是充分的，令 则方程 有解，设解为 又 有解， 设为 ,这样 就是方程的解。 注：从证明过程也提供了方程的解法。 则 等价于方程组 设 先解最后一个方程的解，得 然后把其代入倒数第二个方程求得一 切解，如此向上重复进行，求 得所有 方程的解。 例1：求不定方程 的整数解. 解 因为（25，13）=1，（1，7）=1|4，所以方程有解 我们将它分为两个二元一次不定方程来求解 25x+13y=t, t+7z=4. 先求t+7z=4的解为t=4-7u，z=u。 因为25*(-1)+13*2= 1，所以25x+13y=1的特解为 = -1 ， =2 故25x+13y=t的解为x=-t-13v，y=2t+25v 所以 的解为 x=-4+7u-13v，y=8-16u+25v， z=u . u，v为整数 。 3 勾股数 定义：一般地称x2+y2=z2的正整数解为勾股数 例（3，4，5），（5，12，13）（8，15,17） 为勾股数 x2+y2=z2 方程解的分析 （1）若x，y，z是方程解，则dx，dy，dz也是 方程解 （2）由（1）只要考虑（x，y，z）=1的解即 可，而实际上只 要（x，y）=1即可，假设（x ，y）=d，则d|x，d|y，则有d|z （3）由（2）可设（x，y）=1，则x，y为 一奇一偶。 若x，y都为奇数，则z为偶数，则方程左边 为4K+2，右边为4K，矛盾。所以x，y为一 奇一偶。 由上分析，我们对（x ,y）作了一些限制， 而这些限制并不影响其一般性。 即可假设在 x0，y0，z0，（x，y）=1， 2x的条件下给出x2+y2=z2的通解公式。 定理：在条件x0，y0，z0，（x，y）=1， 2x的条件下 x2+y2=z2的通解公式为 x=2ab，y=a2-b2，z2=a2+b2， ab0 , (a ,b)=1，a ,b一奇一偶。 为了证明定理的结论，先给出下面引理。 引理：设 u0，v0，（u ,v） =1，则不定 方程 uv=w2 的解为 u=a2，v=b2，w=ab 其中a0，b0，（a ,b）=1。 证：设u，v，w是方程的解，令 不含平方数， 又（u，v）=1， 不能被 整除. 故 所以 u=a2，v=b2，w=ab 。a0，b0，（a ,b）=1 下面进行定理的证明. 定理的证明： x=2ab，y=a2-b2，z2=a2+b2， ab0 , (a ,b)=1，a ,b一奇一偶。显然是方程x2+y2=z2的解 ，满足x0，y0，z0，2x ，且设（x，y）=d，则有 由（a，b）=1，有d=1，或d=2,又由y为奇数，所以d=1。 设x，y，z是满足条件的一组解，由2|x，及（x，y）=1知 y，z是单数，有 且 因为设 则有d|z，d|y，因而有d|x，所以d=1 于是由引理令 于是有x=2ab，y=a2-b2，z2=a2+b2，a0,b0,(a,b)=1 由y0,知ab0 , 又y单，所以a ,b一奇一偶。 推论：单位圆上的有理点可写成 证：由 两边同除 有 ，令 所以有 即为单位圆的方程 而有理点的坐标都是有理数，即为可约分数的形式，分数 的分子正好为x2+y2=z2的x和y分母为z，且正负都可，又可 交换即有 例1：勾股数的勾股中至少有一个是3的倍数。 证：设N=3m 1，（m为整数），则 =3k+1 设 中，若x，y都不是3的倍数， 都是3K+1，则其和为3k+2。不可能 是平方数，所以 是 不可能的。 4 费尔马大定理和无穷递降法 1、费尔马大定理：不定方程 xn+yn=zn ， n3无正整数解。 由于一个大于2的整数n，当n是偶数时，必 为4的倍数或为某个奇质数的偶数倍，当n是 奇数时，必是一个奇质数p的倍数。因此， 实际上只需证明 和 （p为奇质数）都没有正整数解就可以了。 对 可用无穷递降法证明，而 无正整数解的证明是非常困难的。 2、无穷递降法 的逻辑步骤 （1）若一个关于正整数的命题P（n）对若 干正整数n是下正确的，则在所有n中一定 有最小者。 （2）若 正确，则有 使 正确。 由（1）（2），则P（n）不能成立。 例2:证明 是无理数 证：假设 是有理数，则 有正整数解 . 设自然数(a,b)所有解中使得a最小一组解. 即有 容易知道a是偶数，设a=2a1， 代入又得到b为偶数，设 则 ,即 也是方程的解, 这里 这与a的最小性矛盾. 无理数。 例2:证明 是无理数 证：假设 是有理数，则存在自然数a,b使 得满足 ，即 容易知道a是偶数 ，设a=2a1，代入又得到b为偶数，设 ,则 ,这里 这样可以进一步求得a2，b2且有 aba1b1 a2b2 但是自然数无穷递降是不可能的，于是产 生了矛盾， 无理数。 几个特殊的不定方程的初等解法 n1、奇偶分析法 例：求不定方程 的正整数解 解：因为328为偶数，即左边为偶数，x，y的奇偶 性相同，不妨设xy设 则有 同理有 一奇一偶, 则 得解 进一步有 所发原方程的解为(2,18)和(18,2) 2、利用特殊模的余数 例2：证明 无整数解。 证：由求根公式得 原方程要有整数解则 为完全平方 而 所以有 不可能为平方数。 所以原方程无整数解。 3、数与式的分解 n例3：求 的整数解。 解：原方程通过变形得 则有 从而原方程的解为 4、不等分析法 n例4：求 的正整数解。 解：因 所以 又因为 为偶数，所以 只能为4，16 代入得 =16， 所以原方程的解为（4，3） 5、分离整数部分法 例5：求 的整数解。 解：因为x=-1不是方程的解，所以原方程为 所以有x+1|2，即x=0，-2，1，-3得原方 程的解为(0,4),(-2,0),(1,3),(-3,1). 6、求根公式法 例6：求 的整数解。 解：把它看成x的二次方程有 由根号里面大于等于0，得y只能1，2，3 代入得到方程的解为 (2,1),(1,1),(1,2),(3,2),(3,3),(2,3) 7、利用韦达定理 例7：求 的正整数解。 解：把它看成x的二次方程，设根为 则有 所以两根同奇偶，且 除4，余数不为0 所以两根只能是1，3，5和11，9，7 又两根之积减2是平方数。所以 只能是 1，11和3，9。所以原方程的解为(1,3), (11,3),(3,5),(9,5). 8、换元法 例8：求 的正整数解。 解：由题意有 于是令y=tx，则有 由韦达定理得 因为1981=1*1981=7*2