Prime Divisibility Lemma