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=23×32×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×7×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 a9. Therefore, the sum of the digits is 8+9+a+9+8=34+a. The largest possible value of a9 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×3×5×7×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×7 and 77=7×11, it must be of the form k×5a×7b×11c where k,a,b,c are positive integers.

    Let m be the number of positive divisors of k where m1. So the number of positive divisors of n is m(a+1)(b+1)(c+1)=8. Since a,b,c,1, it must be the case that m=a=b=c=1 and so n=5×7×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(m4n4) is always divisible by 30.

    Proof

    Let T=mn(m4n4)=mn(m2n2)(m2+n2)=mn(mn)(m+n)(m2+n2).

    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+31=3(k+1)1. Since k is an integer, it follows that k+1 is an integer and thus, m=3j1 for some integer j. The variable name is irrelevant, so we can simply say that m=3k+1 or m=3k1 (or more concisely that m=3k±1), for some integer k.

    Similarly, we can say that n=3j±1 for some integer j.

    If m=3k+1 and n=3j+1, then mn=3k+13j1=3k3j=3(kj). Since k and j are integers, it follows that mn will be divisible by 3.

    In a similar manner, we can show that if m=3k1 and n=3j1, then mn will be divisible by 3.

    If m=3k+1 and n=3j1, then m+n=3k+1+3j1=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=3k1 and n=3j+1, then m+n will be divisible by 3.

    Therefore, in every case, either mn 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+52=5(k+1)2. Since k is an integer, we have that k+1 is an integer and thus, m=5j2, for some integer j. Also, if m=5k+4, then m=5k+51=5(k+1)1. Since k is an integer, we have that k+1 is an integer and thus, m=51 for some integer . Again, since the variable names are irrelevant, we can simply say that m=5k±1 or m=5k±2, for some integer k.

    Similarly, we can say that n=5j±1 or n=5j±2, for some integer j.

    If m=5k±1, then m2=(5k±1)2=25k2±10k+1=5(5k2±2k)+1 Since k is an integer, we have that 5k2±2k is an integer and so m2 is of the form 5a+1, for some integer a.

    If m=5k±2, then m2=(5k±2)2=25k2±20k+4=25k2±20k+51=5(5k2±4k+1)1 Since k is an integer, we have that 5k2±4k+1 is an integer and so m2 is of the form 5a1 for some integer a. So m2=5a±1.

    Similarly, we can show that n2=5b±1.

    Therefore, in a similar manner to what we did in the divisible by 3 case, we can show that in all cases, m2+n2 or m2n2 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 102020. What is the sum of the digits of n?

  4. In the Fibonacci sequence, 1,1,2,3,5,, 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 132=x10y 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 a3+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.