Congruence problem


by mattmns
Tags: congruence
mattmns
mattmns is offline
#1
Oct23-05, 08:02 PM
mattmns's Avatar
P: 1,119
Hello I have the following question.
----
Solve the following congruences simultaneously:

[tex]2x + 3y \equiv 2 mod 631[/tex]
[tex]3x + 2y \equiv 3 mod 631[/tex]
----

I first tried adding and got [tex]5x + 5y \equiv 5 mod 631[/tex], but I was then stuck, so I tried the old multiplication, which looked worse as: [tex]6x^2 + 13xy + 6y^2 \equiv 6 mod 631[/tex]

Any ideas? I am guessing that I need to go somewhere with the addition one, but I can't see where. The instructor had a hint of using the fact that 631 is prime, but I can't see anything from that. Thanks.

Hmm, just got an idea, [tex]5(x + y) \equiv 5 mod 631[/tex], then find inverse of 5 and multiply it through to find x+y = something mod 631. I did this and got:

[tex]x + y \equiv 5*79380 mod 631[/tex]
which is
[tex]x + y \equiv 1 mod 631[/tex]
Now where can I go from here? Any ideas?
Phys.Org News Partner Science news on Phys.org
Lemurs match scent of a friend to sound of her voice
Repeated self-healing now possible in composite materials
'Heartbleed' fix may slow Web performance
Gokul43201
Gokul43201 is offline
#2
Oct24-05, 09:44 AM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,154
Try solving them like regular simultaneous equations.

Eliminate x from the equations. You have a congruence relation for y. Now plug this back in and find a separate congruence relation for x.
mattmns
mattmns is offline
#3
Oct24-05, 03:31 PM
mattmns's Avatar
P: 1,119
How would I do that without canceling the y's? In my mind I would have to multiply the top by 3 and bottom by 2, but when I added, I would get 0 = 0 mod 631.

Gokul43201
Gokul43201 is offline
#4
Oct24-05, 06:42 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,154

Congruence problem


No, you won't !


[tex]3x + 2y \equiv 3 ~~(mod~ 631)~~~~--(1)[/tex]
[tex]2x + 3y \equiv 2 ~~(mod~ 631)~~~~--(2)[/tex]

Let's do (1)*2 - (2)*3 ; this is legal since the modulo is the same for both congruences.


[tex]6x + 4y \equiv 6 ~~(mod~ 631)~~~~--(3)[/tex]
[tex]6x + 9y \equiv 6 ~~(mod~ 631)~~~~--(4)[/tex]

Subtracting gives : [tex]5y \equiv 0~~ (mod~631) [/tex]

What does this tell you about 'y' ? Plug that back in and figure out what 'x' should be.
mattmns
mattmns is offline
#5
Oct24-05, 06:50 PM
mattmns's Avatar
P: 1,119
Wow, I am retarded !!!! Thanks for pointing that out Gokul. Hmm, 3 times 3 is 9, and not 6, interesting! Thanks Gokul!
HallsofIvy
HallsofIvy is offline
#6
Oct24-05, 07:30 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,877
[tex]2x + 3y \equiv 2 mod 631[/tex]
[tex]3x + 2y \equiv 3 mod 631[/tex]

Did you notice that the right hand side is the same as the coefficients of x on the left? Hmm, suppose x= 1?
Gokul43201
Gokul43201 is offline
#7
Oct25-05, 09:52 AM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,154
Quote Quote by HallsofIvy
Did you notice that the right hand side is the same as the coefficients of x on the left? Hmm, suppose x= 1?
That's the clever way to do it. Us mortals have to turn the cranks....


Register to reply

Related Discussions
Congruence difficulty Linear & Abstract Algebra 1
Congruence Precalculus Mathematics Homework 3
solution to the general congruence Linear & Abstract Algebra 2
congruence problem Linear & Abstract Algebra 19
congruence help Linear & Abstract Algebra 5