Question

Prove that if gcd(a,b)=d, then gcd(a,a-b)=d.

Answer 1

okay

Answer 2

if d is the gcd of a and b then
a=dm
b=dn

a-b=dm-dn
=d(m-n)

Answer 3

d must also be the biggest divisor of a-b

Answer 4

so it is still the gcd of a and a-b

Answer 5

and a =/= b so m=/=n

Answer 6

thats actually how gcd is found in euclid gcd algofithm !

Answer 7

Yes, but how do you prove that m is coprime to m-n? Am I missing something that is incredibly obvious here?

Answer 8

im not sure what u mean but

Answer 9

if there exists a greater divisior for m-n then d was not the gcd

Answer 10

becaue this higher gcd will also divide a and b

Answer 11

and u can see that by working backwards

Answer 12

actually i retract that statement!! i dunnoo

Answer 13

like suppose m-n became a bigger negative number

Answer 14

then a bigger positive number wud divide m-n but it wont be the divisor of a and b

Answer 15

as it wud be greater than d

Answer 16

if d = gcd(a, b) then we have gcd(a/d, b/d) = 1

so m, n are coprime be definition of gcd itself

Answer 17

```
if d is the gcd of a and b then
a=dm
b=dn

a-b=dm-dn
=d(m-n)
```

here we have started with d = gcd(a,b) and expressed a and b using gcd as :
a = dm
b = dn

all the common factors are in d, there is nothing left common between m and n anymore

Answer 18

im confused try to explain it to me maybe it will help also have some cake

Answer 19

The cake is a lie!

Answer 20

NOOOOOOOOOOO *crys*

Answer 21

let me know if you still need a complete proof
this is a classic, im sure wiki has dozens of proofs for this :)

Answer 22

I still don't understand. If m and n are coprime then what does it tell us about m and m-n?

Answer 23

lets look at `m-n` since thats the new thing

Answer 24

Prove that if gcd(a,b)=d, then gcd(a,a-b)=d
gcd(a,b)=d
ma+nb=d
ma+nb+na-na=d
a(m+n)+n(b-a)=d
a(m+n)-n(a-b)=d
gcd(a,b)=d

Answer 25

i was gonna write what ganesh wrote but changed it when i saw the reply to another proof :P

Answer 26

i like that version of proof, but the OP needs to know that gcd can be expressed as a linear combination first

Answer 27

im sure he know(but sorry cuz i dint mention that XD)

Answer 28

Nope I don't know that. That comes later in my book.

Answer 29

Lets start from scratch, shall we ?

Answer 30

I think a proof by contradiction should proof that m is coprime to m-n but couldn't produce one.

Answer 31

if d = gcd(a, b), then the relations d | a and d | b together imply that d | (a-b)

yes ?

Answer 32

Yes?

Answer 33

for example :

6 = gcd(12, 42), so 6 | (12 - 42)

Answer 34

if \(d = \gcd(a, b)\), then the relations \(d | a\) and \(d | b\) together imply that \(d | (a-b)\)
thus \(d\) is a common divisor of both \(a\) and \(a-b\)

Answer 35

thats almost half of the proof ^
see if that looks okay so far

Answer 36

Yes the part I am having problem with is the maximality of the divisor.

Answer 37

next half deals with that

Answer 38

Next consider some arbitrary common divisor of \(a\) and \(a-b\). Call it \(c\)

\(c | a\) and \(c | (a-b)\) so by the same previous logic, we have \( c | (a -( a-b))\). which is same as \(c | b\).

That means \(c\) is a common divisor of \(a\) and \(b\). Thus it has to be less than or equal to the gcd(a,b) which is \(d\). \(\blacksquare\)

Answer 39

thats the end of proof

Answer 40

we dealt with maximality by showing that ANY common divisor of \(a\) and \(a-b\) has to be less than or equal to \(\gcd(a,b)\)

Answer 41

a=nd
b=md
s.t gcd(n,m)=1
a-b=nd-md=d(n-m)---->d|d(n-m) d|d but d dont divide n-m
thus
d|a-b
(a-b)/d=n-m ---> no other common

idk if this makes it clear XD

Answer 42

That kind of make sense. Something still didn't click though. Give me some time.

Answer 43

\[c | (a-(a-b)) \]
\[c | (a-a+b) \]
\[c |b \]

Answer 44

That make sense. Thanks.