Results 1 to 3 of 3

Math Help - find the least positive interger solution

  1. #1
    Junior Member
    Joined
    Dec 2007
    From
    University of California, Berkeley
    Posts
    48

    find the least positive interger solution

    .

    .
    Last edited by yellow4321; March 6th 2008 at 05:14 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by yellow4321 View Post
    ive been given
    x congruent 3mod4
    x congruent 13mod33
    x congruent 35mod88

    i solved to find unique solution = 211 but then it asks for find the least positive integer solution and state the largest modulus for which the solution is unique. i have no clue how to go about this?
    I would start by splitting each modulus into its distinct prime factors. So for example 88 = 811. This means that x\equiv35\pmod{88} is equivalent to
    \left\{\begin{array}{l}x\equiv35\pmod{8} \text{ and} \\ x\equiv35\pmod{11}.\end{array}\right.
    But 35\equiv3\pmod{8}, and 35\equiv2\pmod{11}.

    So the congruence x\equiv35\pmod{88} is equivalent to the two congruences
    x\equiv3\pmod{8},
    x\equiv2\pmod{11}.

    In the same way, 33 = 311, and you can check that the congruence x\equiv13\pmod{33} is equivalent to the two congruences
    x\equiv1\pmod{3},
    x\equiv2\pmod{11}.

    So instead of the three original congruences
    x\equiv3\pmod{4},
    x\equiv13\pmod{33},
    x\equiv35\pmod{88},
    we now have five congruences , namely
    x\equiv3\pmod{4},
    x\equiv3\pmod{8},
    x\equiv1\pmod{3},
    x\equiv2\pmod{11},
    x\equiv2\pmod{11}.

    But one of these occurs twice, so we can delete the duplicated one. Also, x\equiv3\pmod{8} implies x\equiv3\pmod{4}, so we only need to keep the first of these. Thus we're back to a set of just three congruences:
    x\equiv3\pmod{8},
    x\equiv1\pmod{3},
    x\equiv2\pmod{11}.

    The advantage of doing this is that we now have a system in which each modulus is (a power of) a different prime. This means that we can use the Chinese remainder theorem to complete the solution. This tells you for a start that the "largest modulus for which the solution is unique" is the product 8311=264.

    To find the solution, start by combining the first two of these three congruences. We want a number that leaves a remainder 3 when divided by 8, and a remainder 1 when divided by 3. These numbers are small enough that you should soon be able to find the solution 19. Since 38=24, this tells us that the first two congruences are equivalent to x\equiv19\pmod{24}.

    Finally, bring in the third congruence, x\equiv2\pmod{11}. Together with x\equiv19\pmod{24}, this tells us to look for a number that leaves a remainder 19 when divided by 24, and a remainder 2 when divided by 11. This is slightly more laborious, but can still be done easily enough by mental arithmetic. Start with 19, and add multiples of 24 until you reach a number that leaves a remainder 2 when divided by 11. You get 19, 43, 67, 91, ... . If you keep tabs on the remainders when you divide these numbers by 11, you'll see that they form an obvious pattern: 8, 10, 1, 3, 5, 7, 9, 0, 2. That points to the one you're looking for! It is the unique solution (mod264).
    Last edited by Opalg; January 15th 2008 at 12:57 PM. Reason: corrected small error
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2007
    From
    University of California, Berkeley
    Posts
    48
    .

    .
    Last edited by yellow4321; March 6th 2008 at 05:14 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: April 3rd 2010, 01:17 PM
  2. Number of Interger value of x and y.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 13th 2009, 10:28 PM
  3. Positive root solution
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 23rd 2009, 12:49 AM
  4. interger problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 13th 2008, 08:52 AM
  5. interger problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 8th 2008, 01:13 PM

Search Tags


/mathhelpforum @mathhelpforum