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\Rightarrow r|a\text{ or }r|b$ is almost surely false in a probabilistic sense, and we quantify this with a corresponding asymptotic formula.

arXiv comment4 pages