# Logically proving that the smallest factor of an integer is prime

I argued it as follows, let $p, q, r$ and $s$ be predicates

$p$: "$m$ is divisible by $k$"

$q$: "$k$ is divisible by $n$ ($n < k$ and $m$ is divisible by $n$) "

$r$: " $k$ is the smallest factor of $m$ other than $1$"

$s$: "$k$ is prime"

The true arguments: $(p \land r), (q\iff\lnot s), (r \implies\lnot q)$

Argument:

$p \land r$

$r$

$r \implies \lnot q$

$\lnot q$

$q \iff \lnot s$

$s$

$\therefore p \land r \implies s$ = If $k$ is the smallest factor of any integer $m, k$ is prime.

Is this correct?

• $1$ is the smallest divisor of every natural number. – Adam Hughes Aug 1 '14 at 5:55
• Well $1$ would be the least positive divisor. In general for a natural number $n$, $-n$ would be the least divisor. – Peter Woolfitt Aug 1 '14 at 6:05

Consider the inverse: that there exists an integer $m$ where the smallest factor $n$ is not prime. If that is the case then there exists a prime integer $k$ such that $k < n$ and $k$ divides $n$, thus $k$ also divides $m$, which is a contradiction.
I think there should be some more precision regarding definitions. For instance, the statement "$p$ is prime" is equivalent to saying:
For every pair $a,b$ of integers such that $p$ divides $ab$, one of $a$ or $b$ is divisible by $p$.
Not really a good "strict" proof, if you ask me. For example, you just assumed that $r\implies \neg q$ is true, I see no reason why I should (strictly speaking) believe that.