d2jsp
Log InRegister
d2jsp Forums > Off-Topic > General Chat > Homework Help > Math @ University > Congruences
Add Reply New Topic New Poll
Member
Posts: 5,065
Joined: Dec 14 2005
Gold: 1,073.00
Jun 23 2013 07:53am
hey yo, ive got math exam in 2 days and i have no clue how to solve congruences ><

for example:
15x = 51 (mod 117)
by equals sign '=' i mean 'is-congruent-to', it's similar to equals sign, but there are 3 parallel lines, not 2.

I hope you know what im talking about, any ideas people?
Member
Posts: 28,331
Joined: Jun 9 2007
Gold: 11,700.00
Jun 23 2013 11:15am
Quote (undek @ 23 Jun 2013 13:53)
hey yo, ive got math exam in 2 days and i have no clue how to solve congruences ><
for example:
15x = 51 (mod 117)
by equals sign '=' i mean 'is-congruent-to', it's similar to equals sign, but there are 3 parallel lines, not 2.
I hope you know what im talking about, any ideas people?


you want to find the smallest x for which 15x = 51 (mod 117) ?

the first few numbers which are 51(mod 117) are 51, 168 (=51+117), 285 (=51+2x117)

so the smallest solution is 285 / 15 = 19
Member
Posts: 16,662
Joined: Nov 24 2007
Gold: 15,245.00
Trader: Trusted
Jun 23 2013 02:37pm
You want to solve for y (I'll use x as the symbol for multiplication) :

ay = b (mod c)

where a, b and c are 3 given integers.

First, you must find the largest common divisor between a and c (let's say d).

In your example,
a = 15
b = 51
c = 117
d = 3

If d is not a divisor of b, then the equation has no (integer) solution. A proof is easy : b = ay + kc (with k some integer), so if d divides both a and c, he also divides ay + kc, hence b.

Else, you must divide by d all the 3 coefficients. So you can assume, from now, that a and c have no higher common divisor than 1.

In your example, the new equation is : 5y = 17 (mod 39)

where a = 5, b = 17 and c = 39.

Next, you must find 2 integers u and v for which : au + cv = 1.
Those integers are the Bezout coefficients, you can find them thanks to Euclid's algorithm. See below if you need.
The fact that a and c have no common divisor assure you that u and v exist (they are not unique, but it doesn't matter).

In you example : 5x8 + 39x(-1) = 40 - 39 = 1 so you can take u = 8 and v = -1.

Now multiply the last equation by b :

aub + cvb = b
au' + cv' = b

where u' and v' are 2 new integers (u' = 8x17 = 136 and v' = (-1)x17 = -17 )

Last, you can substract :

ay = b (mod c)
au' = b (mod c)

leading to : a(y - u') = 0 (mod c)

and since a and c have no common divisor, this assure you that y - u' = 0 (mod c), in other words : y = u' + kc (with k some integer).

Conclusion :

ay = b (mod c) if and only if y = u' (mod c)

Remember that all common divisors between a and c must be eliminated first.

In your example :

15y = 51 (mod 117) if and only if y = 136 (mod 39), or y = 19 (mod 39), since 136 = 19 (mod 39)

Back to Euclid's algorithm : use it to find the largest common divisor between 2 integers, start with the highest of the 2 (example with 39 and 5) :

39 = 7x5 + 4
5 = 1x4 + 1

the last non-zero rest is 1 (ie : 1 is the highest common divisor between 39 and 5).

Now start from 1 :

1 = 5 - 1x4
and since 4 = 39 - 7x5 (previous line),
1 = 5 - 1x(39 - 7x5)
1 = 5 - 1x39 + 7x5
1 = (1+7)x5 - 1x39
1 = 8x5 - 1x39

Of course, you could find immediatly 8 and -1 in this case. But this algorithm helps for higher numbers (or if you want to create a computer program).

Feel free to pm if something is missing, good luck.
Member
Posts: 16,144
Joined: Mar 27 2008
Gold: 14,618.00
Jun 23 2013 05:39pm
i'd go with the extended euclidean algorithm, which is easy once you understood it:
http://en.wikipedia.org/wiki/ExtendedEuclideanalgorithm

edit: even better description in german:
http://de.wikipedia.org/wiki/ErweitertereuklidischerAlgorithmus#RekursiveVariante
read the Rekursive Variante part, especially the table with a b q s and t
you don't even need to read the german text, as long as you read the equations to fill up the table ;)

This post was edited by Richter on Jun 23 2013 05:57pm
Member
Posts: 28,331
Joined: Jun 9 2007
Gold: 11,700.00
Jun 23 2013 06:34pm
Quote (Richter @ 23 Jun 2013 23:39)
i'd go with the extended euclidean algorithm, which is easy once you understood it:
http://en.wikipedia.org/wiki/ExtendedEuclideanalgorithm
edit:even better description in german:
http://de.wikipedia.org/wiki/ErweitertereuklidischerAlgorithmus#RekursiveVariante
read the Rekursive Variante part, especially the table with a b q s and t
you don't even need to read the german text, as long as you read the equations to fill up the table ;)


that's trivial since the german language is more precise than english in expressing concepts
but you gave the wrong link
either go into the english language link and click on german or go directly: http://de.wikipedia.org/wiki/Erweiterter%5Feuklidischer%5FAlgorithmus

/edit ggT (german) = gcd (english) - rest as 'Richter' said is easy to comprehend

This post was edited by brmv on Jun 23 2013 06:36pm
Member
Posts: 16,144
Joined: Mar 27 2008
Gold: 14,618.00
Jun 24 2013 06:53pm
Quote (brmv @ 24 Jun 2013 01:34)
that's trivial since the german language is more precise than english in expressing concepts
but you gave the wrong link
either go into the english language link and click on german or go directly: http://de.wikipedia.org/wiki/ErweitertereuklidischerAlgorithmus

/edit ggT (german) = gcd (english) - rest as 'Richter' said is easy to comprehend


thanks you're right, my link doesn't work :) as a student he will find it anyway :P
hmm, i think your link also doesn't work? xD
maybe it's just my browser...
but really, imo just reading the equations should be enough, if you go for this table with the "a b q r and t" values in "Rekursive Variante"
Member
Posts: 28,331
Joined: Jun 9 2007
Gold: 11,700.00
Jun 24 2013 07:18pm
Quote (Richter @ 25 Jun 2013 00:53)
thanks you're right, my link doesn't work :) as a student he will find it anyway :P
hmm, i think your link also doesn't work? xD
maybe it's just my browser...
but really, imo just reading the equations should be enough, if you go for this table with the "a b q r and t" values in "Rekursive Variante"


you are right, because the part after wiki contains underlines, so defaults to yours - "Erweiterter_Euklidischer_Algorithmus" is the right part after de.wikipedia.org/wiki/
Member
Posts: 16,144
Joined: Mar 27 2008
Gold: 14,618.00
Jun 25 2013 10:10am
Quote (brmv @ 25 Jun 2013 02:18)
...contains underlines...

maybe we can write in the jsp-feature-request a topic that we want support for url's with underlines in it?
Go Back To Homework Help Topic List
Add Reply New Topic New Poll