[求助]Elementary number theory --- gcd

HJin 发布于 2007-06-21 08:42， 1040 次点击

I have two natural numbers M and N, M>N, and gcd(M, N) = 1. I want to find integers x and y such that

x*M + y*N = 1.

Can you give me x and y in terms of M and N; i.e., express x or y as a function of M and N.

Thanks,

HJin

10 回复

tobyliying2007-06-21 10:47

gcd(M,N)=1
是什么意思

HJin2007-06-21 10:52

gcd = greatest common divisor

For example,

gcd(4,8) = 4;
gcd(5, 16)=1.

aipb20072007-06-21 11:58

gcd = great common divisor(最大公约数)

这个问题似乎是个数学问题哦！有点复杂，我觉得可能要用到某些数学方程解.
关注下！

tobyliying2007-06-21 11:58

fun(int M,int N)
{
int x,y;
for(int i=-M;i<M;i++)
{
for(int j=-M;j<M;j++)
{
x=i;
y=j;
if((x*M+y*N)==1)
{
cout<<"x:"<<x<<endl;
cout<<"y:"<<y<<endl;
}
}
}
}
main()
{
int M,N;
while(gcd(M,N)!=1||M<=N)
{
cin>>M>>N;
}
fun(M,N);
}
　我是这样做的

tobyliying2007-06-21 11:59

用数学方法　我还没有想出来

aipb20072007-06-21 12:01

LS的
那个x.y的范围怎么就确认到 -M -- M -N -- N啊？
有依据吗？

[此贴子已经被作者于2007-6-21 12:02:39编辑过]

tobyliying2007-06-21 14:29

这道题我想错了。. 对不起。.
这个方程的解是个解集

HJin2007-06-21 14:40

Mathematics theory says that there exist x and y s.t.

x*M + y*N =1 if gcd(M, N)=1.

And I suspect that there are acutually infinitely many solutions for x and y.

You do not need to find all of them. I only want one of them, preferably expressed in terms of M and N.

Thanks.

#10

tobyliying2007-06-21 14:46

我睡了一觉后就想通了.

其中 M必然为奇数, N必然为偶数;

n为正整数,
当M=3 ,N=2时 x=1+2n, y=-(1+3n);
当M=5,N=4时 x=1+4n,y=-(1+5n);

就可以依次类推.
我相信可以写出相应的算法

#11

tobyliying2007-06-21 14:48

我上体育课去了。回来在说怎么写这个FUNCTION 怎么写