Euclid's lemma

Dependencies:

1. GCD is the smallest Linear Combination Used in proof

Let $p$ be a prime. If $p \mid ab$, then $p \mid a \vee p \mid b$.

Assume $p \not\mid a \wedge p \not\mid b$.

\begin{align} &\Rightarrow \gcd(p, a) = 1 \\ &\Rightarrow \exists r \exists s \textrm{ such that } pr + as = 1 \\ &\Rightarrow prb + asb = b = p(rb) + s(ab) \\ &\Rightarrow p \mid b \Rightarrow \bot \end{align}

This is a contradiction, which means $p \mid a \vee p \mid b$.

Info:

• Depth: 2
• Number of transitive dependencies: 2