AMATYC SML Training Session - September 17, 2009

The questions in the competitions come from a wide variety of areas of mathematics. Today’s problems are all examples of number theory – questions dealing with patterns that emerge in the integers. Several of the following questions are taken directly, or with minor modification, from old competitions, while others are original or from other sources, but of a similar style. See how well you can do at these, and then we’ll discuss the mathematics behind the problems.

1. How many 0’s are at the end of the expansion of 2009! ?

A 0 is contributed for each factor of 10. Factors of 10 appear every time there is a factor that is divisible by 5 and a factor (possibly, but not necessarily, the same) which is divisible by 2.

Clearly the divisibility by 5 is the limiting consideration, so how many factors of 5 are there in 2009!? The numbers divisible by 5 are 5, 10, 15… 2005, and there are 2005/5 = 401 such numbers. However, any number divisible by 25 contributes another factor of 5, and there are 80 of those. Numbers divisible by 125 contribute a 3^rd factor of 5, and there are 16 of those, and the 3 numbers divisible by 625 contribute a 4^th factor of 5, for a total of 401+80+16+3=500

2. How many 1 digit prime numbers divide 3³² + 5⁵⁵?

This sum is even, so 2 divides it. 3 divides the first term, but not the 2^nd, so it can’t divide the sum. Similarly 5 cannot divide the sum. So the only question remaining is whether 7 divides it.

To attack this, we are going to use modular arithmetic. That is just a fancy way of saying that we are going to do some dividing, and ignore everything but the remainders.

Consider the remainder when (first) 3³² is divided by 7. 3² =9 has a remainder of 2 when divided by 7, and 3³ =27 has a remainder of 6. If all we care about is the remainder, then 3³ and 6 are the same, so we say that 3³ = 6 (mod 7). Then, 3⁶ = (3³)² = 6² =36 (mod 7) . But, since we are only looking at remainders after dividing by 7, 36 = 1 (mod 7), so we conclude that 3⁶ =1 (mod 7).

Why do we care? How does this help? Glad you asked!

(3⁶)² =1² =1(mod 7), so 3¹² is also 1 more than a multiple of 7. Similarly, 3 to the power of any multiple of 6 is also 1 (mod 7). Now, we can conclude that

3³² =(3³⁰) * 3² =1*9 = 2(mod 7). So 3³² is 2 more than a multiple of 7.

A similar argument shows that 5⁵⁵ is 5 more than a multiple of 7 (really! Try it).

So the sum3³² + 5⁵⁵ is 2+5=7 more than a multiple of 7, which is also a multiple of 7.

Therefore 2 and 7 are the 1 digit prime divisors of this number, and the answer is 2.

3. When written as a decimal number 2009²⁰⁰⁹ has D digits and leading digit L. Find D+L

Let x = 2009²⁰⁰⁹. Log(x) = 2009Log(2008) ≈ 6635.69. So 2009²⁰⁰⁹≈10^6635.69. So D=6635, and L is the greatest integer less than 10^.69, is which is 4. So D+L = 6639.

4. What is the least number of prime numbers (not necessarily different) that 3185 must be multiplied by so that the product is a perfect cube?

. So the smallest cube divisible by this is so 5 prime factors are needed

5. If each letter in the equation represents a different digit, what is the value of T?

a. 3 b. 4 c. 5 d. 6 e. 7

6. The number 877530p765q6 is divisible by both 8 and 11, with p and q both digits between 0 and 9 (inclusive). The number is also divisible by:

a. 7 b. 12 c. 16 d. 18 e. Not Enough Info

To be divisible by 8, the last 3 digits must be divisible by 8, so q=3 or 7.

To be divisible by 11, the difference (sum of the digits in the 10s, 1000s, 10000s,… places) – (sum of digits in 1’s, 100’s, 10000’s, …. places) must be divisible by 11.

(8+7+3+p+6+q)-(7+5+0+7+5+6) = p+q-6. If q=3, then p+q-6=p-3 must be a multiple of 11, which implies that p must also equal 3. If q=7, then p+q-6 = p+1, and there is no digit that could be substituted for p to make this divisible by 11.

So p=3 and q=3.

The sum of the digits is therefore 60, so the number is divisible by 3. Since it is also divisible by 4, it is divisible by 12, so that is the answer.

7. If p>5 is a prime number, what is the largest integer which must be a factor of p⁴-1?

. Since p is odd, each of these 3 factors is even, so there are at least 3 factors of 2 in the product. Furthermore, p-1 and p+1 are consecutive odd numbers, so one of them is actually divisible by 4, so there is yet another factor of 2 – so 16 divides the product. Also, p-1,p,p+1 are 3 consecutive numbers, so 3 divides one of them. It can’t divide p (it is a prime bigger than 3), so it must divided p-1 or p+1. so 3 divides the product, so 3*16 = 48 also divides it. The answer must be a multiple of 48, and so the only option is 240.

8. ACME employees receive paychecks every other Friday. Something very unusual happened in 2008 – they received 3 paychecks in the month of February. If Y is the next year with 3 February paydays, then the unit’s digit of Y is

This can only happen in a leap year, with Fridays on the 1^st, 15^th and 29^th. A (non-leap) year has 365 days, which is 1 more than 52 weeks. That is why the day of the week that a given day falls on shifts by 1 day from one year to the next. Leap years add an extra shift. So every 4 years the days shift by 5. How many multiples of 5 are needed to get to a multiple of 7 (which means the days are back to the original day of the week)? 7 of them. In 7*4=28 years, days get shifted 35 times, the equivalent of 5 full weeks. So Feb 1^st will be on a Friday next in 28 years. But over 28 years there are 52*28 + 5 weeks, which means that Feb 1^st will be the “wrong” Friday – not a payday!. They have to wait another 28 years after that for payday to fall on Feb 1 (and 15 and 29). So it next happens after 56 years, in 2064.

9. Call a composite number circumfactorable if all of its positive integer factors greater than 1 can be placed around a circle so that any two adjacent factors have a common factor greater than 1. How many composite numbers less than 200 are not circumfactorable?

A little trial and error shows that any number is circumfactorable if and only it is not the product of 2 distinct primes: p, q, pq cannot be arranged around the circle in the desried way.

If n=pqr, the factors can be arranged as p pq q qr r rp pqr.

Similarly you can arrange numbers with more factors, or with powers of primes as factors. What numbers less than 200 are of the form pq?

They are: 2* (each prime from 3 to 100), 3*(primes from 5 to 66), 5*primes(from 7 to 39), 7*primes(11 to 28), 11*(primes 13to18), and 13*primes(14 to 15 – of which there are none).

Listing the primes up to 100:

2, 3, 5, 7, 11, 13, 17, 19, 23, ,29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

So the answer is 24+ 16+9+5+2=56.