Browse · MATH
Printjmc
number theory senior
Problem
The American Mathematics College is holding its orientation for incoming freshmen. The incoming freshman class contains fewer than people. When the freshmen are told to line up in columns of , people are in the last column. When the freshmen are told to line up in columns of , people are in the last column. How many people are in the incoming freshman class?
Solution
If is the number of people in the incoming class, then yields a remainder of when divided by . Since both 21 and 14 are divisible by 7, this means that is divisible by . Define , and note that . Dividing by 7, we get . Multiplying by 7 again, we get , which implies . So we are looking for a solution to the following system of linear congruences: First, we look for a solution to the last two congruences. Checking numbers that are one less than a multiple of 23, we find that 68 satisfies . By the Chinese Remainder Theorem, the integers which satisfy both of the last two congruences are precisely those that differ from 68 by a multiple of . Checking , , etc. we find that is the least positive solution to the last two congruences which is also divisible by 7. Note that, by the Chinese remainder theorem again, the solutions of the above system of three congruences are precisely the positive integers that differ from 413 by a multiple of so 413 is indeed the only solution between 0 and 500.
Final answer
413