# 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 $\displaystyle k \in \mathbb{Z}$ and $\displaystyle n \in \mathbb{N}$. Consider the set $\displaystyle 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 $\displaystyle S$ equals the cardinality of $\displaystyle \mathbb{Z}_n$

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

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

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

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

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

So the set S is equivalent to the set $\displaystyle 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 $\displaystyle m=k+i$

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

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

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

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

$\displaystyle i-j=qn$ and $\displaystyle 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.