Number Theory Worksheet 1 Factors and Divisibility

Number Theory Worksheet 1 – Factors and Divisibility

1. What is the smallest number 112 must be multiplied by to give:

A square number.
A cube number.

2. [Source: UKMT Mentoring] If 2, 4 and 7 are three digits of a four-digit number N, where N is divisible by 36, find the greatest possible value of N.

3. If a number n is prime and greater than 3, then what is the maximum number
n-12(n+1) is guaranteed to be divisible by?

4. The number of divisors of 55n3 are 55 (including 1 and the number itself). How many divisors does 7n7 have?

5. Determine the following:

The number of zeros that 25! has.
The prime factorisation of 25!
The number of factors this number has.

6. [Source: UKMT Mentoring] How many digits does 520×413 have?

7. Is there an integer solution n to 2n = n2 + n3?

8. My eldest child is twice as old as my youngest. The product of my childrens’ ages is 1664. How many children do I have? (Hint: as usual, prime factorisation to the rescue!)

Optional:

1. Find the smallest positive integer n such that n! is a multiple of 102009

2. [Source: UKMT Mentoring] Given that nr=n!n!n-r!, find the largest prime factor of 200100.

3. [Source: Classic] Show that n! is never an integer, where n is an integer. You will likely need Bertrand’s Postulate, which states that for any integer k, there is always at least one prime between k and 2k.

Number Theory Worksheet 1 - ANSWERS

1. What is the smallest number 112 must be multiplied by to give: (a) a square number (b) a cube number.
(a) 112=24×7. We can multiply by 7 to get a square number, since the powers in the prime factorisation will be even.
(b) We can multiply by 22×72=196 to get a cube number, since the powers in the prime factorisation will all be multiples of 3.

2. If 2, 4 and 7 are three digits of a four-digit number N, where N is divisible by 36, find the greatest possible value of N.
If it’s divisible by 36, the only two coprime factors are 9 and 4, so we know our number must be divisible by 9 and 4. If it’s divisible by 9, the digits must add up to a multiple of 9, so the missing digit is 5. And if it’s divisible by 4 the last two digits must be divisible by 4. We might as well put the largest digits first, so that we start with 75. 42 is not divisible by 4 but 24 is, so our number is 7524.

3. If a number n is prime and greater than 3, then what is the maximum number
n-12(n+1) is guaranteed to be divisible by?
24. If n is prime, then both n-1 and n+1 are even, so both contain a factor of 2. But since n-1, it contains at least two factors of 2, meaning our number is divisible by 23 so far. Similarly, one (and only one) of n-1, n and n+1 have to be divisible by 3. It can’t be n because it is prime, so either n-1 or n+1 is divisible by 3. We can only guarantee it will be divisible by 3 and not for any higher power, because we don’t know whether it’s n-1 or n+1 that’s divisible by 3. Our number is therefore divisible by 23×3=24.

4. The number of divisors of 55n3 are 55 (including 1 and the number itself). How many divisors does 7n7 have?
Answer=352
If 55n3 has 55 factors, then the powers of the prime factorisation must be 10 and 4 (by similar reasoning to that in the lecture notes). Therefore n3 must have powers of 9 and 3, and n must have powers of 3 and 1. Either n=53×111 or n=51×113. Then 7n7 is either 71×521×117 or 71×57×1121. In either case, we have 2×22×8=352 factors.

5. Determine the following:

a. The number of zeros that 25! has.
As per the method described in the lecture notes, there will be 6 trailing zeros (as we use the power of 5 in the prime factorisation, and we’ll have factors of 5 for each multiple of 5 of at most 25, plus the one multiple of 52=25).

b. The prime factorisation of 25!
To get the power of 2 in the prime factorisation, count the multiples of 2, 4, 8, etc that are less than 25. This gives us 12+6+3+1=22. Continuing like this with other prime factors, we get:
25!=222×310×56×73×112×13×17×23

c. The number of factors this number has.
As per the lecture slides, we just find the product of one more than each power. This gives us 23×11×7×4×3×2×2×2=170 016

6. How many digits does 520×413 have?

=520×226=520×220×26=1020×26. This is 64 with twenty zeros on the end, which has 22 digits in total.

7. Does n have an integer solution to 2n=n2+n3?
2n=n21+n
If the LHS just consists of factors of 2, then so must n2 and thus so must n. Given that n is not 0 (since the equation would not be satisfied) then n is clearly even (as it is a non-zero power of 2). But then 1+n is odd, and thus we have an odd factor on the RHS, while non on the LHS. Thus there is no integer solution.

8. My eldest child is twice as old as my youngest. The product of my childrens’ ages is 1664. How many children do I have?
Note that 1664=27×13. If the eldest child is twice as old as the youngest, then the only difference in the prime factorisation of their ages is that the power of 2 is one greater for the eldest child. Neither of these two children can use the single prime factor of 13, because otherwise their prime factorisations would differ other than the change of power in 2.
So there must be a child in the middle whose age is divisible by 13. Note that the lowest power of 2 greater than 13 is 24. Thus the age of the eldest child must be at least 24. But since we only have three remaining prime factors of 2 available at most, it must be the case that the ages of the children are 23, 13 and 24. i.e. There are 3 children.

Optional:

9. Find the smallest positive integer n such that n! is a multiple of 102009
Answer: 8050
102009=22009×52009. Since 2s will occur commonly in n! than 5s, we just need to find the first value of n for which n! contains 2009 prime factors of 5. From the lecture slides, we know we’ll obtain factors of 5 for each multiple of 5 in the factorial, each multiple of 25, 125, etc. There’s roughly n5 multiples of 5, n25 multiples of 25, and so on. This gives us a geometric series, which if we sum to infinity, gives us n4. This allows us to approximate the n for which we have 2009 factors of 5. If n4=2009, then n=8036. More precisely, 8036! has 2006 factors of 5. Continuing up, 8040! Will have 2007, 8045! will have 2008, and 8050! will have 2010, because it’s both a multiple of 5 and 25. So 8050! Is the first number which will have at least 2009 zeros.

10. Given that nr=n!n!n-r!, find the largest prime factor of 200100.
200100=200!100!100!. If the prime factor p is greater than 50, then it’ll appear twice in the denominator. But then it needs to appear at least 3 times in the numerator in order to not be cancelled out. Thus 3p≤200. The largest prime that satisfies this constraint is 61.

11. Show that n! is never an integer, where n is an integer.
Consider the prime factorisation of n. Any prime factor greater than half of n (if there is one) will appear only once, i.e. its power will be 1. But in order for a number to have a square root that’s an integer, the powers in the prime factorisation must all be even. All that remains is to show that we will definitely have a prime factor p where n2<p<n. This is true by Bertrand’s Postulate, and since n! Is the product of all the integers up to n, a prime will appear above half of n in this product.