Number Theory Worksheet 1 - Factors and Divisibility

Number Theory Worksheet 1 – Factors and Divisibility
All SMC, BMO and Mentoring problems are © UKMT (www.ukmt.org.uk)
1. What is the smallest number 112 must be multiplied by to give:

a. A square number.
b. 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−1 )2 (n+1) is guaranteed to be divisible by?
4. The number of divisors of 55 n3 are 55 (including 1 and the number itself). How many
divisors does 7 n7 have?
5. Determine the following:
a. The number of zeros that 25 ! has.
b. The prime factorisation of 25 !
c. The number of factors this number has.
6. [Source: UKMT Mentoring] How many digits does 520 ×4 13 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
n!
2. [Source: UKMT Mentoring] Given that (nr )= n ! ( n−r )!
, find the largest prime factor of
(200
100 )
.
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 2 k .
www.drfrostmaths.com/rzc
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−1 )2 (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 55 n3 are 55 (including 1 and the number itself). How many divisors does
7 n7 have?
Answer=352If 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 7 n7 is either 71 ×521 × 117
or 71 ×57 ×11 21. 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 ×7 3 × 112 × 13× 17 ×19 ×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 ×4 13 have?
¿ 520 × 226=( 520 ×220 ) ×26=10 20 ×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=n2 ( 1+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 102009Answer:

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
n n
multiples of 5, multiples of 25, and so on. This gives us a geometric series, which if we sum to
5 25
n
infinity, gives us . This allows us to approximate the n for which we have 2009 factors of 5. If
4
n
=2009, then n=8036. More precisely, 8036 ! has 2006 factors of 5. Continuing up, 8040! Will
4
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.
n!
10. Given that (nr )= n ! ( n−r )!
, find the largest prime factor of (200
100 )
.
200 = 200 !
( )100 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 3 p ≤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
n
will definitely have a prime factor p where < p< n. This is true by Bertrand’s Postulate, and since
2
n ! is the product of all the integers up to n , a prime will appear above half of n in this product.

Number Theory Worksheet 1 - Factors and Divisibility

Uploaded by

Copyright:

Available Formats

Number Theory Worksheet 1 - Factors and Divisibility

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Number Theory Worksheet 1 - Factors and Divisibility

Uploaded by

Copyright:

Available Formats

Number Theory Worksheet 1 – Factors and Divisibility

All SMC, BMO and Mentoring problems are © UKMT (www.ukmt.org.uk)

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

5. Determine the following:

7. Does n have an integer solution to 2n=n2+ n3?

9. Find the smallest positive integer n such that n ! is a multiple of 102009Answer:

11. Show that √ n ! is never an integer, where n is an integer.

You might also like