Results 1 to 5 of 5

Math Help - Help with understanding congruence problems

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    12

    Help with understanding congruence problems

    Hello,

    I am just starting out with Number Theory and am struggling to work out congruence problems.

    Im sure this one will be easy for most of you, but can you please quickly walk me through it?

    3956x \equiv 7 (mod 2351)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by Banana1 View Post
    Hello,

    I am just starting out with Number Theory and am struggling to work out congruence problems.

    Im sure this one will be easy for most of you, but can you please quickly walk me through it?

    3956x \equiv 7 (mod 2351)

     3956 \cdot x \equiv 7 \, mod(2351)

    means

    3956x = 7 + 2351k

    3956 times some number(x) is equal to 7 + 2351 times someother number(k)

    The following shows how to find the value of x and the value of k.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2009
    Posts
    12
    Can anyone actually get the answer for this? Ive been playing around with it for ages and cant get it out.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Do you know the Chinese remainder theorem?
    I'm not very good at calculation, so perhaps this method is not optimal. But that's how I'd do it.

    Notice that if you find a solution to the system

    y \equiv 7 \mod 2351
    y \equiv 0 \mod 3956

    Then x=y/3956 is a solution to your original system (can you see why?).
    Since 3956, 2351 are coprime, the Chinese remainder theorem guarantees the existence of a solution; you can determine it fairly easily using the Euclidean algorithm.

    Give this a try and report back if you still can't do it.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by Banana1 View Post
    Hello,

    I am just starting out with Number Theory and am struggling to work out congruence problems.

    Im sure this one will be easy for most of you, but can you please quickly walk me through it?

    3956x \equiv 7 (mod 2351)
    SIDE NOTE:
    If you "Preview Post" and it looks ok, but
    you exit before you "Submit Reply" then
    all of the stuff you did for the preview will
    evaporate (and no one will know of it).

    What I intended to include:
    1st step
    We are looking for the modular inverse of
    3956 and 2351. {ax + by = 1}
    3956*x + 2351*y = 1
    which will be equivalent to
    3956*x  \equiv 1 mod 2351

    Finding the inverse is just about as easy as finding the GCD
    This is a very simple method to compute the modular inverse. If you end with a zero (in the r column) you will have the GCD(a,b) of ax+by
    This is a very easy procedure to learn & use.
    You may need additional comments if it is not clear.
    Code:
     
    Here the asterisk(*) means multiplication
    Eqn      a *    x  +    b *    y  =     r    Operation 
    [ 1]  3956 *    1  + 2351 *    0  =  3956    [1]Equation  
    [ 2]  3956 *    0  + 2351 *    1  =  2351    [2]Equation
    Equations [1] & [2] establish the initial values of x & y 
    Equation [3] = Equation [1] minus Equation [2]
    [ 3]  3956 *    1  + 2351 *   -1  =  1605    [1]-[2]
    [ 4]  3956 *   -1  + 2351 *    2  =   746    [2]-[3] 
    [4a]  3956 *   -2  + 2351 *    4  =  1492    [4]*2 = [4a]
    Eq[4a] is short version of multiple subtractions of Eq[4] minus Eq[3]
    [ 5]  3956 *    3  + 2351 *   -5  =   113    [3]-[4a] 
    [5a]  3956 *   18  + 2351 *  -30  =   678    [5]*6=[5a]
     (see 4a note)
    [ 6]  3956 *  -19  + 2351 *   32  =    68    [4]-[5a] 
    [ 7]  3956 *   22  + 2351 *  -37  =    45    [5]-[6] 
    [ 8]  3956 *  -41  + 2351 *   69  =    23    [6]-[7] 
    [ 9]  3956 *   63  + 2351 * -106  =    22    [7]-[8] 
    [10]  3956 * -104  + 2351 *  175  =     1    [8]-[9]
    3956*(-104) + 2351*175 = -411424 + 411425 = 1
    so
    3956*(-104)  \equiv 1 mod 2351
    since -104 is equivalent to (2351 - 104) mod 2351 it is 2247
    3956*2247  \equiv 1 mod 2351

    2nd step
    We actually need  3956 x \equiv 7 mod(2351)

    which requires a multiply by 7
     3956 (-104 \times 7) \equiv 7 mod(2351)

    -104 x 7 = -728;
    2351 - 728 = 1623

    Thus:
     3956 \times 1623 = 6420588 = 7 + 2351 \times 2731 = 7 mod(2351)

    There are dozens of ways to calculate the modular inverse (& you can find almost all of them on the internet).
    Review the algorithm above for computation of the Modular Inverse.
    For pencil/paper this is the easiest procedure I have found that I can readily recall and use.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. some of congruence problems
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 16th 2011, 05:28 AM
  2. Congruence Problems
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 18th 2010, 11:30 PM
  3. Congruence problems
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 26th 2010, 07:30 PM
  4. Help With Congruence Problems
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 23rd 2009, 11:05 AM
  5. Congruence problems
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 11th 2009, 12:15 PM

Search Tags


/mathhelpforum @mathhelpforum