If you're working over the integers, here's the intuition: since p|mq, you can imagine taking all the prime factors of p, and dividing as many of them as possible into q, with the remaining ones dividing m. Likewise, the remaining ones divide n, since p|nq. But (m,n)=1, so in fact all the factors of p can be divided into q.