Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been studying a particular unary operator on the commutative ring $\mathbb{Z}/n\mathbb{Z}$. The operator is:

$\downarrow(x) = y\pmod{n}$ iff $n \equiv y \pmod{x}$, where $0< x,y \le n$.

The operator isn't distributive on addition or multiplication, so its use is probably fairly limited. I've proven a couple fairly trivial results, but I'm interested in seeing if there are more resources available.

One of the fairly trivial results: If $n$ is composite and $n=pq$ and WLOG $p \le q$, then if $q\ge kp+k$ I can show that

$(\downarrow(q-k))\mid p$.

share|improve this question

2 Answers 2

This is not really an operator on $\mathbb{Z}/n\mathbb{Z}$, it's an operator on the numbers $\{1,2,\ldots, n\}$. The reason is that if $x\equiv x'\pmod{n}$, we would expect any such operator to satisfy $\downarrow (x)=\downarrow(x')$, but this one doesn't.

share|improve this answer
The definition of the operator can be extended trivially to satisfy this property, though. –  Foo Barrigno May 30 '13 at 18:59
Alas, it cannot. $n\equiv y\pmod{x}$ means $x|(n-y)$. $n\equiv y\pmod{x+n}$ means $(x+n)|(n-y)$. These two are rarely both true, and that's just for one choice of $x'$. Try some examples and you'll see. –  vadim123 May 30 '13 at 19:09
The "trivially" part was mapping x to the value I the range. In that sense, yes, it's an operator on the numbers {1,2,...,n}, but as long as you're rigorous about how the operator acts on each congruence class, it should be fine. –  Foo Barrigno May 30 '13 at 22:07

Yes. If the modulus is prime $\, n = p,\,$ then iterating the map $\ x\mapsto p\ {\rm mod}\ x\ $ yields Gauss's algorithm for computing inverses mod $\,p.\,$ By this variant of the Euclidean algorithm, Gauss deduced the prime divisor property, i.e. if a prime divides a product then it divides some factor, which immediately yields uniqueness of prime factorizations (fundamental theorem of arithmetic).

share|improve this answer
I have looked at iterating it, for composite numbers primarily, but it's neat to see that it's connected to Gauss too. A property of the iterated version: for a given n, the number of x's which terminate at 1 (assuming termination halts before x=0) is n-2 iff n is prime. It's like a weird version of the totient function. –  Foo Barrigno May 30 '13 at 22:40
I meant iff n-1 is prime. Whoops! –  Foo Barrigno May 30 '13 at 22:49
@KeyIdeas I had read one of your posts about Gauss's Algorithms I was wondering if it was called something else officially. I'd simply like to read up on it, but I can't find its wikipedia page. –  AlanH Jun 2 '13 at 21:44
@AlanH I don't know any other expositions (it is not well-known). Besides the above-linked answer, see also this answer. If, after that, the algorithm remains unclear then let me know what proves troublesome and I can explain further. –  Key Ideas Jun 3 '13 at 0:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.