Question

Let a,b,c be integers such that gcd(a,b)=1,c>0. Prove that there is an integer x such that gcd(a+bx,c)=1

Answer 1

proof by example maybe?

Answer 2

or is this for all c > 0 ?

Answer 3

euler has an algorithm i believe

Answer 4

gcd(a,b); assuming a>b

gcd(12,5) for example since i need to brush up; 12 and 5 are relatively prime .

12 = 5(2) + 2
5 = 2(2) + 1 <-- this remainder gives the gcd,
2 = 2(1) + 0

is there a simpler way to express that?

Answer 5

x = c/gcd(a,c)

should work..

Answer 6

for some a,b

ax + by = gcd(a,b) comes to mind as well ... but i cant recall all the thrms at the moment like others :)

Answer 7

Let \(x = \dfrac{c}{\gcd(a,c)}\) and consdier the expression
\[a+b*\color{blue}{\dfrac{c}{\gcd(a,c)}}\tag{1}\]

Let \(d\gt 1\) be a divisor of \(c\) :
If \(d\mid a\), then clearly \(d \nmid \color{blue}{\dfrac{c}{\gcd(a,c)}}\) and consequently \(d\nmid (1)\).

If \(d\nmid a\), then clearly \(d \mid \color{blue}{\dfrac{c}{\gcd(a,c)}}\) and consequently \(d\nmid (1)\).

That means none of the divisors \(\gt 1\) of \(c\) are common to \((1)\).

That proves \(\gcd\left(a+b*\color{blue}{\dfrac{c}{\gcd(a,c)}},~~c\right)=1\) for all integers \(a,b,c\)

Answer 8

okay i understood . thank you :)

Answer 9

notice that \(\large m+\dfrac{q}{\gcd(m,q)}\) is always coprime to \(\large q\).

Answer 10

okay this is the key concept behind this. Thank you ! :)

Answer 11

yw:)

Answer 12

there is an error in above proof actually

Answer 13

\(\large m+\dfrac{q}{\gcd(m,q)}\) is NOT always coprime to \(\large q\)

for example : \(m=2,~q = 2^5\)

Answer 14

we need to modify the proof :(

Answer 15

I found a proof in stack exchange just now want to check ???

Answer 16

yeah

Answer 17

http://math.stackexchange.com/questions/609810/show-that-if-a-b-and-c-are-integers-such-that-a-b-1-then-there-i/610706#610706

Answer 18

That looks exactly similar to what i am thinking...

Answer 19

http://gyazo.com/fedbba3d2e15be1dae4826da85ff3976

looks neat !

Answer 20

but I didnt understand the second part in the proof.

Answer 21

thats not second part, that a SECOND PROOF.

Answer 22

the snapshot i attached earlier is the complete proof, you're good if that makes sense..

Answer 23

i meant the same. Sorry with the word use :)

Answer 24

are you happy with first proof in that mse link ?

Answer 25

how did induction helped in the second proof ??????????? :((