x Turn on thread page Beta
 You are Here: Home

# euclids algorithim watch

1. how does this work, i need help!
2. Euclid's Algorithm works to find the greatest common diviser (gcd) between two numbers. Here's an example:

Find the gcd of 32 and 18.
First, divide 32 by 18. This gives 1 with remainder 14.
Second, divivde 18 by 14 (the previous). This gives 1 with remainder 4.
Third, divide 14 by 4. This gives 3 with remainder 2.
Fourth, divide 4 by 2. This gives 2 with NO remainder. That means the gcd is 2.

So, let's assume we want to find the gcd of a and b.
a/b gives remainder r
b/r gives remainder s
r/s gives remainder t
...
x/y gives no remainder. Therefore y is the gcd of a and b.
3. Is that the same as the divisibility algorithm?
4. (Original post by mik1a)
Is that the same as the divisibility algorithm?
I've never heard of that.
5. how would that apply to my previous post on the maths problem?
6. how would that apply to my previous post on the maths problem?
7. (Original post by kamsingh)
how would that apply to my previous post on the maths problem?
19x - 8y = -2

Now, to find the GCD of 19 and 8.
19 = 8(2) + 3
8 = 3(2) + 2
3 = 2(1) + 1
2 = 1(2) + 0

Therefore 1 is the GCD of 19 and 8, so 19x-8y = 1 has solutions, and so therefore must 19x-8y = -2.

Rearrange each of the above to give
(1) 1 = 3 - 2(1)
(2) 2 = 8 - 3(2)
(3) 3 = 19 - 8(2)

Now substitute (2) into (1)
1 = 3 - (8 - 3(2)) = 3(3) - 8

Sub (3) into this
1 = 3(19-8(2)) - 8 = 19(3) + 8(-7)

So a solution to 19x-8y=1 is (3,7).
And a solution to 19x-8y=-2 can be found by multiplying the solution by -2, so (x,y) = (-6,-14)

Notice that if we choose x and y to be 8 and 19 respectively, then we get
19*8 - 8*19 = 0

So we can add multiples of 8 onto x, and multiples of 19 onto y, as many times as we like. Therefore we can say that the solutions to this equation are of the form
x = -6 + 8t
y = -14 + 19t.

x and y must be postive and less than 10, so the only solution is therefore when t = 1.
(x,y) = (2,5)

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: June 3, 2004
Today on TSR

### Loughborough better than Cambridge

Loughborough at number one

### Can I date a girl with no boobs?

Poll

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE