The theorem is constructive.

**Theorem:** If $n \neq 1$ and $n$ divides both $a$ and $b$, then $b$ is composite or $b$ divides $a$.

*Constructive proof.* The proof given by OP in the question is constructive, provided we can prove the Lemma below. QED.

**Lemma:** A number $n > 1$ is either composite or prime.

*Constructive proof.* Let us be careful about the meaning of words here. By *composite* we mean "a product of two numbers, each of which is different from $1$". By *prime* we mean "a number $p > 1$ whose only divisors are $1$ and $p$". Since every number is dividisble by $1$ and itself, primality is equivalent to "a number $p > 1$ such that it has no divisor between $2$ and $p-1$."

Suppose $\phi$ is a decidable predicate on natural numbers, i.e., we have $\forall k \in \mathbb{N} \,.\, \phi(k) \lor \lnot\phi(k)$. Then also the predicates $\forall k \leq n \,.\, \phi(k)$ and $\exists k \leq n \,.\, \phi(k)$ are decidable. (Exercise, prove by induction on $n$.) Using this we can prove:

1. Given $n$ and $k$, it is decidable whether $k$ divides $n$.
2. Given $n$ it is decidable whether there is $k$ such that $2 \leq k < n$ and $k$ divides $n$.

But the second statement says that it is decidable whether $n$ is composite. To finish the proof we need to show that a number $n > 1$ which is not composite is prime. Suppose $n > 1$ is not composite. Consider any $k$ such that $2 < k < n$. Either $k$ divides $n$ or it does not. But it cannot divide $n$, or else $n$ would be composite. Therefore $n$ is prime. QED.