Register to reply

Congruence problem

by mattmns
Tags: congruence
Share this thread:
mattmns
#1
Oct23-05, 08:02 PM
mattmns's Avatar
P: 1,123
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
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
Gokul43201
#2
Oct24-05, 09:44 AM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,155
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
#3
Oct24-05, 03:31 PM
mattmns's Avatar
P: 1,123
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
#4
Oct24-05, 06:42 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,155
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
#5
Oct24-05, 06:50 PM
mattmns's Avatar
P: 1,123
Wow, I am retarded !!!! Thanks for pointing that out Gokul. Hmm, 3 times 3 is 9, and not 6, interesting! Thanks Gokul!
HallsofIvy
#6
Oct24-05, 07:30 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,556
[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
#7
Oct25-05, 09:52 AM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,155
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
Prove there is at least 1 friday the 13th between march and october 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