证明题,关于同余式的如果a,b,c是整数,(a,b)=1,那么存在整数n使得(an+b,c)=1求证?
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/25 03:02:22
![证明题,关于同余式的如果a,b,c是整数,(a,b)=1,那么存在整数n使得(an+b,c)=1求证?](/uploads/image/z/12650941-37-1.jpg?t=%E8%AF%81%E6%98%8E%E9%A2%98%2C%E5%85%B3%E4%BA%8E%E5%90%8C%E4%BD%99%E5%BC%8F%E7%9A%84%E5%A6%82%E6%9E%9Ca%2Cb%2Cc%E6%98%AF%E6%95%B4%E6%95%B0%2C%EF%BC%88a%2Cb%EF%BC%89%3D1%2C%E9%82%A3%E4%B9%88%E5%AD%98%E5%9C%A8%E6%95%B4%E6%95%B0n%E4%BD%BF%E5%BE%97%EF%BC%88an%2Bb%2Cc%EF%BC%89%3D1%E6%B1%82%E8%AF%81%3F)
证明题,关于同余式的如果a,b,c是整数,(a,b)=1,那么存在整数n使得(an+b,c)=1求证?
证明题,关于同余式的
如果a,b,c是整数,(a,b)=1,那么存在整数n使得(an+b,c)=1
求证?
证明题,关于同余式的如果a,b,c是整数,(a,b)=1,那么存在整数n使得(an+b,c)=1求证?
如果a,b,c是整数,(a,b)=1,那么存在整数n使得(an+b,c)=1
前言:很惭愧,我足足想了一天,打草稿打了十几张,想了N种思路,还丢失了一支笔,才不小心找到如下的构造性证明
证:
(1)由已知,((a,c),(b,c))=1
于是存在x,y使得 x*(a,c)+y*(b,c)=1 (可以对两边求模(a,c)的余数而得解出y,同理可解出x)
注意取合适的y值,使 (y,c)=1
(2)同余式 bm=(b,c) mod c有解m
这是因为 (b/(b,c),c)=1,故(b/(b,c)) m ==1 mod c有解,从而(2)有解.
于是,x*(a,c)+bmy ==1 mod c
(3)再求解同余式(a,c)==a my *r mod c
注:(1)中,(y,c)=1 ,(2)中,(m,c)=1,又(a/(a,c),c)=1故1==(a/(a,c))my *r mod c有解,从而式(3)有解.
最后可得 x*a myr +bmy ==1 mod c
即 (axr+b) my ==1 mod c
于是取n=xr,(an+b,c)=1
同学
(a,b)=1是什么意思?最大公约数是1,也就是互素(a,b)=1;x,y!=0; a=xb+y(y0;(c-1)/c
全部展开
同学
(a,b)=1是什么意思?
收起