Problem 14 states, 2021 has a remainder of 5 when divided by 6, by 7, by 8, and by 9. How many positive integers less than 2021 have this property? So here we have a quick summary of what the problem tells us. If we divide 2021 by 6, 7, 8, and 9, we will get some number with a remainder of 5. These numbers are represented with ABCD and they are just arbitrary. So the question asked us how many numbers under 2021 also have this property. One poor strategy would be to go through every number and see if its remainder are 5 when we divide by 6, 7, 8, and 9, but we can probably do a little bit better. With no clear strategy to go off, let's try doing a simpler problem of the same variety and see if we can get some insight. Let's see how many numbers less than 60 have the property that when divided by 3 or 5, the remainder is 2. So now let's use that strategy that I just said was poor to see what happens on a small set of numbers, we'll say 1 through 20. In the first column, let's put the remainder if we divide the number by 3, this is a repeating pattern of 0, 1, and 2. In the next column, let's put the remainder when we divide the number by 5. Here we see another repeating pattern that goes 0, 1, 2, 3, 4. We can see that in this set of numbers, there are two numbers, 2 and 17 that match our pattern, but there is also something interesting after the number 15. The pattern of the two patterns seems to reset at 16, and then it restarts. But why does this happen at the number 15? Well, if we look at the two numbers we are dividing by, that might give us a clue. It's the least common multiple between 3 and 5. So if we know the pattern restarts every 15, and the target number occurs as the second number in each number set, we know that there are 4 numbers with this property below 60. We were able to learn a lot from this simpler version of the problem. We were able to see that if we take the least common multiple of the numbers we are dividing by, we can determine how many of the numbers with the remainder property exist. Now let's go back to our original problem. So we have 4 numbers that we are dividing by, so let's find their least common multiple. We can do this by analyzing their prime factorizations. So 6 breaks up into 2 and 3, 7 is already prime, so it is 7, 8 is 2 cubed, and 9 is 3 squared. We can notice that if we do not multiply by 6, this is okay, because the number will still be divisible by 6, because both 8 and 9 have all of the factors of 6, they have a 2 and a 3. In our case, no other exclusions can be made. So let's multiply all the numbers together to get the least common multiple. 7 times 8 times 9 gives us a product of 504. So the pattern of remainders repeats every 504 numbers. So now let's take a look at the number line. We know that 2021 is one of the numbers that is really close to 504 times 4, which is 2016, so we know the pattern occurs at the very start of each cycle. So in our case, there would be 4 numbers. The exact values don't matter, but if you are curious, here they are. So the question asked us, how many positive integers less than 2021 have this property? The answer is 4, letter A.

remainder

LCM

divisibility

number theory

pattern