Results 1 to 8 of 8

Math Help - Problem with basic Linear Congruence

  1. #1
    Junior Member
    Joined
    Aug 2007
    Posts
    28

    Problem with basic Linear Congruence

    Hi, I'm trying to find all solutions to the equation 4871x=(mod7642) (congruent with).

    Using the euclidian algorithm on these numbers i get, 1 = 615 * 4871 - 392 * 7642. (Writing 1 as a linear combination of the two numbers),

    Now this is a solution to the equation 4871x = 1 + 7642k. with x = 615 being 1 solution.

    The solution in the answers simply states "a solution to the original congruence is given by 7 x 615 = 4305. As gcd(4871,7642)=1 the solution will be unique modulo 7615 and all solututions are given by x = 4305 (mod 7642)"

    I do not understand this solution at all?, Why are we choosing to multiply "x" by 7? Where does the 7615 come from??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by BruceBronson View Post
    Hi, I'm trying to find all solutions to the equation 4871x=(mod7642) (congruent with).
    There are several ways to approach this. One is with the Chinese Remainder Theorem. But I cannot help you because you do not say what 4871x is congruent to.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2007
    Posts
    28
    Quote Originally Posted by ThePerfectHacker View Post
    There are several ways to approach this. One is with the Chinese Remainder Theorem. But I cannot help you because you do not say what 4871x is congruent to.
    4871x Is Congruent with (mod7642)

    I'm not familiar with the Chinese remainter theorm, i was trying to turn it into a linear diophantine equation and solve it that way. can you please help?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,842
    Thanks
    320
    Awards
    1
    Quote Originally Posted by BruceBronson View Post
    4871x Is Congruent with (mod7642)
    In order for a number to be "congruent" you need to specify what number it is congruent to. To put this in more familiar terms you are saying something on the order that "4871x = " and you aren't completing the RHS of the equation.

    For example, you could potentially solve your stated problem by saying that "4871x is congruent to 1234 (mod 7642)." If you want to say that 4871x is divisible by 7642 then you say "4871x is congruent to 0 (mod 7642)."

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2007
    Posts
    28
    Quote Originally Posted by topsquark View Post
    In order for a number to be "congruent" you need to specify what number it is congruent to. To put this in more familiar terms you are saying something on the order that "4871x = " and you aren't completing the RHS of the equation.

    For example, you could potentially solve your stated problem by saying that "4871x is congruent to 1234 (mod 7642)." If you want to say that 4871x is divisible by 7642 then you say "4871x is congruent to 0 (mod 7642)."

    -Dan
    Sorry 4871x is congruent with 1 Mod 7642,

    I just assumed if theres nothing there it assumes "1"
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by BruceBronson View Post
    Sorry 4871x is congruent with 1 Mod 7642,

    I just assumed if theres nothing there it assumes "1"
    4871x \equiv 1 (\bmod 7642)
    Means,
    7642|(4871x - 1)
    And this means,
    4871x - 1 = 7642z for some z\in \mathbb{Z}.
    This means,
    4871x + 7642 y = 1 where y=-z.
    Let us find the smallest positive integral which solves this for x.

    First use die Euclidean algorithm.
    7642 = 1\cdot 4871 + 2771
    4871 = 1\cdot 2771 + 2100
    2771 = 1\cdot 2100 + 671
    2100 = 3\cdot 617 + 87
    617 = 7\cdot 87 + 8
    87 = 10\cdot 8 + 7
    8 = 1\cdot 7 + 1
    7 = 7\cdot 1 + 0

    Now continue.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Aug 2007
    Posts
    28
    Quote Originally Posted by ThePerfectHacker View Post
    4871x \equiv 1 (\bmod 7642)
    Means,
    7642|(4871x - 1)
    And this means,
    4871x - 1 = 7642z for some z\in \mathbb{Z}.
    This means,
    4871x + 7642 y = 1 where y=-z.
    Let us find the smallest positive integral which solves this for x.

    First use die Euclidean algorithm.
    7642 = 1\cdot 4871 + 2771
    4871 = 1\cdot 2771 + 2100
    2771 = 1\cdot 2100 + 671
    2100 = 3\cdot 617 + 87
    617 = 7\cdot 87 + 8
    87 = 10\cdot 8 + 7
    8 = 1\cdot 7 + 1
    7 = 7\cdot 1 + 0

    Now continue.
    Thats exactly what i did, now i get x=615. But the solution multiplies this by 7 to give x=4035 as a unique solution. Why is this multiplied by 7? It also says this solution is "unique modulo 7615" Is this definetly a mistake?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2007
    Posts
    21
    Alright--I am no Number Theorist, but here's my reasoning:

    Now this is a solution to the equation 4871x = 1 + 7642k. with x = 615 being 1 solution.
    True! However, when you solved GCD(7642, 4871), it equaled 7. Not 1.


    Therefore, when you used Euclidean's Algorithm...

    Using the euclidian algorithm on these numbers i get, 1 = 615 * 4871 - 392 * 7642. (Writing 1 as a linear combination of the two numbers)
    ...you wrote the linear combination as if GCD(7642, 4871)=1

    As you solved, and as I restated above, this GCD is equal to 7, not 1.

    Generally, when you use the Euclidean Algorithm, you assume it is equal to 1, but then adjust it, so that the final equation is equal to the GCD (in this case 7).

    Therefore:
    1 = 615 * 4871 - 392 * 7642 (with GCD=1)
    (7 * 1) = [(7 * 615) * 4871] - [(7 * 392) * 7642] (with GCD=7)

    A simple multiplication of both sides of the equation by 7 'corrects' the equation.


    To answer your second (original) question, I feel '7615' is a typo.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Basic Linear Algebra Problem
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: January 14th 2011, 11:20 AM
  2. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 24th 2010, 05:11 AM
  3. Basic Linear Problem Solving Qn.
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 6th 2010, 06:51 PM
  4. Linear congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 1st 2009, 05:48 AM
  5. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 3rd 2008, 10:04 AM

Search Tags


/mathhelpforum @mathhelpforum