Question

NT review
http://prntscr.com/3yxumh

Answer 1

the proof starts with asserting the fact that the set
\[S = \{au+bv~ | ~au + bv > 0 \}\]

is nonempty

Answer 2

trying to proof euclidean algorithm ^^

Answer 3

that comes later,
this is a only an existence proof

Answer 4

prove that \(\gcd (a, b)\) can be written as linear combination of \(a\) and \(b\)

Answer 5

ohk :) so since its not empty set then by WOP there is positive r >0 least number such that
\( r=a x_0 +by_0\)

Answer 6

brb

Answer 7

got that part, next \(r\) needs to be proved as the \(\gcd\) of \(a\) and \(b\)

Answer 8

let gcd(a,b)=d
its not nesseccary that r =d
r might be factor of d
(as we care about existance )
then d|a
and d|b
hence
d=am
d=bn

Answer 9

okie fine

Answer 10

isnt d is the greatest common divisor O.O

Answer 11

yes i think you meant

a = dm
b = dn

Answer 12

ohh yeah typo xD

Answer 13

but that doesn't prove anything

Answer 14

that just says that d | ax + by
it doesnt prove d = ax + by

Answer 15

im thinking . . .

Answer 16

i can attach the proof if you want

Answer 17

http://prntscr.com/3yy1ux

Answer 18

you dnt understand the proof u have ?
ok

Answer 19

im trying to..

Answer 20

attach

Answer 21

attached already ^^

Answer 22

where ?

Answer 23

O.O

Answer 24

http://prntscr.com/3yy1ux

Answer 25

say \(r = ax + by\) is the smallest element in \(S\),
then \(r | a\) because \(\cdots \)
\(r | b \) because \(\cdots\)

so \(r\) is a common factor of \(a\) and \(b\)

Answer 26

if \(c | ax + by\), then \(c | r\)
so \(r\) has to the greatest common factor.

Answer 27

ok ok , its only a game they make to that proof
1_ state the there exist d least integer that satisfy d= ax+by
2_ prove that d= gcd(a,b)
ok ?

Answer 28

did u get why \(r|a\) ?

Answer 29

im trying to follow the proof u attached

Answer 30

its the oposite to what i assumed before

Answer 31

WOP is confusing to interpret sometimes

Answer 32

mmm wait wanna start over ?

Answer 33

can we make sense of below without using WOP ?

the smallest element in the set has to divide both \(a\) and \(b\)

Answer 34

cuz i feel WOP is hiding some details and its a bit mechanical

Answer 35

mmm WOP is had nothing to do with divide or stuff its only a principle that sets that there is a small element in non empty positive set
wanna me to write down WOP ?

Answer 36

then how did they prove \(r | a\) ?

Answer 37

i was thinking they're applying WOP there

Answer 38

Well-Ordering Principle :-
Every nonempty set \(S\) of nonnegative integers contains a least element ; that is , there is some integer \(a\in S\) such that \(a\le b \) for all b's belonging to S

Answer 39

they applied WOP only by giving d

Answer 40

okay how did they arrive at r | a ?

Answer 41

and note that we dnt know yet if d= gcd its our clame

Answer 42

ok so what r u taking about the one i rote before u pring the link , or the r in link ?

Answer 43

r = ax + by

show that r | a and r | b

Answer 44

its confusing me to start like this :-\
lets start over shall we ?

Answer 45

sure

Answer 46

and reasoning every step we make ok ?

Answer 47

ok clean slate... :) start

Answer 48

ok so we have S={ .... }
its nonempty positive Set ok ?
then we can use WOP , let least be d
so
d=ax+by

Answer 49

our aim is to prove that d=gcd(a,b) ok ?

Answer 50

yes the aim is clear :)

Answer 51

good :)
so by D.A there is r,q
such that
a=qd+r s.t \(0\le r <d \)
agree to this ?

Answer 52

yes so far so good xD

Answer 53

ok then
r=a-qd
but d=ax+by
so
r=a-q(ax+by)=a(1-qx)+b(-qy)

ok ?

Answer 54

yes the proof so far is simple enough,
next line is what confuses me the most, please go ahead :)

Answer 55

ok so as u can see r=au+bv and if r is positive then r∈S but r <d from D.A assumtion which is a contradiction since d is the least element of S
so only one case we have r =0

Answer 56

that algebra statement is clear, but im finding it difficult to visualize it using numbers

Answer 57

if r =0 , then r\(\notin S\)

Answer 58

you wanna numerical example ?

Answer 59

i need some intuition - saying \(r \ne S\) just concludes the proof
but it kills other ways to think about the same

Answer 60

\(r \not \in S\) *

Answer 61

i see so u still not confident about r not in S ?

Answer 62

i get that \(r \not \in S\) as \(d\) is the least element in the set.

Answer 63

check what we set before :-

so by D.A there is r,q such that
a=qd+r s.t 0≤r<d *

since r cant be < d , then r =0

oki with this ?

Answer 64

yes

Answer 65

the thing is this proof is not that important , its only reasoning why there is linear compination of a,b s.t d=ax+xy
so dnt get frusted cuz of it :P

Answer 66

this is the starting point for euclid's lemma and congruences o.o

Answer 67

and diaphontine equations

Answer 68

im not talking about the result , im talking about the proof itself :D
result is very important

Answer 69

ax + by = c

has a solution only when gcd(a,b) | c constraint comes from this theorem itself, so i thought i would spend some time to digest this properly

Answer 70

>.> ur sake is much clear than what we are talking about :P it only need the result hehehe

but since we start shall we finish this ?

Answer 71

yeah please

Answer 72

ok
so we reached this
a(1-qx)+b(-qy)= 0

Answer 73

a=qd+r
a=qd

Answer 74

d|a ":)

Answer 75

if we obtaind the same steps for b
by D.A there is \(r_1,q_1\)
such that \( b=q_1d+r_1 \) s.t 0≤\(r_1\)<d
bla bla
then
b=\(q_1\)d or d|b

Answer 76

from
d|a
d|b
that make d common divisor of a,b

now we need to make sure that d is the greatest common divisior not only divisor :3

Answer 77

yes that part is easy :

if c is a common divisor of a and b,
then c | ax + by
=> c | d
=> d is the greatest common divisor

Answer 78

good lol
done ^

Answer 79

ty :)

Answer 80

np :)

Answer 81

my display pic makes me think im smart lil boy for a while lol