Größter Gemeinsamer Teiler

Description

The greatest common divisor gives the greatest number in a ring that dives two numbers. But more importantly it allows us to define what Coprime Numbers are.

Definition

Let $R$ be a Ring where $a_1,...,a_n\in R$. We say an element $d\in R$ is the greatest common divisor (in short gcd) of $a_1,...,a_n$, if

1. $d\mid a_i$ for $1\le i\le n$
2. If $b\in R$ where $b|a_i$ for $1\le i\le n$, then $b\mid d$

Note: The greatest common divisor is only unique up to units.

Examples

Natural numbers

See Größter gemeinsamer Teiler (Natürliche Zahlen).

Special powers

Let $t\in R$ and $m,n\in \mathbb{N}$, then: $ggT(t^n-1,t^m-1)=t^{ggT(n,m)}-1$ Dieses Satz gibt eine Möglichkeit für spezielle große Zahlen den ggT schnell zu berechnen.