AHW said:
Many thanks for the help~~
oops, have just realized I've got the question wrong. It should be 5x=1(6) instead of 5x=1(16).
okay, so you've found 13 is a solution of 5x=1(16), so x=13(16) simply means 13 is a solution of mod 16?
I have used the technique to help solving a system of linear congruences
x=0(2) x=0(3) x=1(5) x=6(7)
by using chinese remainder theorem
m=2x3x5x7=210
n1=210/2=105 105b1=1(2) > b1=1(2)
n2=210/3=70 70b2=1(3) > b2=1(3)
n3=210/5=42 42b3=1(5) > b3=3(5)
n4=210/7=30 30b4=1(7) > b4=4(7)
Xo = 105x1x0+70x1x0+42x3x1+30x4x6=846 = 6(mod 210)
Here's how I would do that. x= 6 (mod 7) means that x= 7k+ 6 for some integer k. x= 1 (mod 5) means that x= 5j+ 1 for some integer j. Then 5j+ 1= 7k+ 6 or 5j- 7k= 5. Now 5(3)- 7(2)= 1 so 5(15)- 7(10)= 5 so one solution is j= 15, k= 10 and so the general solution is j= 15+ 7m, k= 10+ 5m. Since x= 7k+ 6, we now have that x= 7(10+ 5m)+ 6= 76+ 35m which is the same as saying x= 76 (mod 35). But 76= 2(35)+ 6 so this is the same as x= 6 (mod 35) or x= 35n+ 6 for some integer n.
x= 0 (mod 3) means x is a multiple of 3: x= 3p= 6+ 35n or 3p- 35n= 6. 12(3)- 35= 1 so 72(3)- 6(35)= 6. We must have p= 72+ 35q, n= 6+ 3r. Then x= 35n+ 6= 35(6+ 3r)+ 6= 216+ 105r= 6+ 2(105)+ 105r= 6+ 105(r+2) which we can write 6+ 105s
x= 0 (mod 2) means x is a multiple of 2: x= 2t= 6+ 105s so 2t- 105s= 6. Of course, 2(53)- 105(1)= 1 so 2(318)- 105(6)= 6. t= 318+ 105u= 3+ 315+ 105u= 3+ 105(u+ 3)= 3+ 105(v).
Since x= 2t, x= 6+ 210v for some integer v. That's exactly what you got!
(I essentially used the idea of the "Chinese remainder theorem" rather than just the result.)
but the answer is x=6 (mod 420)
I don't understand why it's mod 420.
You are right and the "answer" is wrong.
If x= 6+ 210n, then x/2= 3+ 105n, an integer: 6+210n is a multiple of 2; 6+ 210= 0 (mod 2).
If x= 6+ 210n, then x/3= 2+ 70n, and integer: 6+210n is a multiple of 3; 6+ 210= 0 (mod 3).
If x= 6+ 210n, then x/5= 1+ 42n with remainder 1: 6+210n is a multiple of 5 plus 1; 6+ 210= 1 (mod 5).
Because 7 does not divide 6 we need to look at x= (6+ 210)+ 210(n-1)= 216+ 210(n-1). Then x/7= 30+ 30(n-1)+ 6: 6+ 210n is a multiple of 7 plus 6; 6+ 210n= 6 (mod 7).
6+ any multiple of 210 satisfies the conditions of the problem: x= 6 (mod 210). because 420 is a multiple of 420, any number of the form x= 6 (mod 420) will satisfy the conditions but saying "x= 6 (mod 420)" misses the solution x= 216.
You are right, the "answer" is wrong.
If k and n are positive numbers, do we still need to find these general solutions (k= -2+ 7j and n= -1+ 3j)?
It depends on the exact statement of the problem. For example, "Diophantine" equations of this type often occur in puzzles where the solution are necessarily positive numbers. In that case, you would only need to give the positive solutions (and often both will be positive only for one value of j). But in general it is certainly a good idea to give the "general solution", giving all possible values that satisfy the equation.
