Question

Let $n$ be a positive integer. Prove that a andc leave the same remainder when divided by n if and only if $a-c=nk$ for some integerk.

Short answer

It is proved that a and c leave the same remainder when divided by n if and only if $a-c=nk$ for some integer k.

Step-by-step solution

The Division Algorithm

Theorem 1.1 states that consider $a,b$ as an integer with $b>0$. Then $q$ and $r$ areunique integersin which role="math" localid="1646107310480" $a=bq+r$and $0\le r\le b$.

Theorem 1.1 permits for a negative dividend $a$. However, the remainder $r$ should not only be less than the divisor $b$, and it also should be nonnegative.

Show that a and c  leave the same remainder when divided by n if and only if a-c=nk for some integer k

Assume that $a=nk+r$ with $0\le r\le n$ and $0=n{q}^{\text{'}}+r^{\text{'}}$with $0<r<n^{\text{'}}$.

When $r=r^{\text{'}}$ then role="math" localid="1646107800141" $a-0=n\left(q-q^{\text{'}}\right)$ and $k=q-q^{\text{'}}$ would be an integer.

In that case $a-0=nk$, substitute for determining $\left(r-r^{\text{'}}\right)=n\left(k-q+q^{\text{'}}\right)$.

Assume $r\ge r^{\text{'}}$(as in the other case). The inequalities indicate that $0\le \left(r-r^{\text{'}}\right)<n$ , and it concludes that $0\le \left(k-q+q^{\text{'}}\right)<1$ and implies that $k-q+q^{\text{'}}$. Thus, $r-r^{\text{'}}$ and therefore, $r=r^{\text{'}}$ is obtained.

Hence, it is proved that a and c leave the same remainder when divided by n if and only if $a-c=nk$ for some integer k.