Hey! Sign in to get help with your study questionsNew here? Join for free to post
 You are Here: Home >< Maths

# Euclidean Algorithm

Announcements Posted on
Last day to win £100 of Amazon vouchers - don't miss out! Take our quick survey to enter 24-10-2016
1. Find integers m and n such that 7m + 55n = 1

Haven't been taught this yet but have been expected to do it for homework, can someone tell me how I go about doing it please
2. 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
3. 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
4. Now work that backwards (if that makes sense)

If it doesn't post and I'll show you
5. I don't get what you mean
6. (Original post by 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

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
7. 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
8. Thats fine, but how would you find the answer if it was much larger?
9. (Original post by 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)...
10. (Original post by 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?
11. 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...
12. (Original post by 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.
13. Okay, I will try, Im not sure if it works well, hence why I posted my solution lol...

m and n are integers right?
14. 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.
15. (Original post by 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.
I can only think of two, but if you think of the third, please enlighten me
16. (Original post by 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 ... ).
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.
17. (Original post by SimonM)
Going backwards

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...

(Original post by 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

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
18. (Original post by 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
19. 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 :< …

Write a reply…

Submit reply

## Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank
that username has been taken, please choose another Forgotten your password?
2. this can't be left blank
this email is already registered. Forgotten your password?
3. this can't be left blank

6 characters or longer with both numbers and letters is safer

4. this can't be left empty
your full birthday is required
1. Oops, you need to agree to our Ts&Cs to register
2. Slide to join now Processing…

Updated: September 28, 2008
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:
Today on TSR

### How does exam reform affect you?

From GCSE to A level, it's all changing

Poll
Useful resources

## Make your revision easier

### Maths Forum posting guidelines

Not sure where to post? Read here first

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

Can you help? Study help unanswered threads

## Groups associated with this forum:

View associated groups
Study resources

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

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