Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have encountered this phrase within a proof by prime numbers and couldn't figure out if it is true.

Is there any proof lurking around for this fact?


share|cite|improve this question
up vote 5 down vote accepted

Suppose for contradiction that $x\neq 3$ is divisible by $3$ and is prime. Then the only numbers dividing $x$ are $1$ and $x$. But $3$ divides $x$. So we have $x=1$ or $x=3$. Each of these is a contradiction.

share|cite|improve this answer
Or even better, lose the indirection and say: Suppose that $x$ is divisible by $3$ and is prime. Then the only numbers dividing $x$ are $1$ and $x$. But $3$ divides $x$. Since $3$ is not $1$, we must have $3=x$. – Henning Makholm Oct 25 '12 at 16:03

If a number is divisible by $3$ and it's not $3$, then the number is not prime.

share|cite|improve this answer
Well that's not much more than a reformulation (but it's hard to make obvious things more obvious -they are just not obvious for everyone) – Hagen von Eitzen Oct 25 '12 at 15:55

Well, it's trivial (and this is sometimes the reason to make it so hard to see).

To avoid getting confused by trivialities, it is often helpful to re-formulate the statement. Here, for example: "Any number (positive integer) other than 3 that is divisable by 3 is not a prime". See it? Once again:

Let $x \not= 3$ be any positive integer that is divisable by $3$. Can $x$ be a prime number?

share|cite|improve this answer

Hint $\ $ If $\rm\:ab\:$ is prime then $\rm\:a > 1\:\Rightarrow\: b=1\:\Rightarrow\:ab =a.\:$ Yours is the special case $\rm\:a = 3.$

share|cite|improve this answer

Just observe that any multiple of 3 must repeat that 3 some number of times, and that number would be its factor. For example 6 is 2*3. 9 is 3*3. 12 is 4*3. As you can see, each multiple of 3 has two factors, of which one is 3, and the other is some natural number. And if there are factors, you have a composite number, which is the opposite term for prime number (if something is composite, it cannot be prime). The only multiple of 3 which doesn't have any factors beyond 3 (and 1, which we usually don't consider as factor, since it doesn't produce anything new) is the number 3 itself, which is prime.

share|cite|improve this answer

Suppose $a\neq 3$ is a positive multiple of $3$. Then $a > 3$ and $3$ is a divisor that is not $1$ or $a$...hence $a$ cannot be prime.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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