Thread: Cant work out how someone goes from one step to next in short mod arithmetic problem

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!

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.

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.