In this paper, the problem of obtaining a pair of relatively prime polynomial matrices from two given polynomial matrices is considered. A method to check relative primeness, in the form of a rank condition on a constant matrix, as well as an algorithm to obtain relatively polynomial matrices is developed.