# Relation between residues and primitive roots modulo $p$

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?

• The "residue" statement looks wrong; basically, I don't think any such statement without a $2$ somewhere in it has any chance to be true. As for the "primitive root" statement, it becomes true if you require $x$ to be coprime to $m$. – darij grinberg Jan 8 at 12:28
• Thanks for the hint concerning primitive roots, I corrected the definition. Note that both "statements" are considered to be definitions. What can be wrong with the first one? And aren't there - next to quadratic residues - cubic and biquadratic residues (which are residues by my definition)? – Hans-Peter Stricker Jan 8 at 12:34
• You are defining words that are already defined, so the definitions should be equivalent. The "primitive root" one is now correct. As for the "residues" one, every integer $x$ coprime to $m$ is a residue according to your new definition. Probably not what you want :) – darij grinberg Jan 8 at 12:47
• I just wanted to *restate" the definitions (that admittedly already exist, at least the second one) in a unified manner - to highlight some kind of "syntactical symmetry". That's what it's all about. (Now I have to fix the definition of residues.) – Hans-Peter Stricker Jan 8 at 13:07
• @darijgrinberg: My new definition of "residue" is stronger than the old one, so what you say must hold already for the older, i.e. the weaker one. But probably both are not what I want. – Hans-Peter Stricker Jan 8 at 13:11