Maths Olympiad Prep

Library / /399 of 520

Number theory Difficulty 6.6 National olympiad Find the answer

33 Find the largest positive integer that cannot be expressed as the sum of a positive multiple of 42 and a composite number.

Translate the text above into English, please keep the original text's line breaks and format, and output the translation result directly.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

33. For any positive integer nn that cannot be expressed as a positive multiple of 42 and a composite number, consider the remainder rr when nn is divided by 42. If r=0r=0 or rr is a composite number, then n42n \leqslant 42.

Now consider the case where r=1r=1 or rr is a prime number.
If r1(mod5)r \equiv 1(\bmod 5), then
84+r0(mod5)84+r \equiv 0(\bmod 5)

In this case,
n<3×42=126n<3 \times 42=126

If r2(mod5)r \equiv 2(\bmod 5), then
4×42+r0(mod5)4 \times 42+r \equiv 0(\bmod 5)

In this case,
n<5×42=210n<5 \times 42=210

If r3(mod5)r \equiv 3(\bmod 5), then
42+r0(mod5)42+r \equiv 0(\bmod 5)

In this case,
n<2×42=84n<2 \times 42=84

If r4(mod5)r \equiv 4(\bmod 5), then
3×42+r0(mod5)3 \times 42+r \equiv 0(\bmod 5)

In this case,
n<4×42=168n<4 \times 42=168

If r0(mod5)r \equiv 0(\bmod 5), then
r=5,r=5,

In this case, since 5, 47, 89, 131, and 173 are all prime numbers, nn is at most 215.
In summary, the largest positive integer sought is 215.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.