证明题,关于同余式的如果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求证?
如果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是什么意思？

收起