# Solving Linear CongruencesWatch

#1
Solve:
666x=355 mod 2009

I've got to a point where I've worked out that g=121a-227b.
a) Is this correct?
and b) what do I do from here if this is correct?
0
quote
9 years ago
#2
what are a,b and g?
0
quote
#3
a=666, b=355 and g=gcd(a,b)

(the equation is in the for ax=b mod n)
0
quote
9 years ago
#4
You're trying to find the inverse of 666. I assume you've used Euclid's algorithm to get to that equation?
0
quote
#5
Yeah...
0
quote
9 years ago
#6
(Original post by Sephrenia)
Yeah...
yeah, so what is the GCD?
0
quote
#7
gcd is 1
0
quote
9 years ago
#8
I think I see what's gone wrong. Try using a = 666, b = 2009 instead in the algorithm!
0
quote
#9
was I being a dumbarse?
0
quote
9 years ago
#10
(Original post by Sephrenia)
was I being a dumbarse?

you want to find the inverse of 666 wrt 2009.

You'll get 1 = 666c + 2009d.
take that mod 2009, and c is your inverse.
0
quote
#11
(Original post by yusufu)

you want to find the inverse of 666 wrt 2009.

You'll get 1 = 666c + 2009d.
take that mod 2009, and c is your inverse.
Doesn't a have to be less than b though?
0
quote
9 years ago
#12
(Original post by Sephrenia)
Doesn't a have to be less than b though?
hmmm. yeah actually.
0
quote
#13
If it helps I know the answer is 999...
0
quote
9 years ago
#14
2009 - 3*666 = 11
666 - 60*11 = 6
11 - 6 = 5
6 - 5 = 1

1 = 2.6 - 11
1 = 2(666 - 60.11) - 11 = 2(666) - 121(11)
1 = 2(666) - 121(2009 - 3(666)) = 365*666 - 121*2009.

So 1 = 365*666 (mod 2009)

should be doable from there.
0
quote
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

• University of Lincoln
Wed, 12 Dec '18
• Bournemouth University
Midwifery Open Day at Portsmouth Campus Undergraduate
Wed, 12 Dec '18
• Buckinghamshire New University
Wed, 12 Dec '18

### Poll

Join the discussion

#### Do you like exams?

Yes (166)
18.57%
No (543)
60.74%
Not really bothered about them (185)
20.69%

View All
Latest
My Feed

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

Why not re-start the conversation?

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