1. ## A logic question!!

hi all. here is the question:

there were 17 dogs who found a pile of bones. they decided to divide the bones equally but after they divided the bones, there was 5 extra bones left.

One dog left so there was 16 dogs left. They decided to divide up the bones again, but this time had 10 extra bones left.

Another dog left so there were 15 dogs left, when they divided up the bones again, there was 0 extra bones left.

Two questions:
1. what is the minimum number of bones in the pile?
2. what is another possible solution to the number of bones in the pile?

using brute force of multiples of 15, I found that 90 bones work and it is the smallest number possible. (if you disagree please let me know!)

what is another number of bones that can work? Also, can someone tell me how to set this question up? I am very confused. Thanks!!!!

2. Originally Posted by soyeahiknow

hi all. here is the question:

there were 17 dogs who found a pile of bones. they decided to divide the bones equally but after they divided the bones, there was 5 extra bones left.

One dog left so there was 16 dogs left. They decided to divide up the bones again, but this time had 10 extra bones left.

Another dog left so there were 15 dogs left, when they divided up the bones again, there was 0 extra bones left.

Two questions:
1. what is the minimum number of bones in the pile?
2. what is another possible solution to the number of bones in the pile?

using brute force of multiples of 15, I found that 90 bones work and it is the smallest number possible. (if you disagree please let me know!)

what is another number of bones that can work? Also, can someone tell me how to set this question up? I am very confused. Thanks!!!!
So

$\displaystyle \displaystyle x \equiv 5\ (\text{mod}\ 17)$

$\displaystyle \displaystyle x \equiv 10\ (\text{mod}\ 16)$

$\displaystyle \displaystyle x \equiv 0\ (\text{mod}\ 15)$

Since gcd(15,16,17)=1, the Chinese remainder theorem applies (see the link for a constructive algorithm). You already found a solution trough brute force; the general solution is $\displaystyle \displaystyle x \equiv 90\ (\text{mod}\ 15\cdot16\cdot17)$.

EDIT: I should have said that 15, 16, and 17 are pairwise coprime rather than gcd(15,16,17) = 1.

3. Hi, can you explain further or work the problem out for me a little more? I tried looking at Wikipedia but am confused by the example they gave. Thanks!

4. Originally Posted by soyeahiknow
Hi, can you explain further or work the problem out for me a little more? I tried looking at Wikipedia but am confused by the example they gave. Thanks!
The Chinese remainder theorem states that there is a unique solution mod N. You found the solution already through brute force and thus do not need to use the algorithm discussed in Wikipedia for this particular problem.

The complete solution set is given by x = 90 + (15*16*17)k where k ranges over all integers (actually non-negative integers since we assume that having a negative number of bones doesn't make sense). So to find another solution, use for example, k = 1.

5. Thank you!

Now so I know if I didn't do it by brute force, I would have to use the Euclidean algorithm correct? I looked up some sample problems with solutions that is where I am getting messed up on. I am not sure how that plays out. Could you shed some light on that?

6. Originally Posted by soyeahiknow
Thank you!

Now so I know if I didn't do it by brute force, I would have to use the Euclidean algorithm correct? I looked up some sample problems with solutions that is where I am getting messed up on. I am not sure how that plays out. Could you shed some light on that?
The algorithm described in the Wikipedia article involves finding modular inverses, and the typical fast algorithm for this is the extended Euclidean algorithm; also possible is modular exponentiation. For some nice pencil and paper solutions see this thread.

Here is how your problem plays out, using labels from the Wikipedia article.

$\displaystyle \displaystyle x \equiv 5\ (\text{mod}\ 17)$

$\displaystyle \displaystyle x \equiv 10\ (\text{mod}\ 16)$

$\displaystyle \displaystyle x \equiv 0\ (\text{mod}\ 15)$

N = 4080

N / 17 = 240

N / 16 = 255

N / 15 = 272

$\displaystyle \displaystyle e_1$ is (the modular inverse of 240 mod 17) multiplied by (240).

$\displaystyle \displaystyle e_2$ is (the modular inverse of 255 mod 16) multiplied by (255).

Likewise for $\displaystyle \displaystyle e_3$.

We find that

$\displaystyle \displaystyle e_1 = 9\cdot240 = 2160$
$\displaystyle \displaystyle e_2 = 15\cdot255 = 3825$
$\displaystyle \displaystyle e_3 = 8\cdot272 = 2176$

So the solution is given by (15)(2160) + (10)(3825) + (0)(2176) $\displaystyle \displaystyle \equiv$ 90 (mod N).

Note that it wasn't actually necessary to calculate $\displaystyle \displaystyle e_3$ because it just got multiplied by 0.

To explain modular inverses: The Wikipedia article says "For each i the integers $\displaystyle n_i$ and N / $\displaystyle n_i$ are coprime. Using the extended Euclidean algorithm we can find integers $\displaystyle r_i$ and $\displaystyle s_i$ such that $\displaystyle r_i$$\displaystyle n_i$ + $\displaystyle s_i$N / $\displaystyle n_i$ = 1." This means that $\displaystyle s_i$ multiplied by N / $\displaystyle n_i$ plus a multiple of $\displaystyle n_i$ equals 1; in other words, $\displaystyle s_i$ is the modular inverse of N / $\displaystyle n_i$ mod $\displaystyle n_i$.

So for $\displaystyle \displaystyle e_1$ we need to find the modular inverse of 240 mod 17. This is the same as the modular inverse of 2 mod 17. I'll use simplependulum's method from this thread:

$\displaystyle [2^{-1}] = [\frac{1}{2}] = \frac{[9]}{[18]} = [9]$

Now for the modular inverse of 255 mod 16, which is the modular inverse of 15 mod 16.

$\displaystyle [15^{-1}] = [\frac{1}{15}] = \frac{[1]}{[-1]} = \frac{[-1]}{[1]} = [-1] = [15]$

7. Thanks!