Доказательство формулы остатка

[Skipper]

Теорема о сумме по модулю.
Задали задачу.. Доказать или опровергнуть следующую формулу. Докажем, что эта формула верна.

$(A + C) \mod M = ( ( A \mod M ) + ( C \mod M ) ) \mod M$

Доказательство.

Имеем, $ (A + C)$ это делимое, $M$ - делитель, и пусть будут от этого деления, $q$ - частное , $r$ - остаток . Т.е.

$(A + C) = M \cdot q + r $

Аналогично, от деления $A$ на $M$, пусть $q_1$ - частное , $r_1$ - остаток .
Аналогично, от деления $C$ на $M$, пусть $q_2$ - частное , $r_2$ - остаток .
Т.е.

$A = M \cdot q_1 + r_1 $

$C = M \cdot q_2 + r_2 $

Отсюда следует,

$(A + C) = M \cdot q_1 + r_1 + M \cdot q_2 + r_2 = M \cdot (q_1 + q_2) + (r_1 + r_2) $

Поскольку, $r_1$ и $r_2$ - остатки от деления на $M$ , то их сумма строго меньше $2 M $, значит частное от деления $(r_1 + r_2)$ на $M$ , равно $1$ или $0$.

Рассмотрим оба варианта.
1-й вариант - частное от деления $(r_1 + r_2)$ на $M$ , равно $0$ .

Т.е. $(r_1 + r_2)$ меньше чем $M$ . Тогда очевидно, получаем систему уравнений,

$q = q_1 + q_2 $
$r = r_1 + r_2 $

Рассмотрим доказываемое теоремой утверждение.

$(A + C) \mod M = ( ( A \mod M ) + ( C \mod M ) ) \mod M$

Левая часть равна,

$(A + C) \mod M = r = (r_1 + r_2) = ( ( A \mod M ) + ( C \mod M ) ) $

Таким образом, мы доказали исходное утверждение теоремы, без окончания "mod M " в конце. Но добавление этого окончания ничего не меняет, т.е. исходное утверждение тоже верно. В самом деле,

$(r_1 + r_2) = (r_1 + r_2) \mod M $

поскольку, как было сказано выше, делимое $(r_1 + r_2)$ меньше чем делитель $M$ . В таком случае остаток (а это $(r_1 + r_2) \mod M $ ), равен всегда делимому.

2-й вариант - частное от деления $(r_1 + r_2)$ на $M$ , равно $1$ .

Вернёмся к двум формулам выше ,

$(A + C) = M \cdot q + r $
$(A + C) = M \cdot (q_1 + q_2) + (r_1 + r_2) $

очевидно что в таком случае,

$(r_1 + r_2) = M + r $

так как, $ r$ - строго меньше $M$ по условию (это же остаток), а 2-й вариант подразумевает, что $(r_1 + r_2)$ строго меньше чем $2M$, но больше или равно $M$.
Получаем,

$(A + C) = M \cdot (q_1 + q_2) + M + r $
значит,
$(A + C) = M \cdot (q_1 + q_2 + 1) + r $
и
$q = (q_1 + q_2 + 1) $

Рассмотрим доказываемое теоремой утверждение.
Левая часть равна $r$, по условию, если мы докажем, что и правая часть равна $r$ , то тем самым окончательно докажем теорему, со всей строгостью. Итак, для доказательства теоремы, нужно доказать что,

$( ( A \mod M ) + ( C \mod M ) ) \mod M = r $
из этого следует,
$(r_1 + r_2) \mod M = r $
и по формулам, которые выше вывели,
$(M + r) \mod M = r $

притом, что $r$ меньше чем $M$ . Последнее очевидно, из определения деления с остатком. Тем самым, мы доказали что обе части равны ( и равны $r$ ).
Теорема доказана.

Вопрос, 1) есть ли в этом доказательстве изьян, неточности и т.п. или доказательство абсолютно верное?
Спасибо.

[kotenok gav]

$A+C\mod M$ очевидно равно $r_1+r_2\mod M$. Все.

[Skipper]

ну.. слово "очевидно", не все преподаватели принимают. Некоторым говорят, "очевидно", а описать подробно все случаи в доказательстве заставляют.

[kotenok gav]

Ок, вот вам подробнее, если так хотите: $(A+C)\mod M=((q_1+q_2)M+(r_1+r_2))\mod M=(r_1+r_2)\mod M$.

[iifat]

Skipper в сообщении #1471677 писал(а):

Рассмотрим оба варианта

Жуть какая. Достаточно, собственно, одного: два числа равны по модулю, если разность их кратна этому самому... Как его...

[Skipper]

Кому то очевидно и так, а кому то лучше "разжёванное" доказательство прочитать.

[nnosipov]

Skipper
А Вы школьник? Просто не представляю, какой смысл имеет эта задача не для школьника. С моей точки зрения (как преподавателя) задавать ее студенту --- это просто терять время. Студенту-математику она неинтересна в виду банальности, а студенту-прикладнику она (как задача на доказательство) просто не нужна.

[vorvalm]

Skipper в сообщении #1471677 писал(а):

Теорема о сумме по модулю.
Задали задачу.. Доказать или опровергнуть следующую формулу. Докажем, что эта формула верна.

$(A + C) \mod M = ( ( A \mod M ) + ( C \mod M ) ) \mod M$

Извините, но это же элементарное свойство сравнений.

[Skipper]

Цитата:

А Вы школьник? Просто не представляю, какой смысл имеет эта задача не для школьника.

Я не школьник. А задали на факультативе для школьников - доказать. И если короткое доказательство, тем более вероятно что школьники или не допоймут, или не смогут ответить на какие нибудь каверзные вопросы учителя.

Насчёт студента, согласен, студентам такие доказательства не нужны и их не задают.

Цитата:

Извините, но это же элементарное свойство сравнений.

А свойства тоже многие, сначала доказываются, а уже потом просто запоминаются. Так, все помнят теорему Пифагора, и принимают её как свойство, или то что для двух треугольников -
если сторона треугольника и два прилегающие к ней угла - равны - то и оба треугольника равны.

Мне это казалось очевидным, но почему то в школе пришлось это у доски доказывать.

[kotenok gav]

Вот все доказательство этого свойства:

kotenok gav в сообщении #1471683 писал(а):

$(A+C)\mod M=((q_1+q_2)M+(r_1+r_2))\mod M=(r_1+r_2)\mod M$.

[Skipper]

Цитата:

Вот все доказательство этого свойства

Ну тогда уже так (чтобы наиболее полное и со всей строгостью) -

Докажем, что эта формула верна.

$(A + C) \mod M = ( ( A \mod M ) + ( C \mod M ) ) \mod M$

Доказательство.

Имеем, $ (A + C)$ это делимое, $M$ - делитель, и пусть будут от этого деления, $q$ - частное , $r$ - остаток . Т.е.

$(A + C) = M \cdot q + r $

Аналогично, от деления $A$ на $M$, пусть $q_1$ - частное , $r_1$ - остаток .
Аналогично, от деления $C$ на $M$, пусть $q_2$ - частное , $r_2$ - остаток .
Т.е.

$A = M \cdot q_1 + r_1 $

$C = M \cdot q_2 + r_2 $

Отсюда следует,

$(A + C) = M \cdot (q_1 + q_2) + (r_1 + r_2) $

А тогда,

$(A + C) \mod M = ( M \cdot (q_1 + q_2) + (r_1 + r_2) ) \mod M = (r_1 + r_2) \mod M $

Последнее равенство справедливо потому что первое слагаемое кратно $M$, а значит не имеет остатка, вот и остаётся $(r_1 + r_2) \mod M $ . (предусматривая все вопросы, которые могут возникнуть)
Наконец, так как по условию выше, $ r_1 = (A \mod M)$ и $r_2 = (C \mod M)$ , получаем

$(A + C) \mod M = (r_1 + r_2) \mod M = ( ( A \mod M ) + ( C \mod M ) ) $ $ \mod M$

что и требовалось доказать.

[StaticZero]

Skipper в сообщении #1472033 писал(а):

чтобы наиболее полное и со всей строгостью)

Так у kotenok gav оно как раз наиболее полное и вполне строгое.

С другой стороны, вы правы тоже: затыки бывают, это правда. Очень простые теоремы теории чисел иногда могут троллить школьников, воспитанных в духе Ньютона--Лейбница.

(Оффтоп)

Попробуем удерживать всю простоту в рассуждениях до тех пор, пока она не создаст проблему. Вот есть два числа $A = q_1 M + r_1$ и $B = q_2 M + r_2$. Если мы их сложим, то получим $A + B = (q_1 + q_2) M + (r_1 + r_2)$. Операция "по модулю" отсекает слагаемое с множителем $M$, тогда

$$ A \oplus B = r_1 + r_2 $$

(здесь $\oplus = + \pmod M$, простите, математики).

Q: Это всё? А что будет, если каждые по отдельности $r_i$ меньше $M$, а их сумма больше? Пример: $A = 17$, $B = 27$, $M = 7$: $r_1 = 3$, $r_2 = 6$, $r_1 + r_2 = 9$, но $A \oplus B = 44 \pmod 7 = 2$. Теорема неверна?
A: Да вроде бы не должна, ведь взятие модуля это же линейная операция, почему бы теореме быть неверной? Может, мы что-то делаем не так?
Q: А что именно?
A: $17 + 27 = (2 \times 7 + 3) + (3 \times 7 + 6) = 5 \times 7 + 9$. Девять? В смысле девять??? Мы же хотели изгнать все семёрки в один множитель. Ну отщипнём ещё одну, будет тогда $6 \times 7 + 2$.
Q: А мы могли раньше семёрку отщипнуть?
A: Нет, не могли, потому что и 3 (сиречь $r_1$), и 6 (сиречь $r_2$) оба меньше семёрки. Смотря на каждое из них в отдельности, мы ничего не могли сделать, пока не узнали, что надо их сложить.
Q: Получается, саму сумму по модулю надо брать? Wait, oh shi~
A: Ага, поэтому кружочек вокруг плюсика сбрасывать нельзя:

$$ A \oplus B = r_1 \oplus r_2. $$

Я всё описал, что могло случиться в классе?

[Skipper]

Цитата:

что могло случиться в классе?

Я тоже про этот вариант (и возможные вопросы к доказательству) думал..

[Утундрий]

(Оффтоп)

StaticZero в сообщении #1472036 писал(а):

здесь $\oplus = + \pmod M$, простите, математики

Не-а, не простят. У них $\oplus$ - сложение по-Минковскому.