Hey there! Sign in to join this conversationNew here? Join for free
x Turn on thread page Beta
    • Thread Starter
    Offline

    0
    ReputationRep:
    how does this work, i need help!
    Offline

    0
    ReputationRep:
    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.
    Offline

    14
    ReputationRep:
    Is that the same as the divisibility algorithm?
    Offline

    0
    ReputationRep:
    (Original post by mik1a)
    Is that the same as the divisibility algorithm?
    I've never heard of that.
    • Thread Starter
    Offline

    0
    ReputationRep:
    how would that apply to my previous post on the maths problem?
    • Thread Starter
    Offline

    0
    ReputationRep:
    how would that apply to my previous post on the maths problem?
    Offline

    1
    ReputationRep:
    (Original post by kamsingh)
    how would that apply to my previous post on the maths problem?
    Ok, you had
    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)

    Taadaaa.
    • Thread Starter
    Offline

    0
    ReputationRep:
    sorry about this, im lost at the substition bit :confused:
 
 
 
Poll
Do you agree with the proposed ban on plastic straws and cotton buds?

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

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.