首页 > 其他 > 详细

有关贝祖定理的一个小问题

时间:2014-07-13 15:27:30      阅读:434      评论:0      收藏:0      [点我收藏+]

有关贝祖定理的一个小问题

 

所谓贝祖定理是说:

两个整数 a是互质的,等价于方程 ax+by=1有整数解。

当然, 贝祖定理还有一种更一般的形式,说的是两个整数 ab有最大公因数是c,等价于方程 ax+by=c有整数解。

这两种表述其实是等价的,因为对第二种形式稍微一变形就得到了:

bubuko.com,布布扣

所以我们只需要考虑第一种形式的贝祖定理就可以了。

贝祖定理的证明

贝祖定理的证明并不复杂,不过因为无论是中学还是大学(除了数学专业)都很少讨论这类跟数论相关的问题,所以可能有些人会感觉这个问题有些无从下手。

这里先给个贝祖定理的简单证明。

 

首先,非常容易就可以证明a如果不互质,那么 ax+by=1无整数解。因此我们只需要考虑a是互质的这种情况。

 bubuko.com,布布扣

xy取不同整数值时,ax+by 也会有不同的结果,这些结果中最小的那个正整数设为s,也就是

ax+by=s

a整除的商为q,余数为r,也就是

 bubuko.com,布布扣

那么

bubuko.com,布布扣

如果 不等于0就与我们假设sax+by这个集合的最小的正整数矛盾了。所以r只能等于0,也就是说a可以整除s。同理也可以证明b可以整除s,这说明sab的公约数,而我们知道ab是互质的,所以s只能等于1,这就证明了贝祖定理。

 

xy的计算

如何计算xy的值是另一个问题,当然我们知道xy有无数多组整数解,我们只需要求出一组解就够了。

不失一般性,我们设 a > ba = bq+r

 bubuko.com,布布扣

 可以看到,我们将 ax+by=1转化为 ax+by‘=1其中da要小,这个过程可以一直重复,直到其中一个整数等于1。方程变类似形式:

ex+y=1

这时只要让x=0y=1 就可以了。然后一步步回带,就能求得最初的xy了。这是一个典型的递归的过程。

 下面给个C语言实现的代码,代码比较简单,就没有添加注释:

bool Bezout(int a, int b, int *px, int *py)
{
    int q, r;
    int x, y;
    bool ok;
    if( a == 1 )
    {
        *px = 1;
        *py = 0;
        return true;
    }
    if( b == 1 )
    {
        *px = 0;
        *py = 1;
        return true;
    }

    if( a >= b )
    {
        q = a / b;
        r = a % b;
        if ( r == 0 )
        {
            return false;
        }
        ok = Bezout(r, b, &x, &y);
        if( ok )
        {
            *px = x;
            *py = y - q * x;
        }
        return ok;
    }
    else
    {
        q = b / a;
        r = b % a;
        if ( r == 0 )
        {
            return false;
        }
        ok = Bezout(a, r, &x, &y);
        if( ok )
        {
            *py = y;
            *px = x - q * y;
        }
        return ok;
    }
    return true;
}

这里是测试用例:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool Bezout(int a, int b, int *px, int *py);
int main()
{
    int x, y;
    int a = 73;
    int b = 32;
    bool ok;

    ok = Bezout(a, b, &x, &y);
    if(ok)
    {
        printf("%d * %d + %d * %d = %d, is ok\n", a, x, b, y, a * x + b * y);
    }

    return 0;
}


有关贝祖定理的一个小问题,布布扣,bubuko.com

有关贝祖定理的一个小问题

原文:http://blog.csdn.net/liyuanbhu/article/details/37729751

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!