2

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!

Michael Hardy
  • 1
428
  • 565

1 Answers1

0

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}