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