# modular arithmetic, euclid

• Dec 30th 2008, 10:14 AM
sheep99
modular arithmetic, euclid
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.
• Dec 30th 2008, 11:03 AM
Mush
Quote:

Originally Posted by sheep99
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.
• Dec 30th 2008, 08: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.

$\displaystyle 328-2\times122 = 84$
$\displaystyle 122-1\times 84 = 38$
$\displaystyle 84-2\times 38 = 8$
$\displaystyle 38-4\times 8 = 6$
$\displaystyle 8-1\times 6 = 2$
$\displaystyle 6-3\times 2 = 0$
So 2 is the highest common factor.
What is happening here is on each step we have $\displaystyle 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 $\displaystyle \frac{122\times328}{2}$ , and I am sure that you know how to add fractions from this point on.