Why modulo prime prefered over modulo composite? In encryption process (aes encryption), and also in Galois field, a prime number is always used to perform the modulo operation. So I wanted to know the reason for using only prime numbers for modulo operations ?
 A: The nice things about primes is that when looking at the numbers modulo a prime, you can always "divide" by anything non-zero.
In particular, if you want to solve the equation
$$
ax \equiv b \pmod p
$$
where $a \not \equiv 0$, and $b$ is any number, there exists some $(1/a)$, so that
$$
(1/a)ax \equiv (1/a)b
$$
or in other words,
$$
x \equiv b/a
$$
In mathematical terms, the numbers modulo a prime form a field, whereas the numbers modulo a composite number only form a ring.
To see how this doesn't work for composites, note that
$$
2x \equiv 1 \pmod 6
$$
has no solution, which is to say that $2$ has no multiplicative inverse.
A: Two facts come to my mind:


*

*$\Bbb{Z}/n\Bbb{Z}$ has a ring structure. The set of non-zero elements of $\Bbb{Z}/n\Bbb{Z}$ is a (cyclic) group under multiplication if and only if $n$ is a prime number.

*Let $n= p_1^{a_1} \cdots p_r^{a_r}$. Chinese Remainder Theorem tells you that $$x = y \mod{n}$$
is equivalent to 
$$x = y \mod{p_i^{a_i}} \ \ \ \ \mbox{for all } i$$
so modular equations can be split into simpler ones.
