Teilerfremdheit
Zwei natürliche Zahlen "a" und "b" sind teilerfremd (relativ prim) wenn es keine natürliche Zahl außer der Eins gibt, die beide Zahlen teilt. Wenn zwei natürliche Zahlen keinen gemeinsamen Primfaktor haben, sind sie teilerfremd. Jede natürliche Zahl teilerfremd zu 1 ist, auch die Zahl 1 selbst. Zum Nachweis der Teilerfremdheit berechnet man gewöhnlich den größten gemeinsamen Teiler: Zwei Zahlen sind genau dann teilerfremd, wenn 1 deren größter gemeinsamer Teiler ist.
Die Zahlen 16 und 17 sind teilerfremd, denn ihre Primfaktorzerlegungen 16 = 24 und 17 = 17 enthalten keine gemeinsamen Primfaktoren. Die Zahlen 16 und 24 sind nicht teilerfremd, denn in ihren Primfaktorzerlegungen 16 = 24 und 24 = 23 * 3 kommt jeweils die 8 vor, die zugleich ggT(16, 24) ist. Euklidischer Algorithmus