modular arithmetic, euclid

sheep99 · #1 $Old$ December 30th, 2008, 12:14 PM

using euclids algorithm compute the sum 8/122 + 11/328.
i missed the lecture so i dnt have a clue but theres 2 methods to do this i think.i dont know what the lecturer meant by using ' / '

does this mean 8mod122 + 11mod328
duno how id approach this i thought its possible to say.
8mod122=130 , 11mod328=339. 130 + 339 =469 looks very wrong.
help?lol.

Mush · #2 $Old$ December 30th, 2008, 01:03 PM

Quote:

Originally Posted by sheep99 $View Post$

using euclids algorithm compute the sum 8/122 + 11/328.
i missed the lecture so i dnt have a clue but theres 2 methods to do this i think.i dont know what the lecturer meant by using ' / '

does this mean 8mod122 + 11mod328
duno how id approach this i thought its possible to say.
8mod122=130 , 11mod328=339. 130 + 339 =469 looks very wrong.
help?lol.

Useless post, sorry.

badgerigar · #3 $Old$ December 30th, 2008, 10:22 PM

Quote:

does this mean 8mod122 + 11mod328

You can't add numbers modulo different numbers.

Quote:

using euclids algorithm compute the sum 8/122 + 11/328.

I think the notation is probably meant to mean 8 divided by 122 + 11 divided by 328. The Euclidean algorithm can be used to find the lowest common multiple of 122 and 328.
Notations for the algorithm sometimes differ, but I do mine like this.

$328-2\times122 = 84$
$122-1\times 84 = 38$
$84-2\times 38 = 8$
$38-4\times 8 = 6$
$8-1\times 6 = 2$
$6-3\times 2 = 0$
So 2 is the highest common factor.
What is happening here is on each step we have $a-n\times b = c$ .
a and b are known, so we find n as the largest integer so that a-nb is positive and c as a-nb. Then we use b for the new a and c for the new b and repeat until we get 0. The highest common factor is then the value for b in the last step.
The lowest common multiple is then $\frac{122\times328}{2}$ , and I am sure that you know how to add fractions from this point on.