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$.

Proof by contradiction

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$.

Dependency for:

  1. ϕ is multiplicative
  2. ab is coprime to x iff a and b are coprime to x
  3. Fundamental Theorem of Arithmetic Used in proof
  4. Zp is an integral domain
  5. Eisenstein's criterion
  6. Gauss' Lemma

Info:

Transitive dependencies:

  1. Integer Division Theorem
  2. GCD is the smallest Linear Combination