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.

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.

share|improve this question
    
I think you mean "$x_1\lt x_2\Rightarrow f(x_1)\lt f(x_2)$", rather than what you wrote. –  Arturo Magidin Mar 2 '12 at 5:12
    
What, exactly, is your domain and your codomain? Are you mapping to/from congruence classes, or residue representatives? –  Arturo Magidin Mar 2 '12 at 5:13
    
It shouldn't be. Residues modulo $n$ don't have a natural notion of order (they do have an unnatural one given by the usual order on $\{ 0, ... n-1 \}$). –  Qiaochu Yuan Mar 2 '12 at 5:15
    
I certainly did mean "x_1 < x_2 => f(x_1) < f(x_2)" but only so long as x < n. Whenever x = n f(x) will be zero, which is probably less than f(x - 1). This is the question. Actually, maybe my question is whether < is meaningful in modular arithmetic. @Arturo as I said I am not a mathematician, and I do not understand your question. f(x) takes an integer argument and the result is an integer? –  Ziggy Mar 2 '12 at 5:23
    
As Qiaochu says, we do not usually consider the set of residue classes modulo $n$ (the results of applying the $\bmod n$ operator) to be ordered, because there is no order that has "nice properties." You can assign an arbitrary order and say that $f$ is "increasing" relative to that order, but if you just say that $f$ is "increasing", then nobody will understand that you mean the condition you have listed. So your best bet is to just state the condition explicitly: "If $0\leq x_1\lt x_2\lt n$ then $f(x_1)\lt f(x_2)$, where we order $\{0,1,2,\ldots,n-1\}$ with its usual order." –  Arturo Magidin Mar 2 '12 at 5:27
show 2 more comments

2 Answers

up vote 4 down vote accepted

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

But there's no reason you can't order the residue classes by setting $[x]<[y]$ whenever $0\leq x,y<n$. 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."

share|improve this answer
    
Hmm... I like where you are going with this, but did not understand your answer completely. From your first paragraph though I gather that the answer is "no, there is no concept of an increasing function in modular arithmetic"? In which case I'll have to say something like, f(x) is increasing, except where x = n? –  Ziggy Mar 2 '12 at 5:26
    
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. –  Brett Frankel Mar 2 '12 at 5:29
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

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.