Делимость и ее свойство.

[KiberMath]

Свойство: если произведение $a*b$ делиться на $c$ и при этом
$b$ и $c$ взаимно простые, то $a$ делиться на $c$

Задача доказать это от противного.

{
Предположил, что $a$ не делиться на $c$, тогда должно быть противоречие с условием теоремы.

Дальше рассуждаю так

так как $a$ не делиться на $c$ то можно представить $a$ в виде:

$а=ck_1 + r_1$

так как $b$ и $c$ взаимно простые числа то

$b=ck_2 + r_2$

тогда

$ab = (ck_1+r_1)(ck_2+r_2) = cck_1k_2 + ck_1r_2 + ck_2r_1 + r_1r_2$
}

Вот. Тут получаеться, что все слагаемые последнего выражения деляться на $c$ кроме $r_1r_2$ ... ну так обязательно должно быть, если теорема верна, но как доказать, что $r_1r_2$ не делиться на $c$? из чего это вытекает? известно ведь только что $r_1<c$ и $r_2<c$. Что мешает этим числам в каком -нибудь случае принять такое значение, чтобы их произведение все-таки делилось на $c$ ??

[Lion]

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

[KiberMath]

Lion
К сожалению я не знаю что это такое
Пойду об этом что-нибудь почитаю и вернусь ))

Добавлено спустя 45 минут 1 секунду:

Почитал... но с какой стороны начать идей нет. Подскажите пожалуйста

[xolms]

Используйте что (c,r_2)=1

[KiberMath]

xolms
Я не знаю, что означает (c,r_2) = 1

[Brukvalub]

KiberMath писал(а):

xolms
Я не знаю, что означает (c,r_2) = 1

это означает, что числа в скобках - взаимно-простые, поэтому Вы можете продолжить своё рассуждение, причём произведение следующих остатков будет меньше произведения предыдущих остатков-в этом и состоит метод бесконечного спуска.

[Руст]

KiberMath писал(а):

Свойство: если произведение a*b делиться на с и при этом
b и c взаимно простые, то a делиться на с

Это не аерно. Может не делиться ни а, ни b. Есть свойство для простых c, при котором или а или b делиться на с.
Пример c=6, a=4,b=9.
Это я невнимательно читал условие (как a и b взаимно простые, это встречается в доказательстве единственности разложения).

[KiberMath]

Вообще я не знал теоремы исходя из которой (с,r_2) = 1... Пытался сам докапаться с чего бы это.
Заметил что взаимно простыми числами являются те, кроторые отличаются на единицу. Взял и решил рассмотреть два таких числа q и w, причем q=w+1. Тогда остаток от деления q/w будет равен единице. Дальше заметил, что из q можно получить еще числа взаимно простые с w, умножая q на те простые чилса, которых нет в разложение числа w (eсли умножать на простые числа, которые уже есть в разложении w, то они не будут взаимно простыми). Но тогда остаток будет умножаться на эти же чилса, т.е. остаток в любом случае взаимно простой с числом w.

Вот так я получаю, что каким бы не было число r_1произведение r_1r_2 не разделится на с

Но интересно, что это ведь в случае, когда b<c, но если b>c теорема тоже должна остаться верна, вот только получаеться, что r_2<0... Как-то странно видеть остаток от деления меньше нуля или этого не стоит смущаться.

А как тут применить метод бесконечного спуска все-равно не понимаю )) Подаскжите пожалуйста

[xolms]

Рассмотрите любой делитель c. Он не делит r_2 значит делит r_1, разделите на него и т.д.Получите, что r_1 кратно c ноr_1<c значит r_1=0 иc кратно a (это можно было сделать сразу, без выделения остатков)

[KiberMath]

xolms
Я вас плохо понял. Расскажите пожалуйста поподробнее, почему r_1 оказался кратен с.

[Dan_Te]

Бесконечный спуск - это, конечно, красиво, но на начальном уровне вряд ли целесообразно им пользоваться. Есть более простые (ну или более грубые) средства.

Например, Основная теорема арифметики. Она утверждает, что любое число можно разложить на простые множители, представив в виде
$n=p_1^{k_1}\cdot\ldots\cdot p_m^{k_m}$, где $p_1\ldots p_m$ - различные простые числа. Причем разложение будет единственно с точностью до перестановок множителей $p_i^{k_i}$.

Это очень известная теорема, она представляется очевидной. Да и сам исходный факт тоже очевиден, поэтому чего там мудрить, раскладываем a,b,c на множители, смотрим, что у b и c нет общих простых чисел в разложении, поэтому все множители числа c сидят в числе a.

[bot]

Dan_Te писал(а):

Это очень известная теорема, она представляется очевидной.

А без использования сабжевого свойства Вы её докажете?

Добавлено спустя 4 минуты 33 секунды:

Кстати, при доказательстве ОТА не обойтись без сложения, хотя для определения делимости требуется лишь умножение.

Пример: 100=4*25=10*10 - два различные разложения на простые сомножители в полугруппе по умножению всех чисел вида 3k+1. Другой пример сидит в наших розетках - это число 220.

[Dan_Te]

А без этого не доказывается?
Вообще, мне приходила в голову мысль, что это может быть только подготовкой а Основной теореме =))
Но если уж строго, то надо задать вопрос, а что автору темы вообще известно о делимости на данный момент времени (какими фактами можно пользоваться)?

[RIP]

ОТА легко доказать и без этого свойства. Например, по индукции.

[Lion]

А можно использовать теорему о наибольшем общем делителе: для любых целых $a$ и $b$ найдутся такие целые $x$ и $y$, что $ax+by=(a,b)$.