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:

$$(\exists x < m)\ \operatorname{gcd}(x,m) = 1 \wedge (\exists k)\ x^k \equiv n \pmod{m}$$

$$(\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?

  • $\begingroup$ 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$. $\endgroup$ – darij grinberg Jan 8 at 12:28
  • $\begingroup$ 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)? $\endgroup$ – Hans-Peter Stricker Jan 8 at 12:34
  • $\begingroup$ 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 :) $\endgroup$ – darij grinberg Jan 8 at 12:47
  • $\begingroup$ 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.) $\endgroup$ – Hans-Peter Stricker Jan 8 at 13:07
  • $\begingroup$ @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. $\endgroup$ – Hans-Peter Stricker Jan 8 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.