Start of BMO series!

I'm going to be attempting some BMO1 questions over the course of the next few blog posts. Starting with 2017-2018 Problem 1 and working my way up from there.

Problem: Helen divides $365$ by each of $1, 2, 3, . . . , 365$ in turn, writing down a list of the $365$ remainders. Then Phil divides $366$ by each of $1, 2, 3, . . . , 366$ in turn, writing down a list of the $366$ remainders. Whose list of remainders has the greater sum and by how much?

Solution: First thing to notice is that Helen and Phil are dividing by consecutive numbers respectively. This is important because

$$365 = qk + r \quad \text{ where } 0 \leq r \leq k - 1 $$

$$366 = qk + (r + 1)$$

This implies that $365 \equiv r \pmod{k}$ and $366 \equiv r + 1 \pmod{k}$. From this we can derive the following rules:

1. If $k$ divides $365$ and $366$ evenly, then Helen and Phil both get remainder $0$.
2. If $k$ divides $366$ evenly and not $365$, then Helen gets remainder $k - 1$ while Phil gets remainder $0$.
3. Else, Phil gets remainder $1$ greater than Helen.

So if we determine which values of $k$ divide $365$ or $366$ then we can use our rules to determine the difference in remainder sums between Helen and Phil. We can do this by listing the factors of $365$ and $366$.

$$\text{Factors of 365} = \{1, 5, 73, 365\}$$

$$\text{Factors of 366} = \{1, 2, 3, 6, 61, 122, 183, 366\}$$

In all but $7$ cases (for the $7$ factors of 366 excluding $1$), we have rule 3. This means Phil's remainder sum is $365 - 7 = 358$ more than Helen at this stage.

$2, 3, 6, 61, 122, 183$ all divide $366$ evenly but not $365$. Hence Helen's remainder sum is increased by $1 + 2 + 5 + 60 + 121 + 182 = 371$. So Helen's remainder sum is $371 - 358 = 13$ larger than Phil's. We don't take into account $366$ as a factor because it is not included in Helen's list so does not affect the difference in remainder sums.

There you have it. The key to solving this problem is to stay systematic and clear. The actual approach required is the obvious one, but it's easy to make small counting errors if you don't keep organised.