mod 5 every non-zero element has a multiplicative inverse. for example (4)(4) = 1 mod 5, so "1/4" = 4.
thus s = 1s = ((4)(4))s = 4(4s).
the RHS (4)(3) = 2 mod 5 should be clear, since 12 = 2 mod 5.
Ok so we have:
3+4s=1(mod5)
4s=3(mod5)
from there to there is fine obviously, but then after they do this....
4*4s=4*3(mod5)
s=2(mod5)
Can someone explain simply what is going on to get to s=2(mod5)
Thanks!
thanks, that makes sense, so what now if i have:
n*s = 2a(mod2n)
so, n*s = a(mod2n)?
how would i proceed from here.... because i cant find the multiplicative inverse this time can i?
Basically this is in the midst of solving the simultaneous congruences:
x = a(modn)
x = 2a(mod2n)
x = 3a(mod3n)
So im trying to use the chinese remainder theorem.... will it work?
well, n,2n and 3n are not pair-wise co-prime, so the chinese remainder theorem doesn't apply.
however, if x = a (mod n), then x = a + kn. so x = 2a (mod 2n) is a + kn = 2a (mod 2n),
that is kn = a (mod 2n). but it's hard to say more without knowing what a and n are (specifically, what gcd(a,n) might be).
could we then not say that kn = 2nr + a
so, k=2r +a/n
then put it back into equation, so x = n(2r +a/n) + a
x=2nr +2a
2nr+2a = 3a(mod3n)
2nr = a(mod3n)
2nr = 3nu + a
r = 3nu/2n + a/2n
r = 3u/2 + a/2n
x = 2n(3/2u + a/2n) + 2a
x = 3nu + a +2a
x = 3a + 3nu
so x = 3a?
Does that follow or have i broken some sort of modular rule along the way?
Thanks
no, because 2r + a/n may not be an integer.
suppose a = 2, and n = 3.
x = 2 mod 3
x = 4 mod 6 has no solution. if it did, we would have 3k+2 = 4 mod 6 for some integer k, hence 3k = 2 mod 6.
but every integer of the form 3k is congruent to 3 or 0 mod 6.
if you try to write 3k = 6r + 2, you get the solution k = r + 2/3, and sure, for r = 0, 3(2/3) is a multiple of 6.
but 2/3 is not an integer. if we allowed non-integer solutions, we would get odd things like 1 = 3 (mod 3), since 1 = 3(1/3).
as i said before, without knowing more about "a" and "n" there's not a more general statement about how to continue. there are values for a and n for which no solutions exist.