CEMC Banner

Properties of Numbers

Toolkit

Divisibility Rules

General Properties of Integers

Sample Problems

  1. Find the smallest positive integer \(k\) such that \(504k\) is a perfect square.

    Solution

    The prime factorization of 504 is \(504 = 2^3 \times 3^2 \times 7\). The prime factorization of a perfect square must include each prime factor an even number of times. Therefore, if \(504k\) is a perfect square, then \(k\) must be of the form \(2\times 7 \times m\) where \(m\) is a perfect square. The smallest positive value of \(m\) which is a perfect square is \(m=1\) and so \(k = 14\).

  2. The number \(27572\) is a palindrome because it reads the same backwards as forwards. What is the largest five-digit palindrome divisible by \(6\)?

    Solution

    An integer is divisible by \(6\) if it is divisible by both \(2\) and \(3\). Since the palindrome is divisible by \(2\), the last digit must be even. Therefore, the first digit will be even. The largest possible first digit is \(8\). The largest possible second digit is \(9\) and so the fourth digit will be \(9\). To determine the middle digit we use the fact that if an integer is divisible by \(3\), then the sum of its digits must be divisible by \(3\).

    Let \(a\) represent the middle digit. Since \(a\) is a digit, we have that \(a \leq 9\). Therefore, the sum of the digits is \(8+9+a+9+8 = 34+a\). The largest possible value of \(a\leq 9\) for which \(34+a\) is divisible by \(3\) is \(8\). Therefore, the largest five-digit palindrome which is divisible by \(6\) is \(89898\).

  3. When a positive two-digit number \(m\) is multiplied by a positive three-digit number \(n\) the result is \(21210\). Find all possible pairs \((m,n)\).

    Solution

    The prime factorization of \(21210\) is \(21210 = 2 \times 3 \times 5 \times 7 \times 101\).

    Since \(m\) is a two-digit number it cannot have \(101\) as a divisor. Therefore, \(n\) is a multiple of \(101\).

    The prime factorization of \(n\) can include at most one \(2\), at most one \(3\), at most one \(5\) and at most one \(7\).

    Since \(n\) is a three-digit number, the possible values for \(n\) are \(101\), \(202\), \(303\), \(505\), \(606\) and \(707\). The corresponding values for \(m\) are \(210\), \(105\), \(70\), \(42\), \(35\) and \(30\), respectively.

    Since \(m\) is a two-digit number, \(210\) and \(105\) are not possible. Therefore, the possible pairs \((m,n)\) are \((70,303), (42, 505), (35, 606)\) and \((30, 707)\).

  4. A number has exactly eight positive divisors, including one and the number itself. If two of the divisors are \(35\) and \(77\), what is the sum of all eight positive divisors?

    Solution

    Let \(n\) be the number. Since \(n\) is divisible by \(35 = 5 \times 7\) and \(77 = 7 \times 11\), it must be of the form \(k \times 5^a \times 7^b \times 11^c\) where \(k, a, b, c\) are positive integers.

    Let \(m\) be the number of positive divisors of \(k\) where \(m \geq 1\). So the number of positive divisors of \(n\) is \(m(a+1)(b+1)(c+1)=8\). Since \(a, b, c, \geq 1\), it must be the case that \(m=a=b=c=1\) and so \(n= 5 \times 7 \times 11=385\).

    The eight positive divisors are \(1, 5, 7, 11, 35, 55, 77,\) and \(385\). Their sum is \[1+5+7+11+35+55+77+385 = 576\]

  5. If \(m\) and \(n\) are integers, prove that \(mn(m^4-n^4)\) is always divisible by \(30\).

    Proof

    Let \(T= mn(m^4-n^4) = mn(m^2-n^2)(m^2+n^2) = mn(m-n)(m+n)(m^2+n^2)\).

    To show that \(T\) is divisible by \(30\) we must show that it is divisible by \(2\), \(3\) and \(5\).

    If at least one of \(m\) or \(n\) is even, then \(T\) is divisible by \(2\). If \(m\) and \(n\) are both odd, then \(m+n\) is even, and so \(T\) is divisible by \(2\).

    If at least one of \(m\) or \(n\) is divisible by \(3\), then \(T\) is divisible by \(3\). If \(m\) and \(n\) are not divisible by \(3\), then \(m = 3k+1\) or \(m= 3k+2\) for some integer \(k\). However, if \(m=3k+2\), then \(m= 3k+3-1 = 3(k+1) -1\). Since \(k\) is an integer, it follows that \(k+1\) is an integer and thus, \(m = 3j-1\) for some integer \(j\). The variable name is irrelevant, so we can simply say that \(m= 3k+1\) or \(m=3k-1\) (or more concisely that \(m= 3k \pm 1\)), for some integer \(k\).

    Similarly, we can say that \(n= 3j\pm1\) for some integer \(j\).

    If \(m=3k+1\) and \(n=3j+1\), then \(m-n = 3k+1-3j-1 = 3k-3j = 3(k-j)\). Since \(k\) and \(j\) are integers, it follows that \(m-n\) will be divisible by 3.

    In a similar manner, we can show that if \(m=3k-1\) and \(n=3j-1\), then \(m-n\) will be divisible by \(3\).

    If \(m=3k+1\) and \(n=3j-1\), then \(m+n = 3k+1+3j-1 = 3k+3j = 3(k+j)\). Since \(k\) and \(j\) are integers, it follows that \(m+n\) will be divisible by 3.

    In a similar manner, we can show that if \(m=3k-1\) and \(n=3j+1\), then \(m+n\) will be divisible by \(3\).

    Therefore, in every case, either \(m-n\) or \(m+n\) is divisible by \(3\) and thus, \(T\) is divisible by \(3\).

    If at least one of \(m\) or \(n\) is divisible by \(5\), then \(T\) is divisible by \(5\). If \(m\) and \(n\) are not divisible by \(5\), then \(m = 5k+1\) or \(m= 5k+2\) or \(m=5k+3\) or \(m=5k+4\), for some integer \(k\). However, if \(m=5k+3\), then \(m= 5k+5-2 = 5(k+1) -2\). Since \(k\) is an integer, we have that \(k+1\) is an integer and thus, \(m = 5j-2\), for some integer \(j\). Also, if \(m=5k+4\), then \(m= 5k+5-1 = 5(k+1) -1\). Since \(k\) is an integer, we have that \(k+1\) is an integer and thus, \(m = 5\ell-1\) for some integer \(\ell\). Again, since the variable names are irrelevant, we can simply say that \(m= 5k \pm 1\) or \(m = 5k\pm 2\), for some integer \(k\).

    Similarly, we can say that \(n = 5j \pm 1\) or \(n= 5j \pm 2\), for some integer \(j\).

    If \(m = 5k \pm 1\), then \[m^2 = (5k\pm 1)^2 = 25k^2\pm 10k+1 = 5(5k^2\pm 2k)+1\] Since \(k\) is an integer, we have that \(5k^2\pm 2k\) is an integer and so \(m^2\) is of the form \(5a+1\), for some integer \(a\).

    If \(m = 5k \pm 2\), then \[m^2 = (5k\pm 2)^2 = 25k^2\pm 20k+4 = 25k^2\pm 20k+5-1 = 5(5k^2\pm 4k+1)-1\] Since \(k\) is an integer, we have that \(5k^2\pm 4k+1\) is an integer and so \(m^2\) is of the form \(5a-1\) for some integer \(a\). So \(m^2 = 5a \pm 1\).

    Similarly, we can show that \(n^2 = 5b \pm 1\).

    Therefore, in a similar manner to what we did in the divisible by \(3\) case, we can show that in all cases, \(m^2+n^2\) or \(m^2-n^2\) is divisible by \(5\) and thus, \(T\) will be divisible by \(5\).

    Thus, \(T\) is divisible by \(2\), \(3\), and \(5\) and so \(T\) is divisible by \(30\).

Problem Set

  1. What is the largest palindrome less than \(200\) that is the sum of three consecutive integers?

  2. When a decimal point is placed between the digits of the two-digit integer \(n\), the resulting number is equal to the average of the digits of \(n\). What is the value of \(n\)?

  3. Let \(n\) be the integer equal to \(10^{20} - 20\). What is the sum of the digits of \(n\)?

  4. In the Fibonacci sequence, \(1, 1, 2, 3, 5, \ldots\), each term after the second is the sum of the previous two terms. How many of the first \(100\) terms of the Fibonacci sequence are odd?

  5. Determine the number of positive divisors of \(900\), including \(1\) and \(900\), that are perfect squares.

  6. Ellie has two lists, each consisting of 6 consecutive positive integers. The smallest integer in the first list is \(a\), the smallest integer in the second list is \(b\), and \(a < b\). She makes a third list which consists of the 36 integers formed by multiplying each number from the first list with each number from the second list. (This third list may include some repeated numbers.) If

    determine all possible pairs \((a, b)\).

  7. Charles was born in a year between 1300 and 1400. Louis was born in a year between 1400 and 1500. Each was born on April 6 in a year that is a perfect square. Each lived for 110 years. In what year while they were both alive were their ages both perfect squares on April 7?

  8. What is the smallest positive integer \(x\) for which \(\dfrac{1}{32} = \dfrac{x}{10^y}\) for some positive integer \(y\)?

  9. The average of three consecutive multiples of \(3\) is \(a\).

    The average of four consecutive multiples of \(4\) is \(a + 27\).

    The average of the smallest and largest of these seven integers is \(42\). Determine the value of \(a\).

  10. Determine all pairs \((a, b)\) of positive integers for which \(a^3 + 2ab = 2013\).

  11. An auditorium has a rectangular array of chairs. There are exactly \(14\) teachers seated in each row and exactly \(10\) students seated in each column. If exactly \(3\) chairs are empty, prove that there are at least \(567\) chairs in the auditorium.