Results 1 to 9 of 9

Math Help - Solving simultaneous equations using Hensel's lemma

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    36

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by vinnie100 View Post
    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.
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2010
    Posts
    36
    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?

    Sorry about this. Thanks very much for your help Tonio.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by vinnie100 View Post
    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

    Sorry about this. Thanks very much for your help Tonio.
    .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2010
    Posts
    36
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Mar 2010
    Posts
    36
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Mar 2010
    Posts
    36
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by vinnie100 View Post
    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.
    .
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by vinnie100 View Post
    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.
    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving simultaneous equations.
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 11th 2011, 10:15 AM
  2. Hensel's Lemma
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 2nd 2011, 03:28 PM
  3. Hensel's lemma
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 11th 2010, 06:26 PM
  4. Solving simultaneous equations
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 25th 2009, 06:03 AM
  5. Solving simultaneous equations
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 21st 2008, 07:38 AM

Search Tags


/mathhelpforum @mathhelpforum