And in passing it is well to point out that the Euclidean Algorithm provides the missing link in our proofof the uniqueness ofprime factorization as it allows us to verify the euclidean property that if a prime p is a factor of the product ab, so that ab=pc say, then p is a factor ofat least one ofa and b. The reason for this is that ifp is not a factor ofa then, since p is prime, the hcfofa and p is 1. By reversing the Euclidean Algorithm when applied to the pair a and p, we can then find integers r and s say such that ra+sp=1. This is enough to show that p is then a factor ofb for, since ab=pc, we have: