We say that a knot is $p$-colorable, where $p\ge 3$ is prime, if you can label the strands of the knot using labels from $\{0,1,2,...,p-1\}$, such that at each crossing, $$x+y=2z\pmod p,$$ where $x$ and $y$ are the labels of the two halves of the lower strand, and $z$ is the label of the strand going over. Additionally, it is required that at least two different labels appear, to prevent trivial cases.
Question: Why is this definition restricted to only primes?
I think it has something to do with how every nonzero $x \in \mathbb Z_p$ is invertible but, I don't know.
It would be equally valid to consider $p$-colorability of knots for any $p$, not just for prime $p$; it would just not add anything new. This is due to the following result about the composite generalization:
Theorem. A knot is $n$-colorable if and only if it is $p$-colorable for at least one prime factor $p$ of $n$.
Proof. One direction is quick. Given a $p$-coloring of a knot, where $p$ divides $n$, multiply every label by $\frac np$ and you get an $n$-coloring of the knot.
For the other direction, we will apply strong induction on $n$, where our base case will be every prime $n$. (If $n$ is prime, the statement of the theorem holds because it does not say anything.)
Suppose that a knot is $n$-colorable. We consider two cases, where $p$ is an arbitrary prime factor of $n$:
Case 1. If not all labels in the $n$-coloring are equal modulo $p$, then apply the function $t \mapsto t \bmod p$ to every label. Since $x + y \equiv 2z \pmod n \implies x + y \equiv 2z \pmod p$, this gives us a $p$-coloring.
Case 2. If all labels in the $n$-coloring are congruent to some $c$ modulo $p$, then apply the function $t \mapsto \frac{t-c}{p}$ to every label; this does not trivialize the labeling, because it is a bijection to $\{0,1,\dots,\frac np - 1\}$ from the elements of $\{0,1,\dots,n-1\}$ congruent to $c$ modulo $p$. If $x + y \equiv 2z \pmod p$, then $\frac{x-c}{p} + \frac{y-c}{p} \equiv 2 (\frac{z-c}{p}) \pmod {\frac np}$, so we get an $\frac np$-coloring of the knot. By induction, there is a $q$-coloring of the knot for some prime factor $q$ of $\frac np$, which is also a prime factor of $n$. This completes the case and the proof.
By the theorem, we do not gain anything extra from studying $n$-colorability for composite $n$. One last question: why do we limit ourselves to odd primes?
That's because it is impossible for a knot to be $2$-colorable. If $x+y \equiv 2 z \pmod 2$, then $x \equiv y \pmod 2$, so the label does not change at any crossing; by following the knot around, we see that every label must be the same, and so the supposed $2$-coloring is actually trivial.