Results 1 to 4 of 4

- Jul 19th 2008, 02:29 AM #1

- Joined
- Mar 2007
- From
- England
- Posts
- 104

- Jul 19th 2008, 02:56 AM #2

- Jul 19th 2008, 03:36 AM #3

- Joined
- Mar 2007
- From
- England
- Posts
- 104

Ok, I think I more or less follow the previous explanation, but for this question I'm a little confused still:

Q: 6x=2 (mod 8)

but this cancels to:

(not sure if I can cancel like that)

So

But 3*3=9=1 (mod 8) so

This gives x=3 (mod 8)

I know the answer is suppose to be x=3(mod 8) please can you show me where I went wrong.

- Jul 19th 2008, 03:54 AM #4
Yes, I forgot to mention it. There is an inverse if and only if they are coprime.

What I mean is that a has an inverse modulo n, if and only if a and n are coprime.

Why ?

Here,

Going back to the definition of the congruence, we have : , where .

That is to say .

So this is the same as .

When there is a common factor in , divide a,b, and n by this factor.

---------------------------

In a general case, how to find an inverse ?

- observe : for example, what number is divisible by 3 and such that it is 1 added to a multiple of 4 ? Answer is 9. It's easy by trial and error when it's small number.

- use the euclidian algorithm... I can give you links where I've done such things, or you can read that : Extended Euclidean algorithm - Wikipedia, the free encyclopedia