Problem:
What is the largest positive integer that is not the sum of a positive integral multiple of and a positive composite integer?
Solution:
Suppose that is not the sum of a positive multiple of and a positive composite integer. Let be the smallest positive integer that makes divisible by . Because is not divisible by , it follows that , and the conditions on imply that no term of the arithmetic progression
is composite. If there are at most four terms in this progression, then
On the other hand, if there are more than four terms, then is required, for there must be a multiple of among any five consecutive terms of an arithmetic progression whose constant difference is not divisible by , and no term after is composite. Thus the only progression with at least five terms begins
which has as its first composite term. Thus is the largest integer that is not the sum of a positive multiple of and a composite positive integer.
Because and are relatively prime, every integer can be expressed in the form , for some integers and . Moreover, is a solution of
if and only if is also a solution. Therefore, there is one solution for which . It follows that the largest integer that cannot be written in the form with and is . In other words, every integer larger than is the sum of a multiple of and a composite number a multiple of , in fact. Now check that , , and are prime, thereby showing that is the largest integer that is not the sum of a positive multiple of and a composite positive integer.
The problems on this page are the property of the MAA's American Mathematics Competitions