1
$\begingroup$

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?

  • 0
    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. :-)2011-08-20

3 Answers 3

-1

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

1

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

0

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!

  • 0
    I'll keep looking. I'll report on any interesting findings. :-)2011-08-20