Problem:
Let be the number of solutions in positive integers to the equation , and let be the number of solutions in positive integers to the equation . Find the remainder when is divided by .
Solution:
Let be a nonnegative integer solution to . Then is a positive integer solution to . Conversely, if is a positive integer solution to , then is a nonnegative integer solution to . This establishes a one-to-one correspondence between the nonnegative integer solutions to and the positive integer solutions to . The difference is therefore the number of nonnegative integer solutions to in which . If , then and it follows that must be one more than a nonnegative multiple of , and . Thus the possible values of are , and this is a total of values. Similarly, there are solutions with , and solutions with . Note that the solutions and are each counted twice, so the total number of nonnegative integer solutions to in which is , and the requested remainder is .
(Note: Using a computer algebra system, one can verify that and .)
The problems on this page are the property of the MAA's American Mathematics Competitions