Ich glaube ich habe eine Ahnung was der mathematische Hintergrund davon ist, danach hattest du ja gefragt.

Grundsätzlich liefert die Modulo-Funktion ja den ganzzahligen Rest bei einer Division zweier ganzen Zahlen.
Dadurch läßt sich jede ganze Zahl durch modulo p auf ihren Rest abbilden. (p ist dein Divisor, im Prinzip eine zufällig gewählte ganze Zahl).

Wenn p jetzt eine Primzahl ist, hat deine Menge von Restklassen (bzw. die Reste, auf die du jede ganze Zahl abbildest) einige nette Eigenschaften, genau genommen bildet Z faktorisiert durch p dann einen Körper.
Die wichtigste Eigenschaft ist hierbei zum einen die Nullteilerfreiheit, wenn a*b = 0 gilt muss a oder b = 0 sein. Ist p keine Primzahl so ist dies nicht der Fall.
(Bspw bei Z modulo 6 gilt: 2*3 = 0 da 2*3 = 6 ist welches geteilt durch 6 den Rest 0 hat.)
Auch weiß man, das bei einem Körper die multiplikativ Inversen zu jeder Zahl ungleich 0 existieren und eindeutig sind. Dadurch kann man Gleichungen sehr viel einfacher lösen.

Ich denke diese Eigenschaften spielen bei der Verschlüsselung eine wichtige Rolle, weswegen man als Divisor eine Primzahl nimmt.