Results 1 to 4 of 4

Math Help - Congruence Equation

  1. #1
    Newbie
    Joined
    Dec 2006
    Posts
    6

    Congruence Equation

    I am having a little trouble with this homework question


    Find all incongruent solutions modulo 35 of the congruence
    25x = 380 (mod 35)


    I know there will be five solotions because that is the gcd

    I divided the Equation by 5 which now gives you
    5x = 76 (mod7)

    35 = 1 (25) + 10
    25 = 2 (10) + 5
    10 = 2 (5) + 0

    5= 1 (25) + -2 (10)
    = -2 (35) + 3 (35)


    After this I am not sure how to get the solutions

    Please help
    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 math_cali View Post
    I am having a little trouble with this homework question


    Find all incongruent solutions modulo 35 of the congruence
    25x = 380 (mod 35)
    \gcd(25,35)=5 which divides 380.
    Hence there are 5 incongruent solutions (algebraists say a solution in each equivalence class).

    You can solve this with a techinque but because the numbers are small we can try to "guess" what the solution is. First simplify the 380, the remainder it leaves it 30.
    Thus,
    25x\equiv 30 (\mbox{ mod }35).
    We can see that x= 4 is surly a solution.
    By a theorem all other solutions are,
    4, 4+\frac{35}{5},4+\frac{2\cdot 35}{5},4+\frac{3\cdot 35}{5}, 4+\frac{4\cdot 35}{5}
    Thus,
    4,4+7,4+14,4+21,4+28
    Which are,
    4,11,18,25,32
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2006
    Posts
    6
    Why do we guess x = 4?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by math_cali View Post
    Why do we guess x = 4?
    Because it works.
    Are you asking me is there a techinque to get the number, yes there is.
    One way is the Euclidean algorithm.
    But why do that if the numbers are small.

    Think of it this way. When you reduce a fraction by finding the common divisiors do you do it using a techinque (there is one) of do you just trial and error. You use trial and error and for the most of the time it is way faster.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 18th 2010, 06:26 AM
  2. congruence equation
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: September 2nd 2010, 06:20 AM
  3. 2^x in a congruence equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 15th 2009, 05:08 PM
  4. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 28th 2008, 05:54 PM
  5. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 15th 2006, 07:10 PM

Search Tags


/mathhelpforum @mathhelpforum