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'm performing integer arithmetic modulo a number. I'm curious to know what happens if I take the result modulo a different number.

For example, $(10 \bmod 10) \bmod 100 \equiv 0$ and $(10 \bmod 100) \bmod 10 \equiv 0$.

As seen above, I've reversed the congruences. I'd like to know what properties hold, if any, when I switch congruences. The first property I've noticed is that $(a \bmod a\cdot b) \bmod a\cdot c \equiv (a \bmod a\cdot c) \bmod a \cdot b$.

Are there some simple generalized rules for this? I'd like to try to encompass the results of this switching of congruences in as little rules as possible, yet be able to describe as much behavior as possible. Can you please help?

share|improve this question
2  
You could precise the definition of ((a mod b) mod c) you are using. A usual definition of (a mod b) is the set a+bZ but you mean something else, obviously. Maybe (a mod b = c) iff c in Z is between 0 and b-1 and a-c is in bZ? –  Did Aug 20 '11 at 8:26
    
Hmm...Your second definition is more appealing. However, I'm simply trying to find if there's more than trivial information involved when switching congruences, like shown above. I'm wondering what the difference would be, though - it's not obvious to me how the definition changes things, unfortunately. –  Matt Groff Aug 20 '11 at 8:43
2  
The definition problem is this: when a mathematician writes $5\pmod3$, it means $\lbrace\dots,-4,-1,2,5,8,\dots\rbrace$, but when a programmer writes $5\pmod3$, it means 2. –  Gerry Myerson Aug 20 '11 at 10:27
    
I see - I'm still learning. I definitely had the programmer's perspective. I'm interested in both, but I have more use for the programming perspective. @Gerry Myerson: Thanks. :-) –  Matt Groff Aug 20 '11 at 10:42
add comment

3 Answers

up vote 0 down vote accepted

HINT $\:\ $ If $\rm\ \ b\ |\ c\: \lfloor a/c\rfloor\ $ and $\rm\ a\ mod\ c\ <\ b\ $ and wlog $\rm\ b < c\ $ then

$\rm\quad a\ mod\ b\:\ =\:\ (c\: \lfloor a/c\rfloor\ +\ a\ mod\ c)\ mod\ b\:\ =\:\ a\ mod\ c$

so $\rm\ (a\ mod\ c)\ mod\ b\:\ =\:\ (a\ mod\ b)\ mod\ b\:\ =\:\ a\ mod\ b\ =\ (a\ mod\ b)\ mod\ c$

That is the general solution if my quick back of the envelope caculation is in fact correct. It can be made much more explicit by factoring $\rm\: b\ =\ b_1\:b_2\:$ where $\rm\:b_1\:|\:c,\:\ b_2\:|\:\lfloor a/c\rfloor\:.\:$

share|improve this answer
add comment

(Using what was called in a comment the programmer's meaning of mod.) Considering that (10 mod 5) mod 9 = 0 but (10 mod 9) mod 5 = 1, and even that (21 mod 10) mod 15 = 1 but (21 mod 15) mod 10 = 6, one is led to doubt that the equality (a mod b) mod c = (a mod c) mod b may hold in general for nonnegative integers a, b and c, except when a is at most min{b,c}, or when b divides c or c divides b.

share|improve this answer
add comment

If you are using (what I've called) the programmer's meaning of mod, then the property you've found has nothing to do with multiplication; it's just that if $a$ is the smallest of the three numbers $a$, $b$, $c$, then $(a\mod\,b)\mod\,c=(a\mod \,c)\mod\,b=a$. Oh, I'm assuming all letters stand for non-negative integers. Another (fairly trivial) property is that if $a$ is a multiple of both $b$ and $c$ then $(a\mod\,b)\mod\,c=(a\mod\,c)\mod\,b=0$. Most of the time, reducing $a$ modulo $b$ destroys all information about the residue of $a$ modulo $c$, so I don't think you'll find a lot of non-trivial properties. But don't let that stop you from looking for them!

share|improve this answer
    
I'll keep looking. I'll report on any interesting findings. :-) –  Matt Groff Aug 20 '11 at 10:39
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.