Question

An eccentric baseball card collector wants to distribute her collection among her descendants. If she divided her cards among her 17 great-great-grandchildren, there would be three cards left over. If she divided her cards among her 16 great-grandchildren, there would be 10 cards left over. If she divided her cards among her 11 grandchildren, there would be 4 cards left over. If she divided her cards among her 7 children, there would be no cards left over.

What is the smallest possible number of cards in her collection?

Answer 1

tried anything yet ?

Answer 2

No, not really, but I'm guessing I need to solve this with mods?

Answer 3

Let \(x\) = number of cards
set up four congruences and solve \(x\)

\[x\equiv 3\pmod{17}\\~\\x\equiv 10\pmod{16}\\~\\x\equiv 4\pmod{11}\\~\\x\equiv 0\pmod{7}\]

Answer 4

Should I substitute? like \[x=17x+3=16x+10\] or something?

Answer 5

and \[x=11x+4=7x\]Well they have to have different variables right?

Answer 6

also notice starting from bottom makes it easy, start with x = 7k
you may use congruence properties instead

Answer 7

so \[x=7k\]\[x=11a+4\]\[x=16b+10\]\[x=17c+3\]?

Answer 8

looks good, but i prefer working with congruences as they are simpler

Answer 9

anyways, as u can see u can work it exact same way as we did in the previous problem

simply plugin x=7k in second equation and solve k

Answer 10

so \[x=7k=11a+4\]?
How would you do it with congruences?

Answer 11

\[7k\equiv 4\pmod{11}\]

heard of "inverses" ?

Answer 12

what is the inverse of 7 in mod 11 ?

Answer 13

it's 8

Answer 14

google chinese remainder theorem and you will get a method for solving this

Answer 15

8 is your answer medal me plzz

Answer 16

it's not..

Answer 17

\[7k\equiv 4\pmod{11}\]

multiply the inverse of 7 both sides and solve \(k\)

Answer 18

like k\[k≡32 (\mod11)\]?

Answer 19

Yes, which is same as \(k \equiv 10 \pmod{11}\)

Answer 20

same as \(k = 11t + 10\)
so \(x = 7k = 7(11t+10)=77t+70\)

Answer 21

plug that in next congruence and solve \(t\)

Answer 22

What do you mean by the next congruence?

Answer 23

http://gyazo.com/9a268d4a77b190da48ffd1748ca13f10

Answer 24

from the first two congruences we have
\[x=77t+70\]
plug this in third congruence and solve \(t\)

Answer 25

The next congruence is \[x=16b+10\]

Answer 26

\(x = 16b+10\) is same as
\[x\equiv 10\pmod{16}\]

Answer 27

simply plugin \(x=77t+70\) above and reduce

Answer 28

so \[77t+70=10(\mod 16)\]

Answer 29

do i multiply the inverse of 10 mod 16 on both sides?

Answer 30

first reduce

Answer 31

\(77t+70\equiv 10 \pmod{16}\)

\(77t \equiv -60\pmod{16}\)

\(77t \equiv 4\pmod{16}\)

yes ?

Answer 32

oh right

Answer 33

so then now the inverse?

Answer 34

also 77 is same as -3 in mod 16, so

\(77t \equiv 4\pmod{16}\)

reduces to

\(-3t \equiv 4\pmod{16}\)

Answer 35

now what is the inverse of -3 in mod 16

Answer 36

in other words, what number you need to multiply by "-3" to get 1 ?

Answer 37

-11

Answer 38

so that gives me \[t≡-44(\mod16)\]?

Answer 39

Notice that -11 is same as 5

Answer 40

-44 is correct, reduce it and make it look simpler

Answer 41

that's basically \[t≡4(\mod16)\] isn't it

Answer 42

which is \[t=16x+4\]

Answer 43

is that correct?

Answer 44

\(t = 16m+4\)

Answer 45

so \(x = 77t+70 = 77(16m+4)+70 = 1232m + 378\)

plug that in next congruence and solve \(m\)

Answer 46

So \[1232m=-375(\mod17)\]and then\[m=-5625(\mod17)\]

Answer 47

Which is basically \[m=2(\mod17)\]

Answer 48

Yes, which is same as \(m = 17q + 2\)

Answer 49

so \(x = 1232m+378 = 1232(17q+2)+378 = 20944q +2842 \)

Answer 50

so the smallest possible collection of cards is \(2842\)

Answer 51

Thanks!

Answer 52

Also notice \[20944 = 7*11*16*17\]

Answer 53

the whole thing we did just now can be done in a single line using chinese remainder theorem

Answer 54

woah :o better google that

Answer 55

i suggest you wait till your professor teaches you that

Answer 56

alright, thank you!

Answer 57

np