Remainders
|
Hint: To find the largest possible remainder in the GAIM 2016 problem, search efficiently starting from where the possible remainders are as large as possible.
Sieve of EratosthenesEratosthenes of Cyrene (c. 276 BC - c. 194 BC) was a Greek mathematician who invented a fast way to find all prime numbers up to a given upper bound. His method is an iterative algorithm, which involves skip counting and filtering away the multiples of each prime number.
Challenge! For a given upper bound, what is the largest prime number whose multiples must be identified and removed? (Hint: Think conceptually about finding factors of any number. Or set different upper bounds and try to find a rule that always yields the last prime that must be checked.) |
DivisibilityDivisibility plays an important role in the theory of numbers. Learn and practice the Divisibility Rules up through 11.
11 alternating sum of digits is divisible by 11 Example: 11 | 2728 because 2 - 7 + 2 - 8 = -11.
|
|
Numerical Exercises
|
Problem 1 solution
\[ {28} = {2} ^ {2} \cdot {7} \] From 10 to 30, only 9 integers are relatively prime with 28, since they contain no factors of 2 and 7: 11, 13, 15, 17, 19, 23, 25, 27, and 29 Extension: How many 2-digit numbers are relatively prime with 42? Problem 2 solution
\[6 = 1 + 2 + 3\] \[28 = 1 + 2 + 4 + 7 + 14\] The only perfect numbers less than 30 are 6 and 28. 6 + 28 = 34.
Extension: What are the first four perfect numbers? Problem 3 Solution
When dividing by 3, the largest possible remainder is 3 - 1 = 2. Extension: Rose put an equal number of pencils into 3 bags, but had one pencil left over. She tried again with 5 bags, and had one pencil left over. She tried again with 7 bags, and still had one pencil left over! What's the smallest number of pencils that Rose could have? Problem 4 Solution
13 and 15 are only two apart. Searching for twin primes yields x = 16 when x + 7 = 23, x + 13 = 29, and x + 15 = 31. Extension: What is the second smallest possible value of x? Problem 5 Solution
The prime factorization of 210 = 2∙3∙5∙7. These prime factors must be combined in ways that form 2 or 3 consecutive positive integers. \[210 = (2 \cdot 7)(3 \cdot 5) = 14 \cdot 15\] \[210 = 5 \cdot (2 \cdot 3) \cdot 7 = 5 \cdot 6 \cdot 7\] The sum of the five integers 5 + 6 + 7 + 14 + 15 = 47. Extension: 421,200 is the product of four consecutive positive integers. What is the sum of the four numbers? problem 6 solution
Positive integers that have exactly 4 positive factors are either the cube of a prime, or the product of 2 distinct primes. The smallest 6 positive integers that follow these forms are: 2∙3, 2³, 2∙5, 2∙7, 3∙5, and 3∙7. Then 6 + 8 + 10 + 14 + 15 + 21 = 74. Extension: What is the sum of the smallest 6 positive integers that have exactly three positive factors? problem 7 Solution
problem 8 solution
List the largest 3-digit numbers that are multiples of 17: 986, 969, 952, 935, 918, 901, etc. List the largest 3-digit numbers that are one less than a multiple of 8: 999, 991, 983, 975, 967, 959, 951, 943, 935, 927, etc. The first number that appears on both lists is 935. Extension: What is the smallest positive value of x? problem 9 Solution
\[\frac{1}{2^9} = \frac{1}{2^9} \cdot \frac{5^9}{5^9} = \frac{5^9}{10^9}\] Then the decimal representation of 1/2⁹ can be found by moving the decimal point 9 spaces to the left in the decimal representation of 5⁹. The last digit of 5⁹, and any other power of 5, is 5. It follows that the reciprocal of any power of 2 ends in 5. Extension: What is the last digit of the decimal for 1/5⁹? problem 10 solution
The number of integer values of x for which 10 ★ x = 10² ÷ x = 100 ÷ x is a positive integer boils down to counting of the proper factors of \[100 = 2 ^ 2 \cdot 5 ^ 2\] With 0, 1, and 2 as the possibilities for the exponent of 2, and the same choices for the exponent of 5, 100 has (3)(3) = 9 factors, 8 of which are proper. The proper factors of 100 can also be found by brute force enumeration: 1, 2, 4, 5, 10, 20, 25, and 50. Extension: For how many positive integers less than 100 will the value of x ★ 6 be a positive integer? problem 11 solution
Since 8 and 11 are relatively prime, the integers in question must be multiples of 88. A quick search yields: \[(11 \cdot 8)(2) = 11(8 \cdot 2) = 11 \cdot 16 = 176\] \[(11 \cdot 8)(3) = 11(8 \cdot 3) = 11 \cdot 24 = 264\] Since the next multiple of 88 exceeds 300, the answer is 2.
Extension: How many integers between 100 and 300 are divisible by both 12 and 8? problem 12 solution
\[\frac{1}{2^{12}} = \frac{1}{2^{12}} \cdot \frac{5^{12}}{5^{12}} = \frac{5^{12}}{{10}^{12}}\] Then the decimal representation of 1/2¹² may be found by moving the decimal point 12 spaces to the left in the decimal representation of 5¹². Therefore, regardless of the value of 5¹², there must be 12 digits to the right of the decimal point in 1/2¹². Extension: When 1/4⁴ is written as a decimal, how many digits are to the right of the decimal point? problem 13 solution
For the quotient (n + 1)/(13 - n) to be a positive prime number, numerator and denominator must be both positive or both negative. Quick inspection shows both negative to be impossible. The largest integer to check for both positive, n = 12, yields a quotient of 13. Extension: For how many integer values of n is (13 - n)/(n + 1) a positive integer? problem 14 solution
Dividing away the smallest possible factors of 144 - 2, 3, 4, 6, 8, and 12 - yields the two-digit factors of 144:
72, 48, 36, 24, 18, 12. (72 + 48) + (36 + 24) + (18 + 12) = 120 + 60 + 30 = 210. Extension: What is the sum of all the factors of 144? problem 15 Solution
Thus the number of students in each row could be 24, 18, or 16. 24 + 18 + 16 = 58. Extension: What is the sum of all possible values of x if the graduating class has 300 students? problem 16 solution
The smallest number with 16 positive factors must have a prime factorization of p³∙q³. The exponents for each factor would be 0, 1, 2, or 3, yielding (3 + 1)(3 + 1) = 16 possible factors. The two primes that divide into 72 are 2 and 3, so the desired multiple of 72 must be (2³)(3³) = 6³ = (72)(3) = 216. Extension: What is the least positive multiple of 72 that has exactly 18 positive factors? problem 17 solution
The difference between two prime numbers is almost always even, since most prime numbers are odd. (Try it!) For the difference to be 17, which is odd, one of the numbers involved must be 2 - the only even prime number. Then the two prime numbers must be 2 and 19, and 2 + 19 = 21.
Extension: Prime numbers 2 units apart are called twin primes. What's the sum of the largest pair of 2-digit twin primes? problem 18 solution
The positive integer factors of 18 are 1, 2, 3, 6, 9, and 18. \[\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{6} + \frac{1}{9} + \frac{1}{18} = \frac{18}{18} + \frac{9}{18} + \frac{6}{18} + \frac{3}{18} + \frac{2}{18} + \frac{1}{18}\] \[= \frac{2^2-1}{2-1} \cdot \frac{3^3-1}{3-1} ÷ 18 = \frac{3 \cdot 13}{18} = \frac{13}{6}\] This solution revisits the formula from Problem 14, but the desired sum of 13/6 can also be found by brute force. Extension: What is the sum of the reciprocals of all positive integer factors of 6? What is the next largest integer for which the sum has the same value? |
Proof-Writing Exercises
- Prove the divisibility rules for 3 and 9. Does this method extend to higher powers of 3? Why or why not?
- Prove the divisibility rule for 4 and for 8. Does this method extend to higher powers of 2? Why or why not?
- Prove a divisibility rule for 7.
- Prove the divisibility rule for 11.
- Find and prove a divisibility rule for 13.
- Find and prove the divisibility rule for 17.
- Find and prove the divisibility rule for 19.
- Find and prove the divisibility rule for 29.
- Prove the infinitude of primes (à la Euclid).
- Prove the existence of an arbitrarily long prime gap. (Hint: Use factorials.)
- Find and prove a formula for the number of factors of any given number.
- Find and prove a formula for the sum of the factors of any given number.