Solving Linear Congruences Watch

Sephrenia
Badges: 2
Rep:
?
#1
Report Thread starter 9 years ago
#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
reply
yusufu
Badges: 16
Rep:
?
#2
Report 9 years ago
#2
what are a,b and g?
0
quote
reply
Sephrenia
Badges: 2
Rep:
?
#3
Report Thread starter 9 years ago
#3
a=666, b=355 and g=gcd(a,b)

(the equation is in the for ax=b mod n)
0
quote
reply
yusufu
Badges: 16
Rep:
?
#4
Report 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
reply
Sephrenia
Badges: 2
Rep:
?
#5
Report Thread starter 9 years ago
#5
Yeah...
0
quote
reply
yusufu
Badges: 16
Rep:
?
#6
Report 9 years ago
#6
(Original post by Sephrenia)
Yeah...
yeah, so what is the GCD?
0
quote
reply
Sephrenia
Badges: 2
Rep:
?
#7
Report Thread starter 9 years ago
#7
gcd is 1
0
quote
reply
yusufu
Badges: 16
Rep:
?
#8
Report 9 years ago
#8
I think I see what's gone wrong. Try using a = 666, b = 2009 instead in the algorithm!
0
quote
reply
Sephrenia
Badges: 2
Rep:
?
#9
Report Thread starter 9 years ago
#9
was I being a dumbarse?
0
quote
reply
yusufu
Badges: 16
Rep:
?
#10
Report 9 years ago
#10
(Original post by Sephrenia)
was I being a dumbarse?
:yep:
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
reply
Sephrenia
Badges: 2
Rep:
?
#11
Report Thread starter 9 years ago
#11
(Original post by yusufu)
:yep:
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
reply
yusufu
Badges: 16
Rep:
?
#12
Report 9 years ago
#12
(Original post by Sephrenia)
Doesn't a have to be less than b though?
hmmm. yeah actually.
0
quote
reply
Sephrenia
Badges: 2
Rep:
?
#13
Report Thread starter 9 years ago
#13
If it helps I know the answer is 999...
0
quote
reply
yusufu
Badges: 16
Rep:
?
#14
Report 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
reply
X

Reply to thread

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

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

Do you like exams?

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

Watched Threads

View All
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