Операции над вычетами. Дискретная математика.

[ScarfaseV]

В Дискретной математике существует такое понятие как вычет.
Число можно представить в виде S=q*t+r, где
q=[s/t] - целая часть от деления.
r - остаток от деления.
Также про остаток говорят, что r- вычет s по модулю t.
Обозначение: RESt[s]=RSt[s]=Rt[s].
Так вот, есть такая теорема о вычете суммы чисел в кольце целых чисел:
RESt[x+y]=RESt[RESt[x]+RESt[y]].
Надо доказать эту теорему.
Доказывать нужно примерно вот так:
x+y=q*t+RESt[x+y] => RESt[x+y]=(x+y)-q*t
Так надо расписывать каждый вычет, а вот что делать дальше я не знаю, может кто поможет?

[Sonic86]

В паскале, кажется пишется, $r = S mod t$.
Вам еще полезно будет знать обозначение $a \equiv b (\mod n)$, обозначающее $a-b$ делится на $n$. Например $9 \equiv 5 (\mod 4)$. Если обозначить остаток $s$ от деления на $t$ как $rest(s,t)$ (указывать делитель важно!), то очевидно, что $rest(s,t) \equiv s (\mod t)$.
Условие $r = S mod t$ равносильно 2-м условиям $0 \leq r < t$ и $r \equiv S (\mod t)$.
Теперь с помощью этой равносильности перепишите условие $rest(x+y)=rest(rest(x)+rest(y))$ и докажите.

[ScarfaseV]

Sonic86 в сообщении #237858 писал(а):

В паскале, кажется пишется, $r = S mod t$.
Вам еще полезно будет знать обозначение $a \equiv b (\mod n)$, обозначающее $a-b$ делится на $n$. Например $9 \equiv 5 (\mod 4)$. Если обозначить остаток $s$ от деления на $t$ как $rest(s,t)$ (указывать делитель важно!), то очевидно, что $rest(s,t) \equiv s (\mod t)$.
Условие $r = S mod t$ равносильно 2-м условиям $0 \leq r < t$ и $r \equiv S (\mod t)$.
Теперь с помощью этой равносильности перепишите условие $rest(x+y)=rest(rest(x)+rest(y))$ и докажите.

$x+y\equiv RESt[x+y] (\mod t)$;
$(x+y) - RESt[x+y] mod t =0$;
$x\equiv RESt[x] (\mod t);
$(x) - RESt[x] mod t =0;
$y\equiv RESt[y] (\mod t);
$(y) - RESt[y] mod t =0;
$ RESt[x]+RESt[y] \equiv RESt[RESt[x]+RESt[y]] (\mod t);

Незнаю как
Также я непонял для чего здесь нужно 1 условие

[AKM]

Потому что $21\equiv 101\pmod{5}\equiv 1\pmod{5}\equiv 411\pmod{5}$. A остаток (rest) от деления всех этих чисел на 5 есть 1 (один), что и выделяется первым условием, $0\le r < 5$.

[ScarfaseV]

RESt[x+y]=RESt[RESt[x]+RESt[y]]
А вот просто нельзя ли так доказать:
1) x=q1*t+RESt[x] => RESt[x]=x-q1*t;
Аналогично, RESt[y]=y-q2*t;
2)Рассмотрим правую часть, т.е:
RESt[RESt[x]+RESt[y]]=RESt[x-q1*t+y-q2*t]=RESt[x+y-(q1+q2)*t], но так как
(q1+q2)*t mod t =0 , то имеем RESt[x+y] => RESt[x+y]=RESt[RESt[x]+RESt[y]].
Без всяких сравнений.

[Sonic86]

Да, можно так, без обозначений. Только последний переход чуть подробнее расписать.