# Summer Math Circle Handouts

## Preview text

Summer Math Circle Handouts
June 16, 2019
2 Solutions to Divisibility Problems
2.1 Warm-up Problems
1. 1001 = 7 · 11 · 13
2. The least common multiple of 6 and 8 is 24, so the least number of packages of hot dogs Xanthia needs to buy is 24/6 = 4 .
2.2 Prime Factorization Review Exercises
1. The prime factorization of 48 is 24 · 3. This means there are 5 · 2 = 10 factors of 48. To ﬁnd the product of all of 48’s factors, we can pair them up into 5 groups that multiply to 48: 1 and 48, 2 and 24, etc. Thus the product of the factors will be 485, so n = 5. The sum of the factors will be (1 + 2 + 4 + 8 + 16)(1 + 3) = 124. Thus n + m = 5 + 124 = 129 .
2.3 Modular Arithmetic Review Exercises
1. The LHS of 73 + 89 ≡ 3 + 9 (mod 10) is equivalent to 3 + 9 (mod 10) which is the same as the RHS, so this congruence is true.
2. We have the two congruences a ≡ 7 (mod 11) and b ≡ 8 (mod 11). Adding these two congruences together, we have a + b ≡ 15 ≡ 4 (mod 11).
3. 4848 ≡ (−1)48 ≡ 1 (mod 7).
2.4 Sprint Exercises
1. To ﬁnd the the least positive integer greater than 1 that leaves a remainder of 1 when divided by each of 2, 3, 4, 5, 6, 7, 8 and 9, we can ﬁnd the least common multiple of 2, 3, 4, 5, 6, 7, 8 and 9 and add 1 to it. We ﬁnd the prime factorizations of each of the numbers: 2, 3, 22, 5, 2 · 3, 6, 23, 32. The greatest power of 2 is 23, the greatest power of 3 is 32, and we also have a 5 and a 7. Thus the least common multiple will be 23 · 32 · 5 · 7 = 2520. To get a remainder of 1, we add one to get 2521 .
2. 17 ≡ 3 (mod 7) and 1234 ≡ 2 (mod 7), so 17n ≡ 1234 (mod 7) is equivalent to 3n ≡ 2 (mod 7). 3 · 3 ≡ 2 (mod 7), so the smallest n will be 3 .
3. Because the numbers are easy to work with, you can just divide 123456 by 101 to get a remainder of 34 .
8

4. First we consider 3736. 3736 is divisible by 2, and 3736 ≡ 1 (mod 3). This means that 3736 ≡ 4 (mod 6) (Since it’s even, we must have 1 + 3 = 4). So n ≡ −4 (mod 6) =⇒ n = 2
5. For this problem it’s easiest to make a table of all the values:
AB CDE F GHI J KL M 1 2 1 0 -1 -2 -1 0 1 2 1 0 -1 NOPQRS T UVWXYZ -2 -1 0 1 2 1 0 -1 -2 -1 0 1 2
Using the table, we get that "numeric" is equal to −2 + (−1) + (−1) + (−1) + 2 + 1 + 1 = −1 .
6. We can split 1, 234, 567, 890 up into 12 · 1004 + 34 · 1003 + 56 · 1002 + 78 · 100 + 90. Since 100 ≡ 1 (mod 99), this is equivalent to
12 · 14 + 34 · 13 + 56 · 12 + 78 · 1 + 90 ≡ 270 ≡ −27 ≡ 72 (mod 99)
7. There are 21 terms in the sum (to verify this, add 4 to each term then divide by 5). Using the sum formula, the sum will be (21)(1 + 101)/2 = 21 · 51. 21 ≡ 6 (mod 15) and 51 ≡ 6 (mod 15), so 21 · 51 ≡ 6 · 6 ≡ 6 (mod 15) =⇒ n = 6 .
8. From the warm up exercise, we know 1001 is a multiple of 7, so the smallest four-digit integer one less than a multiple of 7 will be 1000 .
9. 2004 = 22 · 3 · 167. We want to make x, y and z as small as possible, so one of them has to be 167. For the remaining two variables, we can do 12 and 1, 2 and 6, or 3 and 4. 3 and 4 give the smallest sum, so the minimum possible value will be 3 + 4 + 167 = 174.
10. There are 100 terms in the sum (add 1 to each term, then divide by 2). Using the sum formula, we have 100(1 + 199)/2 = 100 · 100. Since 100 ≡ 2 (mod 7), 100 · 100 ≡ 2 · 2 ≡ 4 (mod 7).
11. 10 ≡ 1 (mod 9), so taking the sum mod 9 is equivalent to adding up all the digits (why? We can write the numbers as 1 + (1 · 10 + 2) + (1 · 102 + 2 · 10 + 3) + · · · ). There are 8 1s, 7 2s, 6 3s, 5 4s, and so on. That means the sum is equivalent to 8 + 14 + 18 + 20 + 20 + 18 + 14 + 8 ≡ 2(−1 + 5 + 0 + 2) ≡ 12 ≡ 3 (mod 9).
12. We can divide both sides by n! to get (n + 1) + (n + 2)(n + 1) = 440. Factoring, we obtain (n + 1)(n + 3) = 440. Since n is an integer, (n + 1) and (n + 3) must be factors of 440. Note that 20 and 22 multiply to 440, and are two apart like (n + 1) and (n + 3). Thus n + 1 = 20 =⇒ n = 19 .
13. If x − 3 and y + 3 are multiples of 7, then x − 3 ≡ 0 (mod 7) =⇒ x ≡ 3 (mod 7) and y + 3 ≡ 0 (mod 7) =⇒ y ≡ −3 (mod 7). That means x2 + xy + y2 + n ≡ 32 + 3(−3) + (−3)2 + n ≡ 9 + n ≡ 0 (mod 7). Thus the smallest n must be 5 .
9

14. For 24,z38 to be divisible by 6, it must be divisible by 2 and 3. We know it’s divisible by 2 because it is even. To check divisibility by 3, we add up all the digits to get 2 + 4 + z + 3 + 8 = 17 + z. To make this sum a multiple of 3, z can be 1,4, or 7 for a sum of 1 + 4 + 7 = 12 .
15. Since 5 ≡ 2 (mod 3), we can rewrite 5n ≡ n5 (mod 3) as 2n ≡ n5 (mod 3). Now it’s a matter of guess and check. 21 ≡ 15 (mod 3), 22 ≡ 25 (mod 3), 23 ≡ 35 (mod 3), 24 ≡ 45 (mod 3), so the smallest n is 4 (feel free to verify all of the (in)congruences on your own).

2.5 Problems
1. The greatest integer will be 4312, and the least will be 1324, for a total of 5636 .

2. We can use the formula from the handout to compute p quickly:

∞ 33

33

33

33

33

3i = 3 + 9 + 27 + 81 + . . .

i=1

This sums to 11 + 3 + 1 = 15 .
3. For a number to be divisible by 44, it must be divisible by both 4 and 11. Using the divisibility rule for 11, we take the alternating sums of the digits of 5m5,62n to get 5 + 5 + 2 = 12 and m + 6 + n. For the number to be divisible by 11, m + 6 + n can equal 12 or 23. So m + n = 6 or m + n = 17. Since we want the greatest number possible, we can let m = 9 and n = 8. 28 is divisible by 4, so this works. Thus the answer is m + n = 17 .
4. We can write out the terms of the Fibonacci sequence mod 4, until the sequence starts to repeat. Let the terms in this new sequence be called an = Fn mod 4. Calculating the ﬁrst few terms of an, we get 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0 . . ., which contains two full cycles of the sequence mod 4 (we see that the sequence repeats after the ﬁrst 6 terms). So our cycle is of length 6, which means the value of an is equivalent to an mod 6. So a100 has the same value as a4, because 100 ≡ 4 mod 6. Referring to the ﬁrst 6 terms of an we calculated above, a4 = 3 .
5. Proof. We can express every positive integer n with ones digit d0, tens digit d1, hundreds digit d2, and so on as d0 + d1 · 10 + d2 · 102 + · · · . Since 10 ≡ 1 (mod 3) and mod 9, n is equivalent to d0 + d1 + d2 + · · · in mod 3 and 9. In other words, if the sum of the digits of n are divisible by 3, then n is divisible by 3 (and the same for 9).
6. The prime factorization of 4000 is 25 ·53. If n is positive, then the greatest possible power of 5 in the denominator of the fraction will be 3. If n is negative, 2 will be in the denominator of the fraction. The greatest possible power of 2 is 5. n can also be 0, so this gives us a total of 3 + 5 + 1 = 9 possible values of n.

10

7. We know that n ≡ S(n) mod 9 from our divisibility rule for 9. So if S(n) = 1274, then n ≡ S(n) ≡ 5 mod 9. So n has a remainder of 5 when divided by 9, which means that n + 1 ≡ 6 mod 9. Using our divisibility rule from above, we have n + 1 ≡ S(n + 1) ≡ 6 mod 9. So the answer must leave a remainder of 6 when divided by 9. The only answer choice that satisﬁes this is (D)1239
8. It is easy to see that the smallest possible 4-digit integer with unique digits is 1234. Although 1234 and also 1235(the next smallest) is not divisible by its integers, 1236 is because it is divisible by 2 and 3.
9. To ﬁnd the remainder when divided by 45, we can ﬁnd the remainders when divided by 5 and 9, which we know the divisibility rules for. N mod 5 is equivalent to the unit digit of N , which is just 4. N mod 9 is equivalent to the sum of the digits of N . However, instead of ﬁnding how many of each digit there is in N , we can simply calculate 1 + 2 + . . . + 43 + 44. This is because for each two-digit number, xy ≡ x + y mod 9 (where xy represents the two-digit number 10x + y, not x · y). And for single-digit numbers, x ≡ x mod 9 (where x represents a single digit). So 1 + 2 + . . . + 43 + 44 = 442·45 = 22 ∗ 45 ≡ 0 mod 9, since 45 is divisible by 9. So we have that N ≡ 4 mod 5 and N ≡ 0 mod 9. So we must ﬁnd a number between 0 and 44 that satisifes these properties. Testing multiples of 9, we see that 9 satisﬁes both conditions, so our answer is 9 .
10. We see that since QRS is divisible by 5, S must equal either 0 or 5, but it cannot equal 0, so S = 5. We notice that since P QR must be even, R must be either 2 or 4. However, when R = 2, we see that T ≡ 2 (mod 3), which cannot happen because 2 and 5 are already used up; so R = 4. This gives T ≡ 3 (mod 4), meaning T = 3. Now, we see that Q could be either 1 or 2, but 14 is not divisible by 4, but 24 is. This means that R = 4 and P = (A) 1 . Credit: AoPS
11. We have n = 100q + r by the deﬁnition of quotient and remainder. We must ﬁnd values of n such that q + r ≡ 0 mod 11. We can add 99q to both sides of the congruence, to get 100q + r ≡ 99q mod 11. However, since 99 is divisible by 11, 99q ≡ 0 mod 11. Also note that n = 100q + r. So substituting these values into the congruence 100q + r ≡ 99q mod 11, we get n ∼= 0 mod 11. So the problem is reduced to ﬁnding the number of 5-digit numbers that are divisible by 11 (it was given that n is a 5-digit number). The smallest 5-digit number divisible by 11 is 10010 = 910 · 11, and the largest is 99990 = 9090 ∗ 11 (this is easy to see from the fact that 9999 = 909 ∗ 11 is divisible by 11). Hence, the number of 5-digit numbers that are divisible by 11 is 9090 − 910 + 1 = 8181 .
12. Note that abc + ab + a = a(bc + b + 1). Also note that there is an equal number of numbers in the set that are 0, 1, and 2 mod 3 (so there is a 31 that a variable is a certain number mod 3). This is because 2010 is divisible by 3. If a ≡ 0 mod 3, then the expression will be divisible by 3 (since 3k is divisible by 3 for any integer k). The chance that a is 0 mod 3 is 31 .
11

We must now consider the case that a is not divisible by 3, or a ≡ 1 or 2 mod 3,
which has a 32 chance of happening. But now we must consider the value of b mod 3. If b ≡ 0 mod 3, then 0 · c + 0 + 1 ≡ 1 mod 3, but this cannot happen as

bc + b + 1 must be divisible by 3 (or 0 mod 3). Our next case is if b ≡ 1 mod 3

(probability 13 ), so 1 · c + 1 + 1 ≡ c + 2 ≡ 0 mod 3, which means that c ≡ 1

mod 3 (probability 1 ). So the chance of this case happening is 1 2.

3

3

Our next (and last) case is when b ≡ 2 mod 3 (probability 31 ). 2·c+2+1 ≡ 2c ≡ 0

mod 3, so c ≡ 0 mod 3 (probability 1 ). The chance of this case happening is 1 2.

3

3

Combining all of our probabilities from all our cases, we get 1 + 2 1 2 + 1 2 =

33 3

3

13 .
27

13. Prime factorizing 323 gives you 17 · 19. The desired answer needs to be a multiple of 17 or 19, because if it is not a multiple of 17 or 19, the LCM, or the least possible value for n, will not be more than 4 digits. Looking at the answer choices, (C) 340 is the smallest number divisible by 17 or 19. Checking, we can see that n would be 6460.

14. As 71 is prime, c, d, and e must be 1, 1, and 71 (up to ordering). However, since c and e are divisors of 70 and 72 respectively, the only possibility is (c, d, e) = (1, 71, 1). Now we are left with ﬁnding the number of solutions (a, b, f, g) satisfying ab = 70 and f g = 72, which separates easily into two subproblems. The number of positive integer solutions to ab = 70 simply equals the number of divisors of 70 (as we can choose a divisor for a, which uniquely determines b). As 70 = 21 ·51 ·71, we have d(70) = (1 + 1)(1 + 1)(1 + 1) = 8 solutions. Similarly, 72 = 23 · 32, so d(72) = 4 × 3 = 12.
Then the answer is simply 8 × 12 = 096 . Credit: scrabbler94 (AoPS)

15. Let’s assume that one of the children is 5 years old. Then 5 must divide the 4-digit license plate number, implying that the last digit of the 4-digit number must either be a 0 or a 5. Since the ages of the 8 children are 8 distinct integers from the set {1, 2, . . . , 9}, we know that at least one child’s age is even. Therefore, since the 4-digit number must be divisible by 2, its last digit cannot be 5 (the last digit must be even). Hence, the last digit must be 0.
Since there are only 2 distinct letters in the 4 digit number and each digit is repeated twice, we know that the number must be of the form dd00 or d0d0, where d is an arbitrary digit. Additionally, we know that the last 2 digits of the number form Mr. Jones’ age, so we can rule out the ﬁrst case; thus, the number must be of the form d0d0.
Now, we can write the numeral d0d0 as d · 1010 = d · 101 · 10. We know that the number must be divisible by 3 since 3, 6, and 9 are divisible by 3 and it also must be divisible by 4 since 4 and 8 are divisible by 4. Using the divisibility rule of 4, we must have the numeral a0 is divisible by 4 which means a is even. By the

12

divisibility rule for 3, a + a + 0 + 0 should be divisible by 3 which means a is divisible by 3. Hence, we have that a = 6. However, using the divisibility rules for 7 and 9, 6060 is not divisible by 7 or 9. This is a contradiction, so 5 cannot be the age of one of Mr. Jones’ children. 16. So we must ﬁnd the values of n such that 3n−1 + 5n−1|3n + 5n. We know that
3n−1 + 5n−1|(3n−1 + 5n−1) · (3 + 5) = 3n + 5n + 5 · 3n−1 + 3 · 5n−1 Now we will use the property that if k|a and k|a + b, then k|b. So we can subtract 3n + 5n from the right side of the above statement (using the very ﬁrst statement, 3n−1 + 5n−1|3n + 5n), to get
3n−1 + 5n−1|5 · 3n−1 + 3 · 5n−1 = 15(3n−2 + 5n−2) so
3n−1 + 5n−1|15(3n−2 + 5n−2) We will now take care of the case where n = 1. When n = 1, 3n−1 + 5n−1 = 2, and 3n + 5n = 8, and 2|8. Hence, n = 1 satisﬁes the constraints. Now, for n > 1, we see that gcd(3n−1 + 5n−1, 15) = 1. This is because 3n−1 + 5n−1 is not divisible by 3 or 5, because gcd(3, 5) = 1. Hence, for the above statement to be true, we must have
3n−1 + 5n−1|3n−2 + 5n−2 However, if a|b for positive a and b, then a ≤ b. So we must have 3n−1 + 5n−1 < 3n−2 + 5n−2, which is not true for n > 1 because we have 3n−1 > 3n−2 and 5n−1 > 5n−2. Hence, there are not solutions for n > 1 and hence, the only solution is when n = 1 .
Contributors: Daniel Stewart, Ananth Shyamal, Divya Shyamal, Kevin Yang, Reece Yang