$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

Question

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.

Answer 1

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.

Answer 2

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$

Answer 3

$\begin{eqnarray}{\bf Hint}\qquad &&\ (a\ {\rm mod}\ kn)\ {\rm mod}\ n\\ &=&\, (a\ -\ q\:k\:\!\color{#c00}n)\ {\rm mod}\ \color{#c00}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$$