Results 1 to 6 of 6

Math Help - Congruence Help!

  1. #1
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Congruence Help!

    I feel really silly not being able to figure this out -- the problems come from a proof an example of the Chinese Remainder Theorem. I have tried multiplying and adding and subtracting and such on scrap paper but the answers simply don't make sense to me. The answer won't help me so much as a description of the method, so really any advice is appreciated!!. Thanks in advance! Oh, and take == to meant congruent to...

    1) A claim (book doesn't bother to explain why) states that all sol'ns of 7x == 1 (mod 31) satisfy x == 9 (mod 31)

    2) Another says 5t + 1 == 2 (mod 6) can be solved for t to yield t == 5(mod 6)

    3) The last one says 30u + 26 == 3(mod 7) can be solved for u to yield u == 6 (mod 7)

    The first one -- WHY?! If 31 divide 7x-1, does that mean 31 divides x-9?!

    The second one -- I don't even know what to do. Subtracting 1 from each side gets 5t == 1(mod 6). Using Euclidean Algo (or common sense), gcd(5,6)=1, and 1 = 1.6 - 1.5 so t=1 works. So 1 == 5 (mod 6). Does this mean that t == 5 (mod 6)?

    The last one I start off by subtracting 26 to get 30u == -23 (mod 7). I believe you can subtract off multiples of 7 from 20, to get 2u == -23 (mod 7) . [Is the same allowed on the right?]. Since gcd(2,7)=1 which obv divides 23, We can use 1 = 1.7 - 3.2 --> -23 = -23.7 + 69.2 so u=69. So 2(69) == -23(mod 7). But then what is u congruent to mod 7?

    AH!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Congruence Help!

    Quote Originally Posted by jsndacruz View Post
    I feel really silly not being able to figure this out -- the problems come from a proof an example of the Chinese Remainder Theorem. I have tried multiplying and adding and subtracting and such on scrap paper but the answers simply don't make sense to me. The answer won't help me so much as a description of the method, so really any advice is appreciated!!. Thanks in advance! Oh, and take == to meant congruent to...

    1) A claim (book doesn't bother to explain why) states that all sol'ns of 7x == 1 (mod 31) satisfy x == 9 (mod 31)

    2) Another says 5t + 1 == 2 (mod 6) can be solved for t to yield t == 5(mod 6)

    3) The last one says 30u + 26 == 3(mod 7) can be solved for u to yield u == 6 (mod 7)

    The first one -- WHY?! If 31 divide 7x-1, does that mean 31 divides x-9?!

    The second one -- I don't even know what to do. Subtracting 1 from each side gets 5t == 1(mod 6). Using Euclidean Algo (or common sense), gcd(5,6)=1, and 1 = 1.6 - 1.5 so t=1 works. So 1 == 5 (mod 6). Does this mean that t == 5 (mod 6)?

    The last one I start off by subtracting 26 to get 30u == -23 (mod 7). I believe you can subtract off multiples of 7 from 20, to get 2u == -23 (mod 7) . [Is the same allowed on the right?]. Since gcd(2,7)=1 which obv divides 23, We can use 1 = 1.7 - 3.2 --> -23 = -23.7 + 69.2 so u=69. So 2(69) == -23(mod 7). But then what is u congruent to mod 7?

    AH!
    1. 7x == 1 (mod 31) ==> 7x==63(mod 31) ==> x==9(mod 31)

    2. 5t + 1 == 2 (mod 6) ==> 5t == 1 (mod 6) ==> 5t==25(mod 6) ==> t==5(mod 6)

    3. Take a try...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Re: Congruence Help!

    Ahh I see.. I thought dividing was not allowed for congruences though -- unless you can divide all the way through including the modulus. Is this not true once you add the variable?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Congruence Help!

    Quote Originally Posted by jsndacruz View Post
    Ahh I see.. I thought dividing was not allowed for congruences though -- unless you can divide all the way through including the modulus. Is this not true once you add the variable?
    Properly speaking the 'division' doesn't exist in modular algebra. It is possible however the product of a number a by the 'multiplicative inverse' [if exists...] of b c= a*b^{-1}\ \text{mod}\ n , where b*b^{-1}= 1\ \text{mod}\ n. It is possible to demonstrate thet if n=p is prime, then any number a \ne 0\ \text{mod}\ p has multiplicative inverse. Let consider as example the first congruence...

    7*x \equiv 1\ \text{mod}\ 31 (1)

    Because 31 is prime, 7 has multiplicative inverse and is 7^{-1} \equiv  9\ \text{mod}\ 31 so that the solution of (1) is...

    x \equiv 9\ \text{mod}\ 31 (2)

    At this point You should be able to solve the other two problems alone!...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Re: Congruence Help!

    Thanks so much ChiSigma, that helps a lot. I can't believe I never knew about this forum! I just learned more thumbing through different discussions than I have in 3+ weeks of class.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Congruence Help!

    Quote Originally Posted by jsndacruz View Post
    Thanks so much ChiSigma, that helps a lot. I can't believe I never knew about this forum! I just learned more thumbing through different discussions than I have in 3+ weeks of class.
    Welcome to Math Help Forum jsndacruz!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: May 12th 2009, 10:19 AM
  2. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 10th 2008, 01:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 05:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 09:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 10:57 AM

/mathhelpforum @mathhelpforum