Euclidean algorithm congruences

[AHW]

1)5x=1(16) is equivalent to x=5(6) is equivalent to x=1(2), x=2(3) <the equal sign here i mean congruence to>

i'm a bit confused about the equivalence...how this is so?

2)3k-7n=1, k,n integers
by using euclidean algorithm i got k=-2, n=-1. but the answer i got here is k=5, n=2
(the original question asked to solve x s.t x=1(3) and x=2(7) <the equal sign here i mean congruence to>)


any help appreciated..much thanks~

 

[HallsofIvy]

1)5x=1(16) is equivalent to x=5(6) is equivalent to x=1(2), x=2(3) <the equal sign here i mean congruence to>

i'm a bit confused about the equivalence...how this is so?

I don't know what you are talking about. If you mean congruence modulo a number, then it simply isn't true. 5(13)= 65= 64+ 1 so x= 13 (mod 16). Since 13= 7+ 6, 13 is congruent to 7 (mod 6), not 5. It does happen that 13= 6(2)+ 1 so it is congruent to 1 (mod 2), but 13= 4(3)+ 1 so it is congruent to 1 (mod 3) not 2.

2)3k-7n=1, k,n integers
by using euclidean algorithm i got k=-2, n=-1. but the answer i got here is k=5, n=2
(the original question asked to solve x s.t x=1(3) and x=2(7) <the equal sign here i mean congruence to>)

Yes, if k= -2, n= -1 satisfy that equation. But if k= -2+ 7j and n= -1+ 3j, for any j, then 3k- 7n= 3(-2+ 7j)- 7(-1+ 3j)= -6- 21j+ 7- 21j= 1 because the "21j" te4rms cancel.

In particular, if you let j= 1, k= -2+ 7= 5 and n= -1+ 3= 2. Any of the numbers k= -2+ 7j and n= -1+ 3j will satisfy the equation but numbers "modulo p" are usually represented by the equivalent value between 0 and p- 1. Here those are 5 and 2.

any help appreciated..much thanks~

 

[AHW]

Many thanks for the help~~

I don't know what you are talking about. If you mean congruence modulo a number, then it simply isn't true. 5(13)= 65= 64+ 1 so x= 13 (mod 16).

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)

but the answer is x=6(mod 420)
I don't understand why it's mod 420.

Yes, if k= -2, n= -1 satisfy that equation. But if k= -2+ 7j and n= -1+ 3j, for any j, then 3k- 7n= 3(-2+ 7j)- 7(-1+ 3j)= -6- 21j+ 7- 21j= 1 because the "21j" te4rms cancel.

If k and n are positive numbers, do we still need to find these general solutions (k= -2+ 7j and n= -1+ 3j)?

 

[HallsofIvy]

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.

 

[AHW]

Thanks again~

I've got this new question about hensel's lemma. Hope you don't mind helping again. I've come across this version of hensel's lemma, but I just can't understand what it means. I know it can lift a solution of a polynomial congruence but can't see how things work out from the definition. Can you help to explain it in plain English? Thanks~

Let f be an integral polynomial. Suppose that f(a)=0 (mod p^j), and that p^t ll f'(a). Then if j >= 2t+1, it follows that:
1)whenever b=a (mod p^j-t), one has f(b)=f(a) (mod p^j) and p^t ll f'(b):
2)these exists a unique residue t(mod p) with the property that f(a+tp^j-t) = 0 (mod p^j+1).