Extended Euclidean Algorithm Watch

carpmasterjong
Badges: 0
#1
Report Thread starter 9 years ago
#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
reply
Chewwy
Badges: 15
Rep:
?
#2
Report 9 years ago
#2
multiply through by 5.
0
reply
Notnek
  • Forum Helper
Badges: 20
Rep:
?
#3
Report 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
reply
Oh I Really Don't Care
Badges: 15
Rep:
?
#4
Report 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?

do not click unless you have thought about this - you might kick yourself
Spoiler:
Show
try multiplying everything by 5
0
reply
carpmasterjong
Badges: 0
#5
Report Thread starter 9 years ago
#5
Great, thanks. That's incredibly and frustratingly easy.
0
reply
Oh I Really Don't Care
Badges: 15
Rep:
?
#6
Report 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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

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
    Undergraduate Open Day - Llandaff Campus Undergraduate
    Sat, 27 Apr '19

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%

Watched Threads

View All