Results 1 to 5 of 5

Math Help - Congruence

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    15

    Congruence

    Hello everybody..can u help me with my problem in congruence. This is it...I've answered this one but I think it is wrong...I use euclidean algorithm 11=5(2)+1. Pls help me the true answer with this problem...thank you

    *Find a multiple of 11 that leaves a remainder of 1 when divided by each of the integers 2, 3, 5, 7.
    Last edited by manusform; October 12th 2009 at 02:41 AM. Reason: lacking of *
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by manusform View Post
    Hello everybody..can u help me with my problem in congruence. This is it...I've answered this one but I think it is wrong...I use euclidean algorithm 11=5(2)+1. Pls help me the true answer with this problem...thank you

    *Find a multiple of 11 that leaves a remainder of 1 when divided by each of the integers 2, 3, 5, 7.
    ]

    You can do it by "gentle brute force": from the conditions the multiple, let's call it x, is odd and ends either in 1 or 6 ==> it ends in 1 (why?)
    So you must concentrate on multiples of 11 ending in 1; there aren't that many: 11, 121, 231 341,...,1001, 1111, 1221, 1331, etc.
    Since it must be 1 + 3k, for some integer k, this rules out 11, 121,1001, etc.

    Of course, you could read carefully the proof of the Chinese Remainder Theorem and thus construct your number.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by tonio View Post
    ]

    You can do it by "gentle brute force": from the conditions the multiple, let's call it x, is odd and ends either in 1 or 6 ==> it ends in 1 (why?)
    So you must concentrate on multiples of 11 ending in 1; there aren't that many: 11, 121, 231 341,...,1001, 1111, 1221, 1331, etc.
    Since it must be 1 + 3k, for some integer k, this rules out 11, 121,1001, etc.

    Of course, you could read carefully the proof of the Chinese Remainder Theorem and thus construct your number.

    Tonio
    Maybe this is a better approach -

    Let the number be 11k
    Now 2|11k-1, 3|11k-1, 5|11k-1, 7|11k-1

    Thus 2.3.5.7|11k-1
    or 11k-1 = 210m
    thus 11k - 210m = 1

    We can solve this Diophantine equation using euclidean algo as (11,210) = 1.

    Am I correct in my approach please?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,453
    Thanks
    1868
    Yes, that's excellent!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by HallsofIvy View Post
    Yes, that's excellent!
    Yes - I realized I was correct after your detailed post. It helped me validate my equation.

    General solution to the Diophantine equation is of the form

    (210k-19)11 + (1-11k)210 =1 where k is any integer


    So solution to the original question is (210k-19)11, where k is any integer
    1st positive solution is when k=1, which gives 2101 like you said.

    Thanks
    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, 11:19 AM
  2. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 10th 2008, 02:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 06:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 10:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 11:57 AM

Search Tags


/mathhelpforum @mathhelpforum