Teilerfremdheit

In der Mathematik werden zwei ganze Zahlen a und b als teilerfremd (oder relativ prim) bezeichnet, wenn ihr größter gemeinsamer Teiler 1 ist, also ggt(a, b) = 1. Es gibt also keine natürliche Zahl (außer 1), die sowohl a, also auch b teilt. Dies bedeutet auch, dass die zwei Zahlen keinen gemeinsamen Primfaktor besitzen.

Teilerfremdheit kommt, häufig als Bedingung, in vielen zahlentheoretischen Problemen vor. Zum Beispiel ist eine Voraussetzung für den Chinesischen Restsatz, das die Moduln teilerfremd sind. Die Eulersche φ-Funktion ordnet jeder natürlichen Zahl n die Anzahl der zu n teilerfremden Zahlen, die kleiner als n sind, zu.