7
$\begingroup$

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...

$\endgroup$
5
  • $\begingroup$ While you could look at $p,p+2$ and $p+4$ mod 3 as one idea I suspect this is using the division algorithm unfortunately. $\endgroup$
    – JB King
    Commented Aug 30, 2015 at 22:13
  • 1
    $\begingroup$ It's rather difficult not to use the division algorithm. It's sufficiently central a property to $\mathbb{N}$ that it's rather like saying "without using addition". $\endgroup$
    – Patrick Stevens
    Commented Aug 30, 2015 at 22:15
  • $\begingroup$ Not sure does this qualify as division algorithm but all of the primes bigger then $3$ are of the form $6k\pm 1$ hence there can be at most $2$ consecutive primes which differ by $2$. $\endgroup$
    – kingW3
    Commented Aug 30, 2015 at 22:25
  • $\begingroup$ It is rather difficult to avoid using the division algorithm, at least implicitly, because the primality of numbers has to do with the multiplicative structure, and the integers in question are defined by the additive structure. One could use a special case - as with odd and even numbers - but a natural number is odd iff it leaves remainder $1$ on division by $2$, so we are already into division, even though we may not have named it. $\endgroup$
    – Mark Bennet
    Commented Aug 30, 2015 at 22:37
  • 2
    $\begingroup$ Actually, another possibility is $p = -7$. $\endgroup$
    – Bob Happ
    Commented Aug 31, 2015 at 21:24

2 Answers 2

Reset to default
7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .