Maths Olympiad Prep

Library / /144 of 144

Number theory Difficulty 3.1 AMC 10/12 Find the answer

For each positive integer nn, define S(n)S(n) to be the smallest positive integer divisible by each of the positive integers 1,2,3,,n1, 2, 3, \ldots, n. How many positive integers nn with 1n1001 \leq n \leq 100 have S(n)=S(n+4)S(n) = S(n+4)?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

For each positive integer n,S(n)n, S(n) is defined to be the smallest positive integer divisible by each of 1,2,3,,n1, 2, 3, \ldots, n. In other words, S(n)S(n) is the least common multiple (lcm) of 1,2,3,,n1, 2, 3, \ldots, n. To calculate the lcm of a set of numbers, we determine the prime factorization of each number in the set, determine the list of prime numbers that occur in these prime factorizations, determine the highest power of each prime number from this list that occurs in the prime factorizations, and multiply these highest powers together. For example, to calculate S(8)S(8), we determine the lcm of 1,2,3,4,5,6,7,81, 2, 3, 4, 5, 6, 7, 8. The prime factorizations of the numbers 2,3,4,5,6,7,82, 3, 4, 5, 6, 7, 8 are 2,3,22,5,23,7,232, 3, 2^{2}, 5, 2 \cdot 3, 7, 2^{3}. The primes used in this list are 2,3,5,72, 3, 5, 7, with highest powers 23,31,51,712^{3}, 3^{1}, 5^{1}, 7^{1}. Therefore, S(8)=23315171S(8) = 2^{3} \cdot 3^{1} \cdot 5^{1} \cdot 7^{1}. Since S(n)S(n) is the lcm of 1,2,3,,n1, 2, 3, \ldots, n and S(n+4)S(n+4) is the lcm of 1,2,3,,n,n+1,n+2,n+3,n+41, 2, 3, \ldots, n, n+1, n+2, n+3, n+4, then S(n)S(n+4)S(n) \neq S(n+4) if either (i) there are prime factors that occur in n+1,n+2,n+3,n+4n+1, n+2, n+3, n+4 that don't occur in 1,2,3,,n1, 2, 3, \ldots, n or (ii) there is a higher power of a prime that occurs in the factorizations of one of n+1,n+2,n+3,n+4n+1, n+2, n+3, n+4 that doesn't occur in any of 1,2,3,,n1, 2, 3, \ldots, n. For (i) to occur, consider a prime number pp that is a divisor of one of n+1,n+2,n+3,n+4n+1, n+2, n+3, n+4 and none of 1,2,3,,n1, 2, 3, \ldots, n. This means that the smallest positive integer that has pp as a divisor is one of the integers n+1,n+2,n+3,n+4n+1, n+2, n+3, n+4, which in fact means that this integer equals pp. (The smallest multiple of a prime pp is 1p1 \cdot p, or pp itself.) Thus, for (i) to occur, one of n+1,n+2,n+3,n+4n+1, n+2, n+3, n+4 is a prime number. For (ii) to occur, consider a prime power pkp^{k} (with k>1k > 1) that is a divisor of one of n+1,n+2,n+3,n+4n+1, n+2, n+3, n+4 and none of 1,2,3,,n1, 2, 3, \ldots, n. Using a similar argument to condition (i), one of n+1,n+2,n+3,n+4n+1, n+2, n+3, n+4 must equal that prime power pkp^{k}. Therefore, S(n)S(n+4)S(n) \neq S(n+4) whenever one of n+1,n+2,n+3,n+4n+1, n+2, n+3, n+4 is a prime number or a prime power. In other words, S(n)=S(n+4)S(n) = S(n+4) whenever none of n+1,n+2,n+3,n+4n+1, n+2, n+3, n+4 is a prime number or a prime power. Therefore, we want to determine the positive integers nn with 1n1001 \leq n \leq 100 for which none of n+1,n+2,n+3,n+4n+1, n+2, n+3, n+4 is a prime number or a prime power. The prime numbers less than or equal to 104 are 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,1032, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103. (We go up to 104 since nn can be as large as 100 so n+4n+4 can be as large as 104.) The prime powers (with exponent at least 2) less than or equal to 100 are 4,8,16,32,64,9,27,81,25,494, 8, 16, 32, 64, 9, 27, 81, 25, 49. There are 5 powers of 2, 3 powers of 3, 1 power of 5, and 1 power of 7 in this list. No primes larger than 7 have a power less than 100. Therefore, we want to count the positive integers nn with 1n1001 \leq n \leq 100 for which none of n+1,n+2,n+3,n+4n+1, n+2, n+3, n+4 appear in the list 2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,29,31,32,37,41,43,47,49,53,59,61,64,67,71,73,79,81,83,89,97,101,1032, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103. For four consecutive integers not to occur in this list, we need a difference between adjacent numbers to be at least 5. The values of nn that satisfy this condition are n=32,53,54,73,74,83,84,89,90,91,92n = 32, 53, 54, 73, 74, 83, 84, 89, 90, 91, 92. (For example, 54 is a value of nn that works since none of 55,56,57,5855, 56, 57, 58 appears in the list.) Therefore, there are 11 values of nn with 1n1001 \leq n \leq 100 for which S(n)=S(n+4)S(n) = S(n+4).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.