On the Success of Mishandling Euclid's Lemma

Abstract

We examine Euclid's lemma that if p is a prime number such that p |ab, then p divides at least one of a or b. Specifically, we consider the common misapplication of this lemma to numbers that are not prime, as is often made by undergraduate students. We show that a randomly chosen implication of the form r|ab ⇒ or r|b is almost surely false in a probabilistic sense, and we quantify this with a corresponding asymptotic formula.