I got a very satisfiying answer to my question on the relation between primeness and co-primeness of numbers which can be defined in a somehow symmetric way:
$n$ is prime iff
$$(\forall xy)\ n\ |\ x \vee n\ |\ y \leftrightarrow n\ |\ x\cdot y$$
$n, m$ are co-prime iff
$$(\forall x)\ n\ |\ x \wedge m\ |\ x \leftrightarrow n\cdot m\ |\ x$$
The answer made use of categorical language (as the terms prime and co-prime suggest), explaining the analogy by products and co-products.
Now I came up with another definitional symmetry, and I'd like to know how it can be "explained", possibly again in a categorical framework:
- n is a residue modulo $m$ iff
$$(\exists x < m)\ \operatorname{gcd}(x,m) = 1 \wedge (\exists k)\ x^k \equiv n \pmod{m}$$
- n is a primitive root modulo $m$ iff
$$(\forall x < m)\ \operatorname{gcd}(x,m) = 1 \rightarrow (\exists k)\ n^k \equiv x \pmod{m}$$
To ask more pointedly: Are residues some kind of a (categorical) co-concept of primitive roots?