Gaussa teoria liczb - dowody twierdzeń

1.
$a - a = 0 = 0\cdot n \rightarrow a \equiv a \mbox{\rm (mod } n)$
2.
$ a \equiv b \mbox{\rm (mod } n) \rightarrow a-b = kn \rightarrow b-a = -kn \rightarrow
b \equiv a \mbox{\rm (mod } n) $
3.
$ \{ a \equiv b \mbox{\rm (mod } n) \mbox{\rm i } b \equiv c \mbox{\rm (mod } n)\}
\rightarrow \{a-b = hn \mbox{\rm oraz } c - d = gn\}$ a więc $a - c = (h+g) n \rightarrow
a \equiv c \mbox{\rm (mod } n)$;
4.
$ \{ a \equiv b \mbox{\rm (mod } n) \mbox{\rm i } c \equiv d \mbox{\rm (mod } n)\}
\rightarrow \{a-b = hn \mbox{\rm oraz } c - d = gn\}$
$ (a+c) - (b+d) = (a-b) + (c-d) = (h+g) n
\rightarrow
a + c \equiv b+ d \mbox{\rm (mod } n) $
dla $
a \cdot c \equiv b\cdot d \mbox{\rm (mod } n) $ dowód analogiczny.
5.
$ a \equiv b \mbox{\rm (mod } n) \rightarrow$
$a + c \equiv b+ c \mbox{\rm (mod } n) \mbox{\rm oraz }
a \cdot c \equiv b\cdot c \mbox{\rm (mod } n)$;
dowód jak (4) z uwzględnieniem (1) - $ c \equiv c \mbox{\rm (mod } n)$
6.
$ a \equiv b \mbox{\rm (mod } n) \rightarrow a^{k+1} \equiv b^{k+1}
\mbox{\rm (mod } n) $
Dowód indukcyjny. Teza spełniona jest dla k=1. Zakładamy jej prawdziwość dla pewnego k. Mamy więc:

\begin{eqnarray*}a &\equiv& b \mbox{\rm (mod } n)\\ a^k &\equiv& b^k \mbox{\rm (mod } n)
\end{eqnarray*}


Mnożymy dwie kongruencje stronami i wykorzystujemy własnośc (4).

\begin{eqnarray*}aa^k &\equiv& bb^k \mbox{\rm (mod } n)\\ a^{k+1} &\equiv& b^{k+1} \mbox{\rm (mod } n)
\end{eqnarray*}


co kończy dowód indukcyjny.
Dowód twierdzenia o takiej samej reszcie (r): $a\equiv b \mbox{\rm (mod } n) \rightarrow a = kb + n = \ldots $
przy dzieleniu b przez n zostaje reszta r; tak więc b = qn +r
$ \ldots = (qn + r) + kn = (q+k)n r \rightarrow$ - przy dzieleniu a przez n zostanie też reszta r. W drugą stronę - reszty takie same: a = q1n +r i b = q2 n + r. odejmując stronami $a-b = (q_1 - q_2) n \rightarrow a \equiv b \mbox{\rm (mod } n).$ A nie mówiłem leniuszku, że to łatwiutkie dowody?

Andrzej Lenda
1999-06-15