2
$\begingroup$

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?

thanks!

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Henning Makholm Oct 25 '12 at 16:03
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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) $\endgroup$ – Hagen von Eitzen Oct 25 '12 at 15:55
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.