# Clarify a problem with prime and composite numbers

What is the largest positive integer that is not the sum of a positive integral multiple of 42 and a positive composite integer?

The solution listed says

The requested number $\mod {42}$ must be a prime number. Also, every number that is a multiple of 42 greater than that prime number must also be prime, except for the requested number itself. So we make a table, listing all the primes up to 42 and the numbers that are multiples of 42 greater than them, until they reach a composite number.

I understand the first sentence's reasoning. However I don't get why every multiple of 42 greater than that number also has to be prime except for the solution. If it's not prime, that doesn't mean it will be a sum of a composite number and a multiple of 42. And why does the answer have to be composite? It seems arbitrary.

• Is this the entire solution? – Brian J. Fink Mar 12 '14 at 4:55
• @BrianJ.Fink There was also a table included – qwr Mar 12 '14 at 4:57
• Maybe this has some significance: $42=2\cdot3\cdot7$ – Brian J. Fink Mar 12 '14 at 5:04

(I've completely rewritten this answer, to make it closer to that of the given solution.)

Let us consider such positive integers separately, by their remainder modulo $42$.

So fix an $r$, where $1 \le r \le 42$. (We're picking $1 \le r \le 42$ instead of the conventional $0 \le r < 42$, because we only care about positive numbers and this makes some arguments simpler.) Let us consider numbers $n \equiv r \mod 42$.

That is, we're looking for an $n$ in the sequence $$r, r + 42, r + 2(42), r+3(42), r+4(42), \dots$$ such that $n$ is not the sum of a positive composite integer and a positive multiple of $42$. This is equivalent to saying that $n$, wherever it occurs in this sequence, has no composite number earlier in the sequence than it.

Therefore, the largest "good" $n$ in the sequence is the largest $n$ such that all earlier elements of the sequence are non-composite, which means that $n$ is the first composite number in the sequence.

So for each $r$, where $1 \le r \le 42$, we simply need to write down the sequence $r, r + 42, r + 2(42), \dots$, and record the first composite number that occurs in it. The largest of these is the answer. As a shortcut (as e.g. considering $r=2$ shows that the the answer happens to be at least $44$), we can choose to start with only prime $r$.

• Actually you need to consider $r = 1$ too, and go until $1, 43, 85$, but you can stop there. – ShreevatsaR Mar 12 '14 at 6:35

For clarification purposes: Take 7 columns in EXCEL and put numbers $1, 2,...,7$. On the second row put $8, 9, 10, 11, 12, 13, 14$ and so on for the $3^{rd}$ and successive rows. Eliminate all numbers except prime numbers, and you will end up with two sets of parallel lines. (You can cut around the edges and roll up into a cylinder and there will be exhibited a double helix winding down the outside of the cylinder).

If one gives the designation of $1$ for the first line in any pair and $2$ for the second in any pair, then the general equations connecting the various pairs is $P_1[(n_1)x]=6x -35-42n_1$ and $P_2[(n_2)x]=6x-49-42n_2$, where $x=1,2,3,4,5,6$ and $n_1,n_2=0,1,2...$ This is where the multiple of $42$ comes from.