A pair of polynomial matrices,

and

, is defined to be "externally skew prime" if and only if a solution,

, to the polynomial matrix equation

exists. It is shown that

and

are externally skew prime if and only if

with

and

relatively left prime and

and

relatively right prime. This observation implies a new constructive procedure for determining

and

where

and

are found to be externally skew prime and

is nonsingular. A new procedure for obtaining solutions to the more general polynomial matrix equation,

, based on the notion of skew-prime polynomial matrices is also presented. A characterization of all solutions when

is also given, under appropriate assumptions, and then employed to determine a unique solution to this polynomial matrix equation.