Integer is Coprime to 1
Jump to navigation
Jump to search
Theorem
Every integer is coprime to $1$.
That is:
- $\forall n \in \Z: n \perp 1$
Proof
Follows from the definitions of coprime and greatest common divisor as follows.
When $n \in \Z: n \ne 0$ we have:
- $\gcd \set {n, 1} = 1$
Then by definition again:
- $\gcd \set {n, 0} = n$
and so when $n = 1$ we have:
- $\gcd \set {1, 0} = 1$
$\blacksquare$
Sources
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $10$
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $12$