Thread: Solving simultaneous equations using Hensel's lemma

1. Solving simultaneous equations using Hensel's lemma

I just had an exam today. The question asked:

Solve the following simutaneous system of congruences:

(i) x^2 is congruent to 3 (mod 5^3)
and x^2 is congruent to 6 (mod 7).

I got that each of them had no solutions. Is that correct?

(ii) y^3 is congruent to 3 (mod 5^3)
and y is congruent to 1 mod 4.

I got that then y is congruent to 87 (mod 5^3)
and y is congruent to 1 mod 4.

But then I got stuck a bit. Now gcd (5^3, 4) = 1. So by applying the Chinese Remainder Theorem I got such a random answer which I just left unmultiplied in the end.

Was ALL this the correct idea/answers I have given. As I would quite like to know if I got it all right as my grade massively depends on this question!

Thanks for your help.

2. Originally Posted by vinnie100
I just had an exam today. The question asked:

Solve the following simutaneous system of congruences:

(i) x^2 is congruent to 3 (mod 5^3)
and x^2 is congruent to 6 (mod 7).

I got that each of them had no solutions. Is that correct?

Correct, though it is enough that one of them has no solutoion for the whole system to not have soltuion.

(ii) y^3 is congruent to 3 (mod 5^3)
and y is congruent to 1 mod 4.

I got that then y is congruent to 87 (mod 5^3)
and y is congruent to 1 mod 4.

But then I got stuck a bit. Now gcd (5^3, 4) = 1. So by applying the Chinese Remainder Theorem I got such a random answer which I just left unmultiplied in the end.

I don't understand you: certainly $87^3=3\!\!\!\pmod{125}\,,\,\,but\,\,\, 87\neq 1\!\!\!\pmod 4$ , so you still haven't found a solution to this sytem...

Since the number has to end in 7 so have a chance to fulfill both conditions, you still have to check 97, 107 and 117...and none of them fits, so again there's no solution here.

Tonio

Was ALL this the correct idea/answers I have given. As I would quite like to know if I got it all right as my grade massively depends on this question!

Thanks for your help.
.

3. oh ok I see now

Hmm (ii) was out of 9 marks....since I found y must be congruent to 87 (mod 5^3) and although what I did afterwards was wrong, and since the step afterwards is really short, do you think I can get 6/7 marks out of the 9?

4. Originally Posted by vinnie100
oh ok I see now

Hmm (ii) was out of 9 marks....since I found y must be congruent to 87 (mod 5^3) and although what I did afterwards was wrong, and since the step afterwards is really short, do you think I can get 6/7 marks out of the 9?

This kind of questions drives me nuts......how in the world can I know? It all depends on your teacher , in what she/he considers more and less important...
One thing is sure: claiming that $87=1\!\!\!\pmod 4$ can be seen by some as a rather ugly mistake, so it may cost some good points.
You better wait...and hope.

Tonio

.

5. Hey thanks Tonio

Though hmm now is there a chance I could be right?
On the top of pg 16 on here: http://www.warwick.ac.uk/~maseap/tea...t/ntnotes1.pdf

the Chinese Remainder Theorem is outlined.

So I had got y is congruent to 87 mod 125
y is congruent to 1 mod 4

Then I wrote that 125 = (31x4) + 1.
4= (4x1) + 0
Therefore gcd(125, 4) = 1.
1 = 5^3 - (31 x 4)
So let u = 5^4
v = -31x4

Then u is congruent to 1 mod 4 and 0 mod 5
And v is congruent to 1 mod5 and 0 mod 4.

Therefore the values of y solving the simultaneous congruences 87 mod 125
and 1 mod 4 are:
y congruent to (87 x (-31x4)) + (1x 5^4) [mod (5^3x4)].

That was the answer I wrote down as my final answer because of the top of page 16.

Sorry to bring this up again - but surely this must work. Since the question specifically asked:
'Solve the following system of congruences: y^3 is congruent to 3 (mod 5^3) and y is congruent to 1 (mod 4)'
which I think is the exact same question as on top of pg 16 except first we have to use Hensel's lemma to reduce y^3 congruent to (mod p^k) to y congruent to (mod p^k) and then surely we can apply top of pg 16???

Sorry Tonio for not putting this down earlier. I would be really grateful if you could check. Thanks very much.

6. Also I just wrote in the exam

y congruent to (87 x (-31x4)) + (1x 5^4) [mod (5^3x4)]

without expanding it as I feel that should have been enough?

But that is if my post about is right.
Thanks.

7. http://www.warwick.ac.uk/~maseap/tea...nt/assign3.pdf

And Qu1a on the above exercise sheet has x congruent to 7 (mod 13)
and x congruent to 2 mod 16.

So then by your argument, since 7 is not congruent to 2 mod 16, there are no solutions??? but i went through this before in a seminar and it had solutions so hmm am confused now. Sorry for the trouble.
Thanks very much.

8. Originally Posted by vinnie100
http://www.warwick.ac.uk/~maseap/tea...nt/assign3.pdf

And Qu1a on the above exercise sheet has x congruent to 7 (mod 13)
and x congruent to 2 mod 16.

So then by your argument, since 7 is not congruent to 2 mod 16, there are no solutions???

You really look confused: what argument of mine allows you to deduce what you wrote above?? In fact this system has a pretty easy solution: $x=98$ ...

Tonio

but i went through this before in a seminar and it had solutions so hmm am confused now. Sorry for the trouble.
Thanks very much.
.

9. Originally Posted by vinnie100
Hey thanks Tonio

Though hmm now is there a chance I could be right?
On the top of pg 16 on here: http://www.warwick.ac.uk/~maseap/tea...t/ntnotes1.pdf

the Chinese Remainder Theorem is outlined.

So I had got y is congruent to 87 mod 125
y is congruent to 1 mod 4

Then I wrote that 125 = (31x4) + 1.
4= (4x1) + 0
Therefore gcd(125, 4) = 1.
1 = 5^3 - (31 x 4)
So let u = 5^4
v = -31x4

Then u is congruent to 1 mod 4 and 0 mod 5
And v is congruent to 1 mod5 and 0 mod 4.

Therefore the values of y solving the simultaneous congruences 87 mod 125
and 1 mod 4 are:
y congruent to (87 x (-31x4)) + (1x 5^4) [mod (5^3x4)].

That was the answer I wrote down as my final answer because of the top of page 16.

I really have not much idea what you've done above (based on your OP...I sure understand what you're doing ), and this is one of the worst things that can happen to one of my students (which you are not...fortunately!), since if I don't understand something I dismiss it and that student's grade goes on holiday to Bahamas...

It seems to be that you're saying that $y=(87 \cdot (-31\cdot4)) + (1\cdot 5^4)=-10,163$ is a solution to the above system, and it indeed is (what does the "mod (5^3x4)" means, anyway? The solution must be an integer, not some integer modulo something!)

What you probably meant is that the solution must be any integer satisfying $y=-10,163\!\!\!\pmod{125\cdot 4=500}$ , which of course is correct, and then you can take, for example, the solution $y=-10,163+21\cdot 500=337$ , which is, imo, nicer and positive.

So...? It was you that said that $y=87$ is a solution, and I didn't check your work, so based in what you said I told you that it can't be since $87\neq 1\!\!\!\pmod 4$ ...After that I assumed you checked all the other possibilities and since 97, 107 and 117 didn't work then there's no solution.

Certainly , since $(125,4)=1$ one can try the CRT...but you didn't even mention the CRT until your last messages! You only mentioned Hensel's lemma, which is a nice, powerful, tool,and what you did above is the algorithm to use based in Euclides' algorithm...

Good, so you found the general solution to the system $y^3=3\!\!\!\pmod{125}\,,\,y=1\!\!\!\pmod 4$ , and you must have written that it is any integer of the form $y=-10,163=337\!\!\!\pmod{500}$

Tonio

Sorry to bring this up again - but surely this must work. Since the question specifically asked:
'Solve the following system of congruences: y^3 is congruent to 3 (mod 5^3) and y is congruent to 1 (mod 4)'
which I think is the exact same question as on top of pg 16 except first we have to use Hensel's lemma to reduce y^3 congruent to (mod p^k) to y congruent to (mod p^k) and then surely we can apply top of pg 16???

Sorry Tonio for not putting this down earlier. I would be really grateful if you could check. Thanks very much.
.