1
$\begingroup$

If there is a function $f(x) = x\bmod n$ and, whenever $0\leq x_1\lt x_2\lt n$, we have $f(x_1)\lt f(x_2)$, can we say that $f$ is increasing?

Also, when finally I prove that $f(x)$ is increasing, how do I say it is doing so "modular arithmetically". I want to be able to specify that the function is increasing by the definition of increasing functions that is used for modular arithmetic.

Disclosure: I'm not a mathematician: I'm a student programmer who loves math. I'm working on proving that a given algorithm satisfies the requirements for being a solution to the critical section problem. This is homework, but the answer to that question is not homework.

Thanks!

z.

PS I post on stackoverflow but this is my first question here.

  • 0
    Thanks! Your thorough treatment warms my heart. Congruence class is$a$really cool word. I've learned a lot just by asking this question. This stack is a good stack.2012-03-03

2 Answers 2

4

Mathematicians don't usually put orderings on rings with positive characteristic, since we like to be able to say things like $x for all $x$.

But there's no reason you can't order the residue classes by setting $[x]<[y]$ whenever $0\leq x,y. In other words, $[0]<[1]<\ldots <[n-1]$. Be careful though. For example, if this is your ordering mod 5, then $[-1]>[12]$ since $[-1]=[4]$ and $[12]=[2]$.

Just make sure that your ordering does not depend on which representative you pick from each class. (This is the definition of well-defined.)

As far as terminology goes, this is a nonstandard thing, so it's worth explaining your ordering. Then you can say "$f$ is increasing with respect to this ordering."

  • 0
    Be wary of saying "$f(x)$ is increasing except where $x=n$," since I don't know if the exception is between $n$ and $n+1$ or between $n-1$ and $n$. It is best to explicitly define your ordering and say that the function is increasing with respect to the ordering.2012-03-02
1

If you want to have $x+1\gt x$ for all $x$, then there is no way to order the integers modulo $n$.

If you are willing to settle for $0\lt1\lt2\lt\cdots\lt n-1$, and you have a function with $x\lt y$ implying $f(x)\lt f(y)$, then your function can only be the identity function, $f(x)=x$ for all $x$.