Proof of a statement on prime numbers

Question

Determine if the following statement is true or false.
There exists a non-prime $n\in\Bbb N$ such that for all proper divisors $k$ of $n$ there exists $t\in\Bbb Z\setminus\{1,k\}$ with $t|k$.

I proved that the statement is false by contradiction. Let $n=4$ and $k=2$, then $2\mid4=2$ and $t$ does not exist.

Can I have some feedback on my answer?

To me, you only prove that $n=4$ does not have the property. The fact that $n=4$ does not work, does not show that no $n$ works. What if I claimed $n=8762346238789$ had this property? — Jeppe Stig Nielsen, Aug 22 '16 at 22:35
If $t\in\mathbb{Z}$ is not just a typo (@shardulc's comment), we can always choose $t=-1$, and it is very easy to find examples of such an $n$. — Jeppe Stig Nielsen, Aug 22 '16 at 22:40
You can use \not to put a diagonal "negation" thru a symbol. E.g. \not \in gives $\not \in.$ And there is \ne for $\ne.$ — DanielWainfleet, Aug 22 '16 at 23:09

score 1 · Answer 1 · answered Aug 22 '16 at 22:48

You did not prove the statement is false, because the statement is in the form $\;\exists n\in \mathbf N, P(n)$, where $P(n)$ denotes some assertion about $n$.

Therefore, to prove it's false, you should prove that $\;\forall n, \neg P(n)$. However you only prove there exists an $n$ such that $P(n)$ is false.

A correct proof would interpret first what the statement means: there exists an $n$ such that all its non-trivial divisors have non-trivial divisors, i. ee. all its non-trivial divisors are non-primes.

Unfortunately, a fundamental lemma to prove the decomposition of any natural number into primes is the following:

Let $n$ be a natural number $>1$. The smallest natural number $k>1$ which divides $n$ is prime.

It's easy to prove this lemma by contrapositive: a divisor $k>1$ which is not prime can't be the smallest divisor $>1$.

score 1 · Answer 2 · answered Aug 23 '16 at 03:10

Let $n $ be a composite number. Let $k$ be the least factor. Let $t|k $. And $k|n $ so $t|n $. But $k $ was the least proper divisor so $t$ can not be a proper divisor less than $k $. In other words it is not the case $1 <t <k $ so $t=1$ or $t=k $. So $n $ does not have the property. $n $ was arbitrary. So no $n $ has the property.

And as has been pointed out in the comments, a single counterexample does not demonstrate that no such other number is possible.

Prove whether the exist an odd prime. $p=2$ is a counter example. Does that mean odd primes are impossible? $n=57$ is a counterexample of a number not being larger than $1000$. Does that mean there are no numbers larger than $1000$.

Proof of a statement on prime numbers

2 Answers2