Question

while finding gcf using euclid algorithm, why do we chase after remainder and quotient after each step ?

dont get why gcf of two numbers equal gcf of quotient and remainder. could somebody care to explain plzz ?

Answer 1

We try to find gcf of 2445 and 652. We have
```
step1 : 2445 = 652*3 + 489
step2 : 652 = 489*1 + 163
step3 : 489 = 163*3 + 0
```

thus the gcf of 2445 and 652 is 163

:S i dont get why gcf(2445, 652) equals gcf(652, 489)

Answer 2

@jim_thompson5910

Answer 3

one sec

Answer 4

okay thank you :)

Answer 5

I think I found a page that explains it, but I'm going to try and translate it into something that makes more sense, one more sec (sorry for the long wait)

Answer 6

May I answer, @jim_thompson5910 ?

Answer 7

sure go for it

Answer 8

Gratzie. All right, so, let's say we have a number \(d\) that divides your two numbers \(a, b\). If \(d\) divides \(a\), then we can multiply \(d\) by some number (let's call it \(d_a\)) to equal \(a\), similarly we do the same for \(b\) and call this number \(d_b\). So we know:
\[
d\cdot d_a=a\\
d\cdot d_b=b
\]So, if we have a linear combination of a and b, expressed as:
\[
ax+by
\]For some integers \(x, y\), then, we can say:
\[
ax+by=d\cdot d_a\cdot x+d\cdot d_b\cdot y=d(d_a x+d_b y)
\]Which means that d also divides any linear combination of these two numbers. Thus, since the remainder is a linear combination of the two numbers, the GCD also divides the remainder, as well as the two numbers.
Another way to show this is to give Bezout's Identity.

Answer 9

@LolWolf thanks! so remainder(489) is divisible by gcf i get that.
cuz 489 = 2445-652*3
which is a combination of the two input numbers.

how we conclude gcf of remainder and the divisor gives the gcf of input numbers from this ?

Answer 10

All right, so we know that the GCD (let's call it \(g\)) must divide the pen-ultimate remainder, \(r\), right? (due to the above proof) So, therefore, we know that all divisors of both numbers divide \(r\), and, thus, g being one of those numbers, also divides \(r\), which implies that \(g\leq r\). We also know that \(r\) divides a linear combination of the two numbers (since \(r\) also divides each number), so, \(r\) must also divide \(g\), which implies that \(r\leq g\). Since:
\[
r\leq g\wedge
g \leq r\implies g=r
\]Thus we are done. QED.

Answer 11

LolWolf im not able to follow fully..

So, therefore, we know that "all divisors of both numbers divide r," and, thus, g being one of those numbers, also divides r, which implies that g≤r.

there you mean "all divisors common to both numbers divide r" is it ?

Answer 12

id like to understand this too :p

Answer 13

How you made that grey bracket?

Can you tell me ??

Answer 14

Grey box sorry..

Answer 15

tick tick tick

tick tick tick

Answer 16

```

```

Answer 17

\`\`\`

\`\`\`

Answer 18

This you have made I know the code for that..

Answer 19

Sorry I did not get,,

Answer 20

\`\`\`

\`\`\`

Answer 21

write anything in between 3 back ticks.

Answer 22

for getting greybox...

Answer 23

http://openstudy.com/users/sara12345#/updates/503dfd2ce4b0074824ff598c

Answer 24

How we make back ticks ??

Answer 25

you have the key on your keybord "~"

Answer 26

Yes...

Answer 27

Oh yeah I saw that..

Answer 28

` ` `

` ` `

Answer 29

water good to see u u maintaining low profile these days :)

Answer 30

Low profile meaning ???

Answer 31

means not seeing u ol much

Answer 32

Oh my college has been started so I don't get time to be online here..

Answer 33

could you guys help me plzz

Answer 34

psh who needs college

Answer 35

What exactly is your question Sara ??

Answer 36

my first reply just after the question

i dont get why gcf(2445, 652) equals gcf(652, 489)

Answer 37

@waterineyes

Answer 38

Can't you try by working them out??

Answer 39

how

Answer 40

Can you find gcf of 2445 and 652 ??

Answer 41

it works. does not look obvious

Answer 42

i can find using both euclid algorithm and prime factors

Answer 43

Then use Euclid Algorithm..

Answer 44

i get 163. how i got it i have no idea while using euclid algorithm
where as prime factors is quite obvious

Answer 45

Now find the same for 652 and 489..

Answer 46

using prime factors ?

Answer 47

You can use both,,

But use Euclid Algorithm here too..

Answer 48

step1 : 2445 = 652*3 + 489

Answer 49

step2 : 652 = 489*1 + 163

Answer 50

Go ahead...

Answer 51

i am simply copying my first reply and pasting here...

Answer 52

Yes I know but go for second one now..

Answer 53

step2 ?

Answer 54

`652 = 489*1 + 163 ` `
` 489 = 163*1 + etc etc` `




Like this..

Answer 55

yea

Answer 56

163*2 I think..

Answer 57

*3

Answer 58

step3 : 489 = 163*3 + 0

Answer 59

Yep..

So again you got 163


don't you think the gcf of both are equal that is 163 ??

Answer 60

i just dont see how the logic is flowing.. .
step1 to step2, why we took divisor and remainder ?

Answer 61

step3 : 489 = 163*3 + 0

i think, gcf of 489 and 163 is 163

Answer 62

im sorry just trying to understand

Answer 63

According to Euclid Algorithm,

We just divide two numbers:

After that the remainder got in first step becomes quotient and the quotient of first step becomes dividend

again divide them..

and same process goes on until you get 0..

Answer 64

yea

Answer 65

i dont understand the second step

Answer 66

See, gcf of 652 and 489 is 163..

and gcf of 489 and 163 is also same..

Answer 67

Second step where??

Answer 68

Basically what do you mean by gcf Sara can you tell me ??

Answer 69

greatest common factor

Answer 70

I think it is just the full form of gcf..

I am asking about its meaning..

Answer 71

greatest integer that goes in both a and b

Answer 72

the gcf of a and b

Answer 73

I tell you..

Basically, it means the greatest factor that will be common to both and will divide both simultaneously..

For example:
For 3 and 9, what factor can divide both ??

Answer 74

3 is the factor that is common to both 3 and 9 and will divide 3 and 9 both..

Answer 75

3 = 3^1
9 = 3^2

gcf = 3^1

Answer 76

finding gcf using prime factors is obvious. i get it

Answer 77

and 3 here is greatest factor too..

Because you cannot have factor greater than 3 like 4 and 5 that can divide 3 and 9 both at same time..

Getting Sara??

Answer 78

its euclif algorithm that makes me insane

Answer 79

wit plz

Answer 80

See, prime factorization and Euclid are just the way to find gcf but you must understand first what is gcf..

Answer 81

wait*

Answer 82

Take your time...

Answer 83

Because you cannot have factor greater than 3 like 4 and 5 that can divide 3 and 9 both at same time..

i get this

Answer 84

yes that is the greatest and common and factor too that is why that is called gcf..

Answer 85

thats the reason in prime factors we search for greatest number of common factors..

Answer 86

yeaa

Answer 87

Oh so basically you are asking the working of Euclid Algorithm..

Answer 88

yea just this :
:S i dont get why gcf(2445, 652) equals gcf(652, 489)

Answer 89

See if 163 is the greatest common factor then that will divide 2445, 652 and 489 at the same time..

On dividing by 163 at the same time you will get : 15, 3 and 1..

Answer 90

It is same as;

As table of 3 contains 9 15 27 45 etc

Similarly table of 163 contains:

2445, 652 and 489..

Answer 91

Sorry, I'm a little late to the party (I have to sleep!). But, the point of my first proof was to show that the pen-ultimate remainder (i.e. the one before the last remainder, which equals zero) \(r_p\) is also, in fact a linear combination of the two numbers, right? Because if we rearrange division algorithm, we get, for some number and quotient \(n, q\) and divisor and remainder \(d, r\):
\[
n=qd+r\implies\\
r=n-qd
\]Here, \(r\) is also a linear combination of both \(d, n\). This means, by our previous proof that \(\text{GCD}(n,d)=\text{GCD}(r,d)\). And that the GCD divides \(r\) (and therefore \(r_p\)), thus \(g\le r_p\). But, since the pen-ultimate remainder must have divided it's preceding number (due to the last step equaling zero), it therefore must divide the GCD (which we define as: "the divisor of two numbers \(a,b\) such that all other common divisors divide it), if it divided a linear combination of it. By this, then, we have that \(r_p\le g\). Putting these two conditions together, we get that \(r_p=g\).