For each positive integer , define to be the smallest positive integer divisible by each of the positive integers . How many positive integers with have ?
Solution
For each positive integer is defined to be the smallest positive integer divisible by each of . In other words, is the least common multiple (lcm) of . 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 , we determine the lcm of . The prime factorizations of the numbers are . The primes used in this list are , with highest powers . Therefore, . Since is the lcm of and is the lcm of , then if either (i) there are prime factors that occur in that don't occur in or (ii) there is a higher power of a prime that occurs in the factorizations of one of that doesn't occur in any of . For (i) to occur, consider a prime number that is a divisor of one of and none of . This means that the smallest positive integer that has as a divisor is one of the integers , which in fact means that this integer equals . (The smallest multiple of a prime is , or itself.) Thus, for (i) to occur, one of is a prime number. For (ii) to occur, consider a prime power (with ) that is a divisor of one of and none of . Using a similar argument to condition (i), one of must equal that prime power . Therefore, whenever one of is a prime number or a prime power. In other words, whenever none of is a prime number or a prime power. Therefore, we want to determine the positive integers with for which none of is a prime number or a prime power. The prime numbers less than or equal to 104 are . (We go up to 104 since can be as large as 100 so can be as large as 104.) The prime powers (with exponent at least 2) less than or equal to 100 are . 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 with for which none of appear in the list . 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 that satisfy this condition are . (For example, 54 is a value of that works since none of appears in the list.) Therefore, there are 11 values of with for which .