# $a\equiv\bar a\!\pmod{\!kn}\Rightarrow a\equiv\bar a\!\pmod{\! n};\$ $(a\bmod kn)\bmod n=a\bmod n.\$ Congruences persist mod factors of the modulus

I noticed relation between modulo operation and number which is power of two

Example I have to calculate $3431242341 \mod 2^5$, which is $5$ but it is equivalent to $( 3431242341 \mod 2^9 ) \mod 2^5$

I tried many examples and it seems to be true in general, and I am not sure if it is a coincidence or true in general that I can use first modulo operation ( greater number) and the result will be the same.

• The crucial fact is not that the first modulus ($2^9$) is greater, but that it is a multiple of the other modulus. – Daniel Fischer Jul 30 '14 at 19:47
• This can be understood intuitively in radix arithmetic - see my answer. – Bill Dubuque Jul 30 '14 at 21:33

## 3 Answers

The phenomenon you observed holds in greater generality.

Suppose that $$m$$ and $$n$$ are positive integers such that $$m$$ divides $$n$$. Then for any integer $$a$$ we have $$(a\bmod n)\bmod m= a\bmod m$$.

Certainly $$(a\bmod n)\bmod m$$ is of the right size, between $$0$$ and $$m-1$$.

Since $$a$$ and $$(a\bmod n)$$ differ by a multiple of $$m$$, it follows that the remainder when $$(a \bmod n)$$ is divided by $$m$$ is the same as the remainder when $$a$$ is divided by $$m$$, which is what we needed to show.

Suppose $a\equiv b \mod pq$ and $b \equiv c \mod p$, then we have $$a=rpq+b=rpq+(sp+c)=(rq+s)p+c$$ so that $a\equiv c \mod p$

$$\begin{eqnarray}{\bf Hint}\qquad &&\ (a\ {\rm mod}\ kn)\ {\rm mod}\ n\\ &=&\, (a\ -\ q\:kn)\ {\rm mod}\ n\\ &=&\,\qquad\qquad\ a\,\ {\rm mod}\ n\end{eqnarray}$$

Example  The parity of an integer $$\,a\,$$ is the parity of its least significant (units) decimal digit, i.e.

$$\ \ \, \begin{eqnarray} a\ {\rm mod}\ 2\, &=&\, (a\ {\rm mod} &10)& {\rm mod}\ 2\\ &=&\qquad\quad &a_0& {\rm mod}\ 2,\,\ \ a_0\! = \text{units decimal digit of }\, a\end{eqnarray}$$

Hence an integer is even iff its units digit is even, and it is divisible by $$5$$ iff its least digit is, and it is divisible by $$10^5$$ iff its least digit in radix $$10^{\large 9}$$ is, since $$\ a\ {\rm mod}\ 10^{\large 5} = (a\ {\rm mod}\ 10^{\large 9})\ {\rm mod}\ 10^5.\,$$ OP is an analog in radix $$\,2\,$$ vs. $$10.\,$$ This is a prototypical example of the method of simpler multiples.

More generally congruences persist mod $$\rm\color{#c00}{factors}$$ of the modulus, i.e.

\begin{align} &\bbox[5px,border:1px solid red]{a\equiv \bar a\!\!\!\pmod{\!k\:\!\color{#c00}n}\ \Rightarrow\ a\equiv \bar a\!\!\!\pmod{\!\color{#c00}n}}\\[.4em] \text{by its defining divisibility persists: }&\ \ n\mid kn\mid a-\bar a\,\Rightarrow\, n\mid a-\bar a\ \ \text{by transitivity of 'divides'.} \end{align}

OP is a special case of this persistence, by taking $$\,\bar a = (a\bmod kn),\,$$ and recalling that

$$\,a\equiv \bar a\!\!\!\pmod{\! n}\ \iff \ a\bmod n = \bar a\bmod n$$

• I downvoted this because you referred me to your post as an answer to my question (after closing my question). Since it does not actually consider my question and the context in which I asked it, it is therefore unsatisfactory. – rocksNwaves Jan 17 '20 at 21:02
• @rocksNwaves Not true. My comment on your question explains precisely how it answers your question. If you don't understand that then the polite thing to do is to ask for elaboration, not to immediately downvote a correct answer. – Bill Dubuque Jan 17 '20 at 21:33