What is the difference between working in $mathbb{Z}$ mod $p$ and working $mathbb{Z}_p$? I’m mainly interested in the terminology and nomenclature, I understand that the result would be the same.

This came after reading the documentation of NTL. Why do functions like `SqrRootMod`

live in ZZ, rather than ZZ_p? In the former case one has to explicitly state that “assumes n is an odd prime”. Is it because of the word “odd”, i.e. $mathbb{Z}_p$ could also include 2?

This is quite subjective, so I apologise if I’m missing the point of the question.

When we say that $a equiv b$ (mod $p$), we are referring to an equivalence relation $equiv$ on $mathbb{Z}$ defined by $a equiv b$ if and only if $a – b$ is a multiple of $p$. The transitivity of the relation is, in itself, very useful, as are many basic theorems that allow it to be treated “like an equals sign”.

On the other hand, $mathbb{Z}_p$, refers to the set of **equivalence classes** of $mathbb{Z}$ with respect to this relation. For instance, when we write $0 in mathbb{Z}_p$, we are really referring to the set ${ldots,-2p, -p, 0, p, 2p, ldots}$ of all elements of $mathbb{Z}$ that are equivalent to $0$ under the relation $equiv$. The reason we might want to do this is that $mathbb{Z}_p$ is a well-defined ring with respect to the obvious addition and multiplication; we can prove this directly by defining addition and multiplication of equivalence classes, or just observe that $mathbb{Z}_p$ is the quotient of the ring $mathbb{Z}$ by its ideal $pmathbb{Z}$ (hence the common notation $mathbb{Z}/pmathbb{Z}$ instead of $mathbb{Z}_p$).

Thus, when we apply our theorems about treating $equiv$ “like an equals sign”, what we are really doing is using the fact that the quotient by the equivalence relation gives a well-defined ring, and using properties of that ring to manipulate the equivalence classes of the integers on either side of $equiv$.

But we can go further! Everything so far applies equally well to any integer $n$ in place of $p$. When (and only when) $p$ is prime, we have the result that every nonzero element of $mathbb{Z}_p$ is **invertible**, by which we mean that for $a in mathbb{Z}_p setminus {0}$, there exists $b in mathbb{Z}_p$ such that $ab = 1$ (which follows from Bezout’s Lemma for $mathbb{Z}$, or just from the fact that $pmathbb{Z}$ is a maximal ideal of $mathbb{Z}$). This is the final step in verifying that $mathbb{Z}_p$ is not only a ring, but also a field (often denoted $mathbb{F}_p$ for this reason). Fields have many nice properties, so we can immediately apply many general theorems. For example, the ring $mathbb{F}_p[t]$ of polynomials with coefficients in $mathbb{F}_p$ is a principal ideal domain. An understanding of this field structure is essential to proving many actual concrete results, such as Eisenstein’s Criterion for the irreducibility of an integer polynomial, and Dedekind’s Theorem on the splitting of rational prime ideals in number fields.

So, to summarise this gargantuan ramble, writing $a equiv b$ (mod $p$) is a direct statement about $a$ and $b$, whereas $mathbb{Z}_p$ is an abstract construction. However, most of the useful properties of the former rely on the ring (and field) structure of the latter.

It is only a formal difference. We just can write a congruence

$$

x^2equiv 1bmod 17

$$

as an equation $x^2=1$ in $Bbb F=Bbb Z/17Bbb Z$. The latter form is sometimes more convenient. For example, since $Bbb F$ is a field, the equation $x^2-1=(x-1)(x+1)$ has exactly two solutions, namely $x=1$ and $x=-1$. This is perhaps easier to see when we look at an equation over a field rather than a congruence.