# Thread: Making sense of a proof that every integer is congruent modulo n to some element of S

1. ## Making sense of a proof that every integer is congruent modulo n to some element of S

I'm trying to make sense, well better sense, of a proof of the following that my instructor gave me, while I work out my own proof of the same if then statement.

The problem is;

Let $k \in \mathbb{Z}$ and $n \in \mathbb{N}$. Consider the set $S=\{k, k+1,...,k+n-1\}$

Prove that every integer is congruent modulo n to some element of S.

The given proof is;

He introduces the definition of cardinality for a set and notes that the cardinality of $S$ equals the cardinality of $\mathbb{Z}_n$

(1) Let $m\in\mathbb{Z}$

(2) Solve $m\equiv(k+j)\pmod n$

(3) Show that $(k+i)\equiv(k+j){\pmod n} \longleftrightarrow (i=j)$

(4) $(k+i)-(k+j)=i-j$

(5) $n|(i-j)$ and $n|(j-i)$

So the set S is equivalent to the set $H=\{0,1,2,...,n-1\}$ We have a Theorem that states, every integer is congruent modulo n to an element of H.

end proof.

So the part about the cardinality of S and H makes perfect sense. Since all S is is H with a k added to every element.

From 2 to 3 looks good to me. He just set $m=k+i$

Proving the bi-conditional in 3 is giving me a problem.
$(i=j) \rightarrow (k+i)\equiv(k+j){\pmod n}$ Is trivial.

The other direction is giving me some trouble.
$(k+i)\equiv(k+j){\pmod n} \rightarrow (i=j)$

Assume $(k+i)\equiv(k+j){\pmod n}$

$\frac{(k+i)-(k+j)}{n}=q$

$i-j=qn$ and $j-i=(-q)n$

I don't get how this shows that i and j are equal. Does it show that they are they additive inverses of each other?

2. ## Re: Making sense of a proof that every integer is congruent modulo n to some element

did he state that $i,j \in \mathbb{Z}_n$ ?

3. ## Re: Making sense of a proof that every integer is congruent modulo n to some element

Originally Posted by romsek
did he state that $i,j \in \mathbb{Z}_n$ ?
If he did one of us didn't write it down in my notes. If it makes the proof work though I would totally take it.