# Cyclic order relation in Zn

The ring Zn:={0,1,..,n-1} under addition and multiplication modulo n. Suppose a,b,c,x $\in$ Zn are nonzero and the cyclic order R(a,b,c) holds, then under what conditions does R(ax,bx,cx) hold ?

-
If and only if $R(a(-x),b(-x),c(-x)$ doesn't? :-) (Well at least if $x$ is a unit modulo $n$). I can't see there being any sensible general answer to this. –  Robin Chapman May 21 '10 at 17:27

Answer. Under the condition $$\left\lbrace\frac{x(b-a)}n\right\rbrace<\left\lbrace\frac{x(c-a)}n\right\rbrace \qquad\qquad(*)$$ where $\lbrace\cdot\rbrace$ denotes the fractional part of a real number.

The condition $R(a,b,c)$ is equivalent to $R(0,b-a,c-a)$ and means that the least residues of $b-a$ and $c-a$ modulo $n$ are ordered in the increasing order as integers. Note that the least residue of an integer $m$ modulo $n$ can be expressed by means of $n\cdot\lbrace m/n\rbrace$.

The relations ($*$) are hardly related for different values of $x=1,2,\dots$: one can always construct $n$ and residues $a$ and $b$ in such a way that for a given range of $x\in X_1\cup X_2$ ($X_1$ and $X_2$ are two finite disjoint sets of $\mathbb Z_{>0}$) the inequality ($*$) hold for $x\in X_1$ and does not hold for $x\in X_2$.

-
So the answer doesn't depend on R(a,b,c) which means the question should have been "what is the most efficient way for an algorithm to check whether elements are in cyclic order?" and the answer is to change the cyclic relation to a linear relation by shifting 'a' back to zero. –  Roy Maclean May 23 '10 at 12:11
Yes, this would be the most appropriate question. And the answer I would prefer is $R(a,b,c)\iff\lbrace(b-a)/n\rbrace<\lbrace(c-a)/n\rbrace$. –  Wadim Zudilin May 23 '10 at 12:58
Although multiplication of all the elements by a factor does appear in the Dvornicich and Zannier paper in Charles Matthews answer. –  Roy Maclean May 23 '10 at 13:09
It appears in many other places (including my own articles) but this does not imply that the cases are related to the cyclic order. It's just a natural thing in the modular arithmetic to reduce residues to the least representatives. Note that Gauss proved the law of quadratic reciprocity by reducing residues to the absolutely least ones. –  Wadim Zudilin May 23 '10 at 14:27