# 2000 PMWC Problems/Problem T1

## Problem

A box contains $4000$ to $6000$ candies. When the candies are evenly distributed to $5$, $6$, $7$, $8$, or $9$ children, there is always one candy left. If the candies are packaged into small bags each having the same number of candies, what is the largest number of candies below $4000$ in each bag so that no candies are left?

## Solution

If there is always one candy left over when the candies are evenly distributed to $5$, $6$, $7$, $8$, or $9$ children, then there must also be exactly one candy left over when the candies are distributed to $LCM(5, 6, 7, 8, 9)$ children. Since $LCM(5, 6, 7, 8, 9) = 2^3 * 3^2 * 5^1 * 7^1 = 2520$, the total number of candies can be expressed as $2520n + 1$, where $n$ is any nonnegative integer. However, we know that there are between $4000$ and $6000$ candies, so the only viable value for $n$ is $2$, meaning the total number of candies is $2520(2) + 1 = 5040 + 1 = 5041$.

The problem then asks us to find the largest number of candies below $4000$ such that the candies are evenly distributed and no candies are left over. This is equivalent to asking what the largest factor of $5401$ is that is less than $4000$. Since $5401 = 71^2$, the only factors of $5401$ are $1$, $71$, and $5401$. Thus the answer is $\boxed{71}$.