Results 1 to 5 of 5

Math Help - Modular Arithmetic- brain teezer- finding x

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    5

    Modular Arithmetic- brain teezer- finding x

    HeY ppl! I have a senario I need to solve but need some help from you guyz! I'm at like step 2!

    The senario is: A band of 17 pirates stole a sack of coins. When they tried to divide them equally among them, 3 coins remained. In the brawl that followed, one pirate was killed. Again, they tried to divide the coins equally among themselves only to find 10 coins remaining. Another pirate was killed! Now, upon dividing the coins, none was left. What is the minimum number of coins that the pirates could have been distributing.

    So far all i know is that you use the Chinese Remainder theorem and you get a set of equations... ->
    x = 3mod17
    x = 10mod16
    x = 0mod15

    Anyone know how to solve this?!
    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 carmz View Post
    x = 3mod17
    x = 10mod16
    x = 0mod15
    I like to do these problems without using Chinese Remainder Theorem. Watch how.

    Look at 2nd and 3rd equations. Add modulos 17 to first congruence seven times. And add modulos 16 to second congruence seven times. We get,
    x\equiv 122(\bmod 17)
    x\equiv 122(\bmod 16)
    Since \gcd(16,17)=1 we can combine and get,
    x\equiv 122(\bmod 272)

    Thus, we are left with simply,
    x\equiv 122(\bmod 272) (1)
    x\equiv 0(\bmod 15) (2)

    Look at (1) subtract the modulos 272 once and with (2) subtract modulos 15 ten times, to get,

    x\equiv -150(\bmod 272)
    x\equiv -150(\bmod 15)

    Since \gcd(272,15)=1 we can combine to get,
    x\equiv -150(\bmod 4080)\implies x\equiv 3930(\bmod 4080)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2008
    Posts
    5
    How did you get the 122? And how did u know to add modulos 17 to first congruence and modulos 16 to second congruence exactly seven times? And thanks for helping with this btw! Ur a genius lolz!
    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 carmz View Post
    How did you get the 122? And how did u know to add modulos 17 to first congruence and modulos 16 to second congruence exactly seven times? And thanks for helping with this btw!
    The thing is adding a modulus does not change the congruence.
    If x\equiv 3(\bmod 17) then x\equiv 3 + 17 (\bmod 17) also, and so x\equiv 3 + 2\cdot 17(\bmod 17). Thus, the point is you can keep on adding that modulos as much as you want without changing the congruence.

    We had,
    x\equiv 3(\bmod 17)
    x\equiv 10(\bmod 16)

    Your goal is to add to the first congruence 17 and 16 to the second enough times so that the numbers match. The problem is of course figuring out how many times to do it.

    The first step is to gaze at the problem. Maybe you can mentally figure out how to do it, either by adding or subtracting. In this case it is not so clear.

    If that fails I recommend to do it algebraically. Suppose you are adding 17 x times and 16 [/tex]y[/tex] times. We want that 3+17x = 10+16y \implies 17x - 16y = 7. Now we need to find values x,y (integers) which make this true. This is a linear Diophantine equation (did you study those). Note 17(1) - 16(1) = 1\implies 17(7) - 16(7) = 6. Thus, x=7 and y=7. And there, you go it.

    The second times after I combined the congruences and was left with just two I was able to see mentally. Which saves times. And then you combine them and get your answer.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,707
    Thanks
    627
    Hello, carmz!

    This can be solved with ordinary algebra . . . and some imagination.


    A band of 17 pirates stole a sack of coins.
    When they tried to divide them equally among them, 3 coins remained.
    In the brawl that followed, one pirate was killed.
    Again, they tried to divide the coins equally among themselves and found 10 coins remaining.
    Another pirate was killed! Now, upon dividing the coins, none was left.
    What is the minimum number of coins that the pirates could have been distributing?
    Let N = original number of coins.

    We know that: . N \;=\;17a + 3\:\text{ for some integer }a \;\;{\color{blue}[1]}.

    . . . . and that: . N \;=\;16b + 10\:\text{ for some integer }b\;\;{\color{blue}[2]}

    . . . . and that: . N \;=\;15c\:\text{ for some integer }c\;\;{\color{blue}[3]}


    Equating [3] and [2]: . 15c \:=\:16b + 10 \quad\Rightarrow\quad c \:=\:\frac{16b+10}{15} \:=\:b + \frac{b+10}{15}

    Since c is an integer, b + 10 is a multiple of 15: . b+10\:=\:15k\quad\Rightarrow\quad b \:=\:15k-10

    . . Substitute into [2]: . N \:=\;16(15k-10) + 10 \quad\Rightarrow\quad N\;=\;240k -150\;\;{\color{blue}[4]}


    Equating [1] and [4]: . 17a + 3 \:=\:240k - 150\quad\Rightarrow\quad a \:=\:\frac{240k - 153}{17} \:=\:14k - 9 + \frac{2k}{17}

    Since a is an integer, k is a multiple of 17.
    . . The least value is: . k \,=\,17


    Substitute into [4]: . N \;=\;240(17) - 150 \quad\Rightarrow\quad \boxed{N\;=\;3930}

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Arithmetic Modular help!!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 24th 2010, 08:44 AM
  2. Modular arithmetic HELP!!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 16th 2009, 12:02 PM
  3. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 2nd 2009, 12:17 PM
  4. Modular arithmetic help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 4th 2008, 08:47 AM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 28th 2008, 12:29 AM

Search Tags


/mathhelpforum @mathhelpforum