LinkBack URL
About LinkBacksCould someone please explain to me how to do this question:
3x=5(mod 7)
The answer is 4 but I'm not sure how to get there.
Help would be appreciated.
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.
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
  |
Originally Posted by free_to_fly 
