Question

\(d = ax + by\)

\(d\) is the smallest whole number; does this mean \(d = \gcd(a, b) = \gcd(x, y)\) ?

Answer 1

i was looking at gcd(a, b) proof and got stuck on this doubt...

Answer 2

means there is unique d s.t
d=ax+by

Answer 3

yes is \(d\) also the gcd of \(x\) and \(y\) ?

Answer 4

nope its not

Answer 5

I thought so, but if d is smallest whole number then it has to be the gcd right ?

Answer 6

lets prove it ^

Answer 7

okay..

Answer 8

Counterexample
gcd(14,10)=2
3(10)-14(2)=2
gcd(3,2)=1 not 2

Answer 9

it has to be GCD of a,b
since function u have is

s:={ au+bv | s.t au+bv \(\in N\)}

Answer 10

exactly :)
@myininaya

Answer 11

oh we cannot swap (a, b) and (x, y) is it, its still hard to see..

Answer 12

well if u swap x,y
then u need to swap the wole proof as well
and they would be other d1=gcd(x,y)
s.t

\(d_1\) = mx+ny

Answer 13

I see... the counter example clears up everything xD thank you both for quick help !

Answer 14

np :)

Answer 15

also -11(10)+8(14)=2
but gcd(10,14)=2 and gcd(-11,8)=gcd(11,8)=1
i wonder if we can find two numbers a,b so that 10a+14b=2
and gcd(a,b) is not equal to 1
so far I can only find gcd(a,b) is 1

Answer 16

d = ax+by can have multiple representations is it ?

Answer 17

-11(10)+8(14)=2

i feel (-11, 8) is the unique solution for 10x + 14y = 2

just a guess, i may be very wrong...

Answer 18

my bad !

10x + 14y = 2 is a diaphontine equation, it can have infinite solutions

Answer 19

yeah one solution i wrote as (3,-2) earlier

Answer 20

its a condition that gcd(x,y)=1
disrigarding d value

Answer 21

i only need to make sure of that mm
not sure yet

Answer 22

since (3, -2) is one solution, all other solutions can be given by :

x = 3 + 7t
y = -2 - 5t

Answer 23

that means gcd(3+7t, -2-5t) is always 1 for all values of t @ikram002p ?

Answer 24

i think so

Answer 25

right thanks
for some reason i was having a brain fart on how to find that
so gcd(x,y)=gcd(3+7t,-2-5t)
This might equal 1
I'm just wondering if for all x,y will the gcd(x,y)=1 where the 10x+14y=2.
so gcd(3+7t,-2-5t)
=gcd(3+7t,1+2t)
=gcd(-t,1+2t)
=gcd(t+1,1+2t)
=gcd(t+1,t)
=1
for all t

Answer 26

you know since no two consecutive integers will have a common factor

Answer 27

nice !

Answer 28

@ganeshie8 you rivewing Burton book ?
there is a collary after thm 2.3 check it

Answer 29

I think I made a mistake up there
gcd(3+7t,-2-5t)
=gcd(3+7t,1+2t)
=gcd(t,1+2t) <--not -t but putting -t or t I don't think should actually matter
=gcd(t,1)
=1 for all t

Answer 30

wow! this looks interesting xD

you're talking about this ikram ?
http://prntscr.com/40fm9c

Answer 31

yep ..
that make me really think for any x,y
gcd(x,y)=1

ax+by=d
then
a(mg)+b(mh)=d
ag+bh=d/m
then d wont be the least whol number according to WOP

Answer 32

another way to see gcd(x, y) has to be 1 is :

ax + by = gcd(a, b)

dividing both sides by gcd(a, b) gives :
px + qy = 1

where p, q are coprime, So gcd(x, y) = 1

Answer 33

http://www.saylor.org/site/wp-content/uploads/2013/05/An-Introductory-in-Elementary-Number-Theory.pdf
like theorem 8 on page 21 of this pdf

Answer 34

that is what i was using above

Answer 35

ok yeah @ganeshie8

Answer 36

that is probably easier

Answer 37

cool

Answer 38

@ganeshie8 mmm
why x,y are coprime
when
ax+by =1 ?

Answer 39

Recall :
a = bc
=> b|a and c|a

Answer 40

px+qy = 1
if x,y are NOT coprime, then you can factor out gcd(x,y)
then this gcd has to divide 1 which is impossible.

Answer 41

aha nice :)