The prime number is used for two reasons. One reason is that integers modulo simple forms represent a mathematical field. Arithmetic in a field works differently, like arithmetic on integers. This makes the field useful in certain problems of the competition, otherwise the sequences used in some cases may collapse. Certain arithmetic can give zero, other trivial results, or simpler results than we would like, because numbers are related to the coefficient of the module, which leads to some reduction or elimination.
Another reason is to get the programmer to deal with arithmetic for integers of a certain size. If a composite number was used, other methods could be used that did not resort to arithmetic with large integers.
For example, it is assumed that we want to know that 13 2 is modulo 35, but we only have a very small processor that cannot handle three-digit numbers, so it cannot calculate 13 2 = 169.
Well, 35 = 5 • 7 and 13 corresponds to 3 modulo 5 and 6 modulo 7. Instead of calculating the square 13, we can calculate the squares of these residues, which means that 13 2 coincides with 3 2 = 9 = 4 modulo 5 and is consistent with 6 2 = 36 = 1 modulo 7. Combining these residues requires some additional knowledge ( advanced Euclidean algorithm ). For these specific numbers, we can multiply the remainder of 5 by 21 and the remainder of 7 by 15 to get 4 · 21 + 1 · 15 = 99. Reducing this modulo 35 gives 29, which is the answer (remainder 13 2 modulo 35).
If the module is simple, this arithmetic bypass is not available. The original module essentially requires the use of arithmetic on numbers up to the square of the module (or time-consuming workarounds), but a composite module would allow the use of arithmetic on smaller numbers, up to double the module.