Suppose $p, p+2, p+4$ are prime numbers. Prove that $p = 3$ not using division algorithm.

Suppose $p, p+2, p+4$ are prime numbers. Prove that $p = 3$ not using division algorithm. Hint: why can’t $p = 5$ or 7?

So I have done the two hints and in both cases I get a 9 in my set of numbers, 9 is not prime. But now my issue is how do I extend this idea to all other prime numbers except for $p = 3$? I don’t know for sure that for every other prime greater than 3 that when 2 or 4 are added to it that I will get a composite number. I am thinking contradiction perhaps…

Solutions Collecting From Web of "Suppose $p, p+2, p+4$ are prime numbers. Prove that $p = 3$ not using division algorithm."

Not exactly sure what you mean by “division algorithm”, but I have a feeling that the best, most direct way to prove this involves that algorithm. So what I will use instead is the base 3 representation of $p, p + 2, p + 4$.

If $p$ is a prime greater than 3, its base 3 representation ends in 1 or 2. If the base 3 representation of $p$ ends in 1, then the base 3 representation of $p + 2$ then ends in 0, which means it’s a multiple of 3, and we know that without actually having to compute $\frac{p + 2}{3}$.

If the base 3 representation of $p$ ends in 2, then the base 3 representation of $p + 2$ ends in 1, so that might be a prime number as well. But then the base 3 representation of $p + 4$ ends in 0.

There is only one prime such that its base 3 representation ends in 0, and that’s 3 itself. Then 5 in base 3 is 12 and 7 is 21.

Meditation: What is so special about 9? Why is 9 not prime?

Meditation: what is so special about 3 that means it can be magically exempt from the restrictions that make $p$ invalid for any other prime?

(Do think about those before going on.)

The two of those together imply that we’re going to want to use that “a multiple of 3 is always in that triple”. The reason that’s enough is because $p=3$ is the only way we can get a prime which is also divisible by 3.

Reduce the whole thing modulo $3$ and you have the result immediately, although that is kind of cheating, implicitly using the division algorithm. Instead, I’d probably use the pigeonhole principle: if none of them is divisible by 3, then at least two have the same parity mod 3. (Still kind of uses the division algorithm, but less clearly.) Subtract the two, and we get something which is divisible by 3. But that means 1 or 2 or 4 is divisible by 3. Contradiction.