GCD with Prime
Jump to navigation
Jump to search
Theorem
Let $p$ be a prime number.
Then:
- $\forall n \in \Z: \gcd \set {n, p} = \begin{cases} p & : p \divides n \\ 1 & : p \nmid n \end{cases}$
Proof
The only divisors of $p$ are $1$ and $p$ itself by definition.
$\gcd \set {n, p} = p$ if and only if $p$ divides $n$.
Hence the result.
$\blacksquare$