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.

  • $\begingroup$ Is this the entire solution? $\endgroup$ – Brian J. Fink Mar 12 '14 at 4:55
  • $\begingroup$ @BrianJ.Fink There was also a table included $\endgroup$ – qwr Mar 12 '14 at 4:57
  • $\begingroup$ Maybe this has some significance: $42=2\cdot3\cdot7$ $\endgroup$ – 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$.

  • $\begingroup$ Actually you need to consider $r = 1$ too, and go until $1, 43, 85$, but you can stop there. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.