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 ϕ:X→X for which there exists a finite number of elements ui in the C⁎-algebra B(X) of adjointable operators on X and vi in the multiplier algebra M(A) of A such that ϕ(x)=∑iuixvi for x∈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 B(X)⊗M(A) if and only if A is a prime C⁎-algebra.