  Let $X$ be a right Hilbert module over a $C^*$-algebra $A$ equipped with the
canonical operator space structure. We define an elementary operator on $X$ as
a map $\phi : X \to X$ for which there exists a finite number of elements $u_i$
in the $C^*$-algebra $\mathbb{B}(X)$ of adjointable operators on $X$ and $v_i$
in the multiplier algebra $M(A)$ of $A$ such that $\phi(x)=\sum_i u_i xv_i$ for
$x \in X$. If $X=A$ this notion agrees with the standard notion of an
elementary operator on $A$. In this paper we extend Mathieu's theorem for
elementary operators on prime $C^*$-algebras by showing that the completely
bounded norm of each elementary operator on a non-zero Hilbert $A$-module $X$
agrees with the Haagerup norm of its corresponding tensor in
$\mathbb{B}(X)\otimes M(A)$ if and only if $A$ is a prime $C^*$-algebra.
