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)$


$ p \land r $

$ r $

$ r \implies \lnot q $

$ \lnot q$

$q \iff \lnot s$


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

Is this correct?

  • 2
    $\begingroup$ $1$ is the smallest divisor of every natural number. $\endgroup$ – Adam Hughes Aug 1 '14 at 5:55
  • 1
    $\begingroup$ Well $1$ would be the least positive divisor. In general for a natural number $n$, $-n$ would be the least divisor. $\endgroup$ – 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$.

I don't see how this was involved in your proof. Alternatively, you could use the definition of irreducibility and apply the prime factorization theorem to get a proof closer to the one you are suggesting. In this case, I think you are close, except you need to add existential quantifiers to some of your statements.


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.


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.