Antallet af forskellige rester ved heltalsdivision

Lad $d, D, r\in \mathbb{N}, n\in\mathbb{N}\cup\{0\}\leq D$. Antag desuden, at $D=d\cdot n+r$. Vi siger, at $r$ er resten ved heltaldivision, eller $r$ er “$D$ modulo $d$”, hvilket skrives $r=D\mod{d}$.

Postulat

Antallet af forskellige rester ved heltalsvidision, dvs. antallet af elementer i mængden $R\ni r$, er $d$.

Bevis

For enthvert $d$ er der præcis $d$ forskellige situationer med heltalsrest:
$\begin{array}{cclc}\text{Divisor}, D&=&\text{Divisor } d\cdot n+r&\text{Modulo}, r\\
D&=&d\cdot n & 0\\
&=&d\cdot n+1& 1\\
&=&d\cdot n+2& 2\\
&=&\vdots&\vdots\\
&=&d\cdot i& i\\
&=&\vdots&\vdots\\
&=&d\cdot n+(d-1)& d-1\\
&=&d\cdot n+d = d\cdot (n+1) & 0\\
\end{array}$
Det ses, at mønsteret fra $D=d\cdot n+1$ gentages for $D=d\cdot n+(d+1)=d\cdot (n+1)+1$

About Morten Engelsmann

Underviser i matematik, kommunikation, it og samarbejde. Uddannet indenfor skovbrug, statistik og matematik. Arbejdserfaring indenfor miljø, industri, offentlig administration og it/tele.
This entry was posted in Logik, Matematik and tagged , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *