Sunday, 18 June 2017

Unfamiliar Property of Modular Arithmetic



I saw this property listed in Princeton Review's Math GRE book:




"For any positive integer $c$, the statement $a\equiv b\mod n$ is equivalent to the congruences $a\equiv b,b+n,b+2n,\ldots,b+(c-1)n\mod cn$."



Now, my problem is that I have no idea what it's telling me. An example would suffice, because my own attempts to generate examples seem to end in failure. I tried starting with $10\equiv 2 \bmod 8$ and $c=4$, but $10\equiv 26\mod 32$ is false ($26 = 2 + 3\cdot8$ and $32 = 4\cdot8$).



Any help is appreciated!


Answer



Example: $a = 10, b = 2, n = 8, c = 4$.



\begin{align}

10 &\equiv 2 \pmod{8}.
\end{align}



The equivalence guarantees



\begin{align}
a &\equiv b + dn \pmod{32}
\end{align}



for some $0 \leq d < 4$. Indeed,




\begin{align}
10 &\equiv 2 + 1 \cdot 8 \\
&\equiv 10\pmod{32}.
\end{align}



Justification: Here is a proof for the first direction. Let $c$ be a positive integer. Suppose



\begin{align}
a \equiv b \pmod{n}.

\end{align}



Then $a = b + d n$ for some integer $d$. If we reduce modulo $cn$ we have



\begin{align}
a \equiv b + dn \pmod{cn}.
\end{align}



for some integer $d$. The set $\{0,n,2n,\dots,(c-1)n\}$ are all possible reductions of $dn$ modulo $cn$. Hence




\begin{align}
a \equiv b + dn \pmod{cn}.
\end{align}



for some integer $0 \leq d < c$. Moreover only one integer $d$ in this range will satisfy this congruence, since $jn \not\equiv kn \pmod{cn}$ for integers $j,k$ such that $0 \leq j < k < c$.



The reverse direction is much easier, just reduce modulo $n$. That is, suppose



\begin{align}
a \equiv b + dn \pmod{cn}.

\end{align}



for some integer $0 \leq d < c$. Then $a = b + dn + kcn$ for some integer $k$. Thus,



\begin{align}
a &\equiv b + dn + kcn \\
&\equiv b \pmod{n}.
\end{align}


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...