Das Verfahren der vollständigen Induktion hängt eng zusammen mit der Menge der natürlichen Zahlen bzw. mit Teilmengen natürlicher Zahlen.

Bei vielen zahlentheoretischen Überlegungen spielen Teilbarkeitsbeziehungen eine Rolle.So kann man z. B.

Die natürliche Zahl a teilt die natürliche Zahl b (a | b), wenn es eine natürliche Zahl n gibt, sodass gilt b = n · a.

Eine Zahl ist durch 11 teilbar, wenn ihre Querdifferenz durch 11 teilbar ist.Eine Zahl ist durch 7 teilbar, wenn die Zahl, die aus ihr nach einem bestimmten Algorithmus ermittelt wird, durch 7 teilbar ist.

Eine Gleichung der Form a x + b y = c mit ganzzahligen Koeffizienten a, b und c, für die ganze Zahlen x und y als Lösungen gesucht sind, heißt eine (lineare) diophantische Gleichung in zwei Unbekannten.Diophantische Gleichungen können gelöst werden durch systematisches Probieren, mit der...

Als Beispiel für die Anwendung der Kongruenzrechnung werden hier mit deren Hilfe einige Teilbarkeitsregeln (so für 9 und 11) bewiesen. Diese Regeln können auch für Rechenkontrollen genutzt werden.