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:

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.

You ask how a constructive mathematician would prove the theorem. Just like you did! We only need to verify that every number is either composite or prime, see below. But Carl Mummert gave the "proof from the book", which is constructive:

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

Constructive proof (Carl Mummert). Either $n = b$ or $n \neq b$. If $n = b$ then $b$ divides $a$. If $n \neq b$ then $b$ has a non-trivial divisor and is composite. QED.

Here is your proof, worked out in a bit more detail.

Constructive proof. If $n$ is not composite then it is prime by the Lemma below. Because $n$ divides $b$ it follows that $b = n$, hence $b$ divides $a$. 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.

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.

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:

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.