# Extended Euclidean AlgorithmWatch

#1
Hi, had this question come up in an exam today and it wasn't covered in the notes but I think it must be a follow on from the extended euclidean algorithm which was in the notes.

I think it was something like this. Suppose gcd(a,b)=1 and that gcd(a,c)=gcd(b,c)=1, explain in general how to find all solutions to ax+by=c.

Hence find all solutions to 167x+59y=5.

The first part asked to find gcd(167,59) and then write it in the form 167x+59y=1 which was simple enough and used what was in the notes.
0
9 years ago
#2
multiply through by 5.
0
9 years ago
#3
If (a,b)=1 then there exist x,y such that ax+by=1. Therefore, there exists x,y, such that a(xc)+b(yc)=c.
0
9 years ago
#4
The idea would be to get in that form

Spoiler:
Show
x = -6 ; y = 17
then make the substitution
Spoiler:
Show
x = (-6 + D) and y = (17 + C)
you know that there is an integer k that satisfies the above constraints as 167 and 59 are ?
Spoiler:
Show
they are coprime so it follows that 167D + 59C = 0 has a solution if D = 59k and C = 167k, for an integer k
which means that you have found the general solution to 167x + 59y = 1 ; what would be a smart thing to do?

Spoiler:
Show
try multiplying everything by 5
0
#5
Great, thanks. That's incredibly and frustratingly easy.
0
9 years ago
#6
does anyone know why this condition is neccessary?

gcd(a,c)=gcd(b,c)=1

for instance, we can easily choose gcd(a,c) = 167 =/= gcd(b,c) = 1

and yet there is a general solution of

167x + 59y = 167

or perhaps the condition if for a different area
0
X

new posts
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• Cranfield University
Cranfield Forensic MSc Programme Open Day Postgraduate
Thu, 25 Apr '19
• University of the Arts London
Open day: MA Footwear and MA Fashion Artefact Postgraduate
Thu, 25 Apr '19
• Cardiff Metropolitan University
Sat, 27 Apr '19

### Poll

Join the discussion

#### Have you registered to vote?

Yes! (315)
37.77%
No - but I will (64)
7.67%
No - I don't want to (62)
7.43%
No - I can't vote (<18, not in UK, etc) (393)
47.12%