The theorem is constructive. You ask how a constructive mathematician woudl prove it. Just like you did!
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:
- Given $n$ and $k$, it is decidable whether $k$ divides $n$.
- 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.