Results 1 to 12 of 12
Like Tree1Thanks
  • 1 Post By hollywood

Thread: Chinese Remainder Theorem

  1. #1
    Newbie
    Joined
    Oct 2018
    From
    Taiwan
    Posts
    10

    Chinese Remainder Theorem

    .




    Dear

    How to solve the CRT for cryptography as below -

    (1) Find x such that

    x = 2(mod3)
    x = 5(mod9)
    x = 7(mod11)

    (2) Find x such that

    x = 2(mod3)
    x = 4(mod7)
    x = 5(mod11)

    (3) Find x such that x^2= 26(mod77)

    (4) Find x such that x^2 = 38(mod77)

    Please help me by provide your advice and suggestion

    Prayerfully



    Tron Orino Yeong
    tcynotebook@yahoo.com
    0916643858









    .





    .




    Dear

    How to solve the CRT for cryptography as below -

    (1) Find x such that

    x = 2(mod3)
    x = 5(mod9)
    x = 7(mod11)

    (2) Find x such that

    x = 2(mod3)
    x = 4(mod7)
    x = 5(mod11)

    (3) Find x such that x^2= 26(mod77)

    (4) Find x such that x^2 = 38(mod77)

    Please help me by provide your advice and suggestion

    Prayerfully



    Tron Orino Yeong
    tcynotebook@yahoo.com
    0916643858









    .
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    Posts
    1,049
    Thanks
    280

    Re: Chinese Remainder Theorem

    In the first question, if $x\equiv 5\pmod 9$, then $x\equiv 2\pmod 3$, so you only really have two conditions. If you look on the internet, you will find an algorithm to apply the Chinese Remainder Theorem, but it has several steps and I don't think it's very intuitive. So let me give you an alternative. You have:

    $x\equiv 5\pmod 9$
    $x\equiv 7\pmod {11}$

    Since 9 and 11 are relatively prime, the answer will be given modulo 99. The first thing to do is to look at 9 and 11:

    $9\equiv 0\pmod 9$
    $9\equiv 9\pmod {11}$

    $11\equiv 2\pmod 9$
    $11\equiv 0\pmod {11}$

    If you have more than two moduli, you would look at the products of all but 1 modulus. For example, in the second problem, you have 3, 7, and 11, so you would look at 21, 33, and 77. The idea is to get zeros in all but one equation.

    The next step is to multiply by something to make the nonzero numbers 1. For example, the top one would be multiplied by 5 to get $45\equiv 1 \pmod {11}$. Since the numbers are small, you can just list the multiples of 9 and choose the one that is congruent to $1\pmod {11}$. For large numbers, you would use the Extended Euclidean Algorithm. In this case, it turns out that 5 is the number to multiply by to get 1 for both the top set of equations and the bottom set of equations.

    $45\equiv 0\pmod 9$
    $45\equiv 1\pmod {11}$

    $55\equiv 1\pmod 9$
    $55\equiv 0\pmod {11}$

    Now you have (0,1) and (1,0) so to get (5,7), you take 7 times the first set of equations and add 5 times the second set of equations.

    $590\equiv 5\pmod 9$
    $590\equiv 7\pmod {11}$

    You now reduce 590 (mod 99) to get the answer 95. Of course, you should always check your answer:

    $95\equiv 5\pmod 9$
    $95\equiv 7\pmod {11}$

    So that's the method. In problem (2), you use the same method, the only difference being you have 3 moduli to work with instead of 2.

    For problem (3),

    $x^2\equiv 26\pmod {77}$,

    since $77=7*11$, you can break it into two equations:

    $x^2\equiv 26\pmod 7$
    $x^2\equiv 26\pmod {11}$

    and reducing,

    $x^2\equiv 5\pmod 7$
    $x^2\equiv 4\pmod {11}$

    The second equation has solutions $x\equiv 2\pmod {11}$ and $x\equiv 9\pmod {11}$, but the first one has no solutions. The squares (mod 7) are 0, 1, 4, 2, 2, 4, and 1. So the system has no solutions, and therefore the original problem has no solutions, and that's our answer.

    If the problem were $x^2\equiv 15\pmod {77}$, then you would have

    $x^2\equiv 1\pmod 7$ with solutions 1 and 6
    $x^2\equiv 4\pmod {11}$ with solutions 2 and 9

    and then you would take all combinations:
    $1 \pmod 7$ and $2 \pmod {11}$ gives $x\equiv 57\pmod {77}$
    $1 \pmod 7$ and $9 \pmod {11}$ gives $x\equiv 64\pmod {77}$
    $6 \pmod 7$ and $2 \pmod {11}$ gives $x\equiv 13\pmod {77}$
    $6 \pmod 7$ and $9 \pmod {11}$ gives $x\equiv 20\pmod {77}$

    so the answer would be x is congruent to 13, 20, 57, or 64 (mod 77).

    The same process is used in problem (4). You will get zero solutions if either the (mod 7) equation or the (mod 11) equation has no solutions, or you will get 4 solutions by combining the two solutions (mod 7) with the two solutions (mod 11).

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2018
    From
    Taiwan
    Posts
    10

    Re: Chinese Remainder Theorem

    See attached file -
    Attached Thumbnails Attached Thumbnails Chinese Remainder Theorem-draft.jpg  
    Last edited by vokoyo; Oct 18th 2018 at 06:42 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Mar 2010
    Posts
    1,049
    Thanks
    280

    Re: Chinese Remainder Theorem

    The Chinese Remainder Theorem only works if the moduli are pairwise relatively prime. In problem (1), you have 3, 9, and 11, but 3 and 9 are not relatively prime.

    - Hollywood
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2018
    From
    Taiwan
    Posts
    10

    Re: Chinese Remainder Theorem

    Please check for my solution draft paper -



    Chinese Remainder Theorem-1.jpg



    Chinese Remainder Theorem-2.jpg
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,720
    Thanks
    1515

    Re: Chinese Remainder Theorem

    It appears you ignored the advice Hollywood gave you for question 1. Not surprisingly, you got a wrong answer. For example, if $k=0$ then you have $x=18$. That does not match two of the original equivalencies. I haven't checked the second one.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Mar 2010
    Posts
    1,049
    Thanks
    280

    Re: Chinese Remainder Theorem

    For the first page, please read my previous two posts.

    On the second page, everything is correct up to the very end, where you made an arithmetic error: 308 + 396 + 1050 = 1754, so the answer is 137 (mod 231).

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Oct 2018
    From
    Taiwan
    Posts
    10

    Re: Chinese Remainder Theorem

    Thank you very much

    Please help me for question (3) and question (4)

    Chinese Remainder Theorem-1.jpg

    (I need urgent assistance for this exercise)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Mar 2010
    Posts
    1,049
    Thanks
    280

    Re: Chinese Remainder Theorem

    When you're searching for $x^2 \equiv 26 \pmod 7$, instead of looking at what 26 is congruent to (26, 33, 40, ...), you should look at what x might be congruent to. There are only 7 possibilities: 0, 1, 2, 3, 4, 5, and 6. The squares (reduced mod 7) are 0, 1, 4, 2, 2, 4, and 1. But 26 is congruent to 5, so there are no solutions.

    In the original problem, $x^2 \equiv 26 \pmod {77}$, we need to find an x that solves both $x^2 \equiv 26 \pmod 7$ and $x^2 \equiv 26 \pmod {11}$. No solutions to the first part means there are no solutions to the original problem.

    You can use a similar process to solve problem (4).

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Oct 2018
    From
    Taiwan
    Posts
    10

    Re: Chinese Remainder Theorem

    Therefore how to write the formal statement in university exam answer sheet - if there is no solution
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,720
    Thanks
    1515

    Re: Chinese Remainder Theorem

    Quote Originally Posted by vokoyo View Post
    Therefore how to write the formal statement in university exam answer sheet - if there is no solution
    That is the formal answer. $\nexists x \in \mathbb{Z}$ such that $x^2 \equiv 26 \pmod{7}$. Or simply, "No solutions exist". So long as you justify your answer (as Hollywood did), you should be given full credit.

    Wolframalpha's Answer
    Last edited by SlipEternal; Oct 20th 2018 at 02:26 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Oct 2018
    From
    Taiwan
    Posts
    10

    Re: Chinese Remainder Theorem

    A million thanks to all of you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Jun 21st 2011, 07:47 AM
  2. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 4th 2011, 10:20 PM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: Jul 31st 2009, 08:34 AM
  4. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 23rd 2009, 09:26 PM
  5. chinese remainder theorem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 29th 2008, 03:20 PM

/mathhelpforum @mathhelpforum