# Proof-verification: $\forall a \space \exists! r\in${0,…,n-1} with $a \equiv r\space (mod \space n)$

I am still in school but started studying on elementary-number-theory a bit. I hope someone can give suggestions on my try and also point out mistakes i have done.

I wanted to show the following:

Statement A: For every positive integer $a$ there is exactly one $r\in${0,...,n-1} with $a \equiv r\space (mod \space n)$

I tried to show this assuming $\neg A$.

Therefore we have atleast another r´ which fulfills the congruence $a \equiv r´\space mod \space n$

With $a \equiv b\space (mod \space n) \Longleftrightarrow n|(a-b)$ we get $n|(a-r)$ and $n|(a-r´)$

With the definition of divisibility we have $nq=a-r$ aswell as $np=a-r´$

Now we can see that:

$$nq+r=np+r´$$ $$n(q-p)=r´-r$$ And with $s=q-p$; $s \in \mathbb{Z}$ we get $$ns=r´-r$$ But since $r \wedge r´\in${o,...,n-1} we know that $(n-1)\geq |r´-r|\geq0$ which leads into a contradiction because $s$ needs to be $1> s\geq0$ which is not an integer. Altough if $s=0$ we also have $|r´-r|=0 \Longrightarrow p=q$ since $n(q-p)=r´-r$. And that shows that r is clearly defined.

What i am unsure about is the definition of $s$. Since it is defined as $q-p$ i hope that i can still say it is $\in \mathbb{N}$ because if $q\neq p$ and $q\geq p$ it should be.

Edit: As Hagen von Eitzen pointed out i missed out to show that a certain $r$ even exists

For that we have the definition of division with remainder which is

$a=qn+r$ ; $n>r\geq 0$

From there we have: $$a=qn+r$$ $$a-r=qn$$ $$n|(a-r)$$ which then turns to $a\equiv r$ (mod n) ;$n>r\geq 0$ which is the same as $r\in$ {0,...,n-1}

I am not sure if that is enough to show that there is atleast one $r$ existing for every $a$

• For one, you only have $s\in \Bbb Z$. Unless you assume (wlog.) that $r'\ge r$. - But most importantly you only show that there is at most one such $r$ when the task is to show that there is exactly one such $r$. – Hagen von Eitzen Nov 25 '15 at 16:06
• @HagenvonEitzen You are totally right here - really appreciate the help. But isnt my Statement on $\neg A$ wrong then - that there is atleast one other $r´$? – K. Hoffmann Nov 25 '15 at 16:13
• You did not prove $¬A$, you proved $¬B$, where B is "more than one such rs exist". So now you also have to prove C where C is "there's at least one such r" – peter.petrov Nov 25 '15 at 16:17