# What's known about nested congruences?

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?

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

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

-

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

-

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!

-
I'll keep looking. I'll report on any interesting findings. :-) –  Matt Groff Aug 20 '11 at 10:39