Solving linear congruences

[plenderj]

Just wondering if anyone had a site that shows how to solve a linear congruence ... eg. 13x = 4 Mod 20

Not programatically, just manually

[Sirius Zor'Z]

4 Mod 20 is 4

[plenderj]

I know that
But thats not what a linear congruence is

[Sirius Zor'Z]

What then is a linear congruence?

[plenderj]

http://members.aol.com/Windmill96/mod.html

[Guv]

If I understand your problem, you are looking for an integer solution to the following equation.

13 * X = 20 * Y + 4

There are many solutions, but it is not obvious to me that there should any integer solutions. I would not be surprised to discover that there are none or many integer solutions.

I think somebody named Diophantine (or something similar) investigated such equations and developed some methods. Try a web search on his name and slight variations.

If that does not help, try researching Number Theory, which deals with this and many other problems involving integer solutions.

If Number Theory is not a good search key, try Fermat, which is likely to find sites that have data and/or links relevant to number theory.

[plenderj]

Yeah these are diophantine related, and its got to do with Fermat and Number Theory and EulerPhi etc.

I just cant find any decent examples on solving linear congruences. I can only find source code, which I cant bloody well write down in a maths exam ... which I might add is on monday at 09:30

[DavidHooper]

which exam is it plenderj? alevels are over...

[Guv]

As mentioned in my previous post, it looks like you need to know how to solve linear Diophantine equations. When I searched the internet for Diophantine, quite a few were listed, including the following.

http://www.thoralf.uwaterloo.ca/htdocs/linear.html

The above site provides solutions to linear Diophantine equations and shows some of the work involved. If you give it several equations, you might be able to figure out how they are solving them.

If you are having a test on Monday, I suspect that you have a text book or some library references that you should be studying.

The problem you posted seems to be equivalent to trying to solve the following.

13 * X = 20 * Y + 4 or
13 * X - 20 * Y = 4

The latter is a standard linear Diophantine equation. The site mentioned above provided the following general solution.

X = 20 * N - 12
Y = 13 * N - 8

Every value of N yields an (X, Y) pair that satisfies the original conditions.

[plenderj]

My girlfriend has since found the notes for me. Thank god
It basically goes like this :

Solve : 19x = 2 Mod 360

gcd(19, 360) = 1 => co=prime
=> x^EulerPhi(m) = 1 Mod m

19x^EulerPhi(360) = 1 Mod 360
19x = 19^EulerPhi(360) Mod 360

To work out EulerPhi(360) :
Divisors of 360 : 6x6x10 = 2x3x2x3x2x5 = 2^3 x 3^2 x 5
=> EulerPhi(360) = EulerPhi(2^3) x EulerPhi(3^2) x EulerPhi(5)
=> 4xEulerPhi(2) x 3xEulerPhi(3) x EulerPhi(5)
=> 4.1 x 3.2 x 4 = 4 x 6 x 4 = 96
=> EulerPhi(360) = 96

19x = 19^96 Mod 360
x = 19^95 Mod 360
x = 2.19 Mod 360 ..... note1

=> Answer :
x = 38 Mod 360

And Check if its true :
19x38 Mod 360 = 2 ?
722 Mod 360 => (722 - 720) Mod 360 = 2
=> True


note1 there has to do with PowerMod ... ie. a^b Mod n
Theres a way of working it out but I've not figured it out yet.
Doesnt matter though because you just have to write the above.


Oh, and DavidHooper, they're college exams.
Maths for my ICT course : www.cs.tcd.ie/courses/baict/