The Student Room Group
Reply 1
Do you know how to use the Euclidean Algorithm to find the highest common factor?

You could always guess. Try n = 1 as a starting point
Reply 2
55 = 7 x 7 + 6 --> (55,7) = (7,6)

7 = 6 x 1 + 1 --> (7,6) = (6,1)

6 = 1 x 6 + 0 --> (6,1) = (1,0)

Therefore the hcf = 1
Reply 3
Now work that backwards (if that makes sense)

If it doesn't post and I'll show you
Reply 4
I don't get what you mean :s-smilie:
Reply 5
bekahchu
55 = 7 x 7 + 6 --> (55,7) = (7,6)

7 = 6 x 1 + 1 --> (7,6) = (6,1)

6 = 1 x 6 + 0 --> (6,1) = (1,0)

Therefore the hcf = 1


Going backwards

7=6×1+17 = 6 \times 1 + 1
76×1=17 - 6 \times 1 = 1
7(557×7)×1=17 - (55 - 7 \times 7 ) \times 1 = 1

Unfortunately its not very clear when the gcd of the numbers is 1, the method used is slightly more obvious when you have a larger number as the gcd
Reply 6
Okay I don't know what way you people have gone about solving it, I haven't done questions like this either, hence why I am posting my solution, as I'm not sure if its the correct approach.

But I solved it like this... (Not sure if this is ideal, but it gave me a solution)

7 = 7 x 1, -7 x -1
55 = 5 x 11, -5 x -11, 55 x 1, -55 x -1

Common factors are 1 and -1

Since the coefficents of m and n are so large and we are looking for integers of m and n...

|m,n| greater than and equal to 1...

from this we know that if +/- m, then -/+ n to be possible to get a end value of 1 (Basically if one is positive the other is negative).

Test m = 1
7 + 55n = 1
55n = -6
n = -6/55

Test m = -1
-7 + 55n = 1
55n = 8
n = 8/55

Test n = 1
7m + 55 = 1
7m = -54
m = -54/7

Test n = -1
7m -55 = 1
7m = 56
m = 8

Solution found... n = -1 and m = 8
Reply 7
Thats fine, but how would you find the answer if it was much larger?
Reply 8
SimonM
Thats fine, but how would you find the answer if it was much larger?


Well I haven't really done these questions before, but I suppose I would test the values that had priority first i.e. the highest modulus common factor...

So I should find the answer after the first 4 tests... (- value of the common factor the then + value, on both n and m)...
Reply 9
Koudoo

So I should find the answer after the first 4 tests... (- value of the common factor the then + value, on both n and m)...



Wha?
Reply 10
Im sorry my explanation isn't too good, I am basically saying that I should be able to solve it in 4 tests, if there are 2 integer values to be found, and the rest known...

As I would test the right values first, the highest modulus common factors...
Reply 11
Koudoo
Im sorry my explanation isn't too good, I am basically saying that I should be able to solve it in 4 tests, if there are 2 integer values to be found, and the rest known...

As I would test the right values first, the highest modulus common factors...


Really? Could you write out your method in a way that I can understand then?

Could you demonstrate with

2322m + 654n = 6.
Reply 12
Okay, I will try, Im not sure if it works well, hence why I posted my solution lol...

m and n are integers right?
Reply 13
You could have a look here:
http://mathworld.wolfram.com/DiophantineEquation.html

I seem to remember that we had three different techniques for solving simple linear diophantine equations at school (one of which was the extended Euclidean algorithm), but it's been years since I've done that and I can't really remember it properly. :frown:
Reply 14
Sinuhe
You could have a look here:
http://mathworld.wolfram.com/DiophantineEquation.html

I seem to remember that we had three different techniques for solving simple linear diophantine equations at school (one of which was the extended Euclidean algorithm), but it's been years since I've done that and I can't really remember it properly. :frown:


I can only think of two, but if you think of the third, please enlighten me
Reply 15
SimonM
I can only think of two, but if you think of the third, please enlighten me

I'll have a look at my number theory notes when I get back home (in late December, unfortunately) and I'll let you know if there really are three that we used (see, my memory sometimes plays games with me ... :p: ).
It's been four years since we did that, but I think one was using congruence modulo something to simplify the equation, one was this Euclidean algorithm, and one was using some sort of weird tabulation; I'm not really sure though. In the end they're probably all the same method in different disguises anyway. :smile:
Reply 16
SimonM
Going backwards

7=6×1+17 = 6 \times 1 + 1
76×1=17 - 6 \times 1 = 1
7(557×7)×1=17 - (55 - 7 \times 7 ) \times 1 = 1

Unfortunately its not very clear when the gcd of the numbers is 1, the method used is slightly more obvious when you have a larger number as the gcd


When working backwards shouldn't it be...

1 = 0 x 6 + 1 x 1
1 = 1 x 7 - 1 x 6
1 = 1 x 55 + -8 x 7

Giving the solutions of 1 and -8...

SimonM
Really? Could you write out your method in a way that I can understand then?

Could you demonstrate with

2322m + 654n = 6.


Okay yeah, I can't use it with too large numbers which is a shame :woo:

But I still sloved your question anways...

I had to use the a variation of the Euclidean Algorithm

2322m + 654n = 6
387m + 109n = 1

387 = 109 x 3 + 66
109 = 60 x 1 + 49
60 = 49 x 1 + 11
49 = 11 x 4 + 5
11 = 5 x 2 + 1

Then...

1 = 0 x 5 + 1 + 1
1 = 1 x 11 - 2 x 5
1 = -2 x 49 + 9 x 11
1 = 9 x 60 - 11 x 49
1 = -11 x 109 + 20 x 60
1 = 20 x 387 - 71 x 109

So the solutions are m = 20 and n = -71
Reply 17
Koudoo

I had to use the a variation of the Euclidean Algorithm


Yeah, thats called the extended Euclidean Algorithm and is the one I demonstrated earlier in the thread
Reply 18
Oh, my bad, I should have read everything more thoroughly...

I wonder where the thread starter has gone, since her question has been answered, but we got no reply :< &#8230;

Latest