Results 1 to 10 of 10

Math Help - Modulo equation

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    30

    Modulo equation

    Here's the question:

    Determine the value of  \ x \ , \ 0 \leq x < 15, if x satisfies:

    x \equiv 2 \ (\mathrm{mod} \ 3)
    x \equiv 4 \ (\mathrm{mod} \ 5)
    From these congruences, I can write

    \frac {x-2}{3} = k \ , \ k \in \mathbb{Z}

    \frac {x-4}{5} = p \ , \ p \in \mathbb{Z}

    From which we get that

    x = 3k + 2

    x = 5p + 4

    Ergo,

    3k + 2 = 5p + 4

    Now, I managed to find different values for p and k through trial and error so that the left side and right side of the equation become the same number (which is 14). And that's the answer for the question.

    But my question is: isn't this possible to do algebraically or at least numerically rather than through trial and error?

    Correct me if I am wrong; but isn't this a Diophantine equation which has to be solved with Euclides algorithm?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Modulo equation

    More specifically it's an example of the Chinese remainder theorem.
    Chinese remainder theorem - Wikipedia, the free encyclopedia

    And yes, this involves the extended Euclidean algorithm.
    The wiki page contains an algorithm and an example of how it works.

    The solution in your case is simple enough not to need the Euclidean algorithm though:

    x \equiv 2 \cdot 5 \cdot [5^{-1}]_3 + 4 \cdot 3 \cdot [3^{-1}]_5 \pmod{3 \cdot 5}

    x \equiv 2 \cdot 5 \cdot 2 + 4 \cdot 3 \cdot 2 \pmod{15}

    x \equiv 14 \pmod{15}
    Last edited by ILikeSerena; December 24th 2011 at 03:12 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2011
    Posts
    30

    Re: Modulo equation

    I did not understand what you did there.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Modulo equation

    In the wiki article there is a section about the case of two equations:
    Chinese remainder theorem - Case of two equations - Wikipedia, the free encyclopedia

    The equations:
    have the solution:
    which is \pmod{n_1 \cdot n_2},
    and which assumes that n_1 and n_2 are coprime.


    I substituted the values from your equations.

    In particular [5^{-1}]_3 represents the inverse of 5 (mod 3).
    This is the number that multiplied by 5 yields 1 (mod 3).

    Since:
    5 \cdot 2 \equiv 10 \equiv 1 \pmod 3
    we conclude that:
    5^{-1} \equiv 2 \pmod 3
    Last edited by ILikeSerena; December 24th 2011 at 03:11 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2011
    Posts
    30

    Re: Modulo equation

    Hmm, okay.

    But, could you please thoroughly show me the Diophantine/Euclides algorithm approach? Thx!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Modulo equation

    I think you mean the Chinese remainder theorem/Euclidean algorithm approach?

    Well, I recommend you read the wiki article.
    It explains it much better than I can.

    If you have questions, perhaps I can answer those...?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2011
    Posts
    30

    Re: Modulo equation

    I just want to know how I can solve this "equation"

    3k + 2 = 5p + 4

    when considering it as a linear Diophantine equation.

    Now, the Euclidean algorithm is used for calculating the greatest common factor here. But how is that useful and how is it actually used in equations like these?

    So, I would appreciate it if you could show me the procedure of using the Euclidean algorithm in order to find a value for x?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Modulo equation

    here is an equivalent approach. it may seem mysterious why this works, but it really is just the chinese remainder theorem in disguise.

    x = 2 (mod 3)
    x = 4 (mod 5).

    therefore, since gcd(3,5) = 1:

    5x = 10 (mod 15)
    3x = 12 (mod 15), so:

    8x = 22 = 7 (mod 15).

    so 2(8x) = 2(7) = 14 (mod 15)
    16x = x = 14 (mod 15) (because 16 = 1 mod 15).

    the question in your mind should be, how did i know to multiply by 2? well, gcd(8,15) = 1, so 8 is invertible (mod 15). finding the inverse of 8 involves the euclidean algorithm, and for a larger modulus, i would have to use it, but 15 is a pretty small modulus, and the only possible inverses for 8 are 1,2,4,7,8,11,13 and 14.

    the point is, you need to study how integers mod n behave in more depth. the divisors of n MATTER. congruences mod 6 are going to be less user-friendly than congruences mod 7 (it is possible to write down equations which simply cannot be solved mod 6). the numbers co-prime to n matter, they are the only ones we can safely "undo" multiplication by.

    2x = 5 (mod 6) has no solution. why? because gcd(2,6) IS NOT 1.

    to the general case:

    if x = a (mod m) and x = b (mod n), and gcd(m,n) = 1, then:

    nx = na (mod mn) and mx = mb (mod mn). if we add these two equations, we get:

    (m+n)x = na + mb (mod mn). now this has a (unique) solution iff gcd(m+n,mn) = 1.

    suppose gcd(m+n,mn) ≠ 1, say it was d instead. let p be some prime dividing d.

    since p divides d, which divides mn, p divides mn, and since gcd(m,n) = 1, p divides either m or n (but not both).

    so p cannot possibly divide m+n (if p divides m, then n = (m+n) - m. if p divided both of these, it would divide n, too

    a similar argument holds if p divides n). so if there is any prime which divides d, we get a contradiction.

    so gcd(m+n,mn) = 1. so m+n is invertible mod mn.

    this gives us the solution x = (m+n)^(-1)(na + mb) (mod mn).

    although this "looks" different, it really is the same answer.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Modulo equation

    Quote Originally Posted by SweatingBear View Post
    I just want to know how I can solve this "equation"

    3k + 2 = 5p + 4

    when considering it as a linear Diophantine equation.

    Now, the Euclidean algorithm is used for calculating the greatest common factor here. But how is that useful and how is it actually used in equations like these?

    So, I would appreciate it if you could show me the procedure of using the Euclidean algorithm in order to find a value for x?
    Well, your example is perhaps too simple to illustrate the extended Euclidean algorithm, but here goes.

    First I'll rewrite your equation to -5x + 3y = 2.

    With the extended Euclidean algorithm we find x and y, such that -5x + 3y = gcd(5,3) = 1.

    To this end we iterate through a sequence of -5x_i + 3y_i = d_i, ending in d_i=0

    For the setup we start with x_1=1, y_1=0, x_2=0, y_2=1.
    Code:
    i   -5x_i + 3y_i = d_i   q_i
    1      1      0    -5     
    2      0      1     3    -2
    In each iteration we divide d_{i-1} by d_i to find the quotient q_i.
    In the first step that gives a quotient of -2.

    Then we subtract q_i times the equation from the previous step.
    Code:
    i   -5x_i + 3y_i = d_i   q_i
    1      1      0    -5     
    2      0      1     3    -2
    3      1      2     1     3
    4                   0
    That is:
    x_{i+1}=x_{i-1} - q_i x_i
    y_{i+1}=y_{i-1} - q_i y_i
    d_{i+1}=d_{i-1} - q_i d_i
    This is repeated until we hit zero, which already happened at step 4.


    Now we've found in step 3 that:
    -5 \cdot 1 + 3 \cdot 2 = 1
    Multiply the entire equation by 2 to find:
    -5 \cdot 2 + 3 \cdot 4 = 2
    which is the solution you requested.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Modulo equation

    Let's try this again:

    You have -5p+3k=2 for which you want to find integers p and k.

    We start with:
    -5 \cdot 1 + 3 \cdot 0 = -5
    -5 \cdot 0 + 3 \cdot 1 = 3

    Dividing -5 by 3 gives 2 with remainder 1.
    So we add the second equation times 2 to the first equation:

    \begin{matrix}-5 \cdot 1 + 3 \cdot 0 &=& -5 & \\ -5 \cdot 0 + 3 \cdot 1 &=& 3 & \qquad \times 2 + \\ \hline \\ -5 \cdot 1 + 3 \cdot 2 &=& 1 & \end{matrix}

    This is the lowest value we can get for the right hand side.
    Since we need a right hand side of 2, we multiply by 2:
    -5 \cdot 2 + 3 \cdot 4 = 2

    In your original equation, you had x=3k+2.
    So your solution is x=3 \cdot 4+2=14
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modulo
    Posted in the Calculus Forum
    Replies: 3
    Last Post: November 21st 2010, 05:13 PM
  2. Modulo
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 7th 2010, 05:14 PM
  3. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  4. Modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 23rd 2008, 04:04 AM
  5. CNT - Modulo
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 9th 2007, 11:30 PM

Search Tags


/mathhelpforum @mathhelpforum