👍 +2 👎 |
Задача из листка "Алгоритм Евклида"Пусть kn-lm=1. Докажите, что тогда НОД(ka+lb,ma+nb)=НОД(a,b).
Частные случаи понимаю, общий доказать не могу. Заранее спасибо!
математика обучение
Алина Дроздова
|
👍 0 👎 |
Я думаю, что для любых одновременно ненулевых чисел [m]a,b,c \in \mathbb{Z}[/m] справедливо соотношение
[m](ab,c) = \frac{(a,c)(b,c)}{((a,b),c)},[/m] Где [m](a,b)[/m] --- это НОД чисел а и b. Проверьте это строго (я его написал по интуиции, проверять мне его неохота, но оно похоже на правильное.) Используя это соотношение (если оно верно!) и доказав предварительно, что [m](ka+lb,m,ma+nb) = (a,b,m)[/m] несложно доказать желаемое утверждение. |
👍 0 👎 |
Если подумать, что утверждение
[m](ab,c) = \frac{(a,c)(b,c)}{((a,b),c)}[/m] неверно. Значит надо как-то по-другому. |
👍 0 👎 |
.
Пусть это не так, тогда существует такое простое число p, что [m]p|(ka+lb,ma+nb)[/m] (тогда [m]p| ka+lb[/m] и [m]p|ma+nb[/m]) и [m]p \not|(a,b)[/m]. Возможны два случая. 1) [m]p \not| a[/m] и [m]p \not| b[/m], тогда, т.к. [m]kn-lm=1[/m], то [m]lm = kn-1[/m] и [m]m(ka+lb) = mka+lmb = mka+(nk-1)b = mka+nkb-b = k(am+nb)-b.[/m] Т.к. [m]p| ka+lb[/m], то [m]p| m(ka+lb)[/m], значит [m]p| k(am+nb)-b[/m], но [m]p|ma+nb[/m], значит [m]p|b[/m] --- противоречие. 2) случай когда p делит a или p делит b разбирается еще проще. |
👍 0 👎 |
Большое спасибо за ответ. Я только не поняла насчет того, что существует простое p, которое делит большой НОД и не делит малый. Это как-то просто следует из алгоритма Евклида или из свойств НОД?
|
👍 0 👎 |
> не поняла насчет того, что существует простое p
Тут я немного погорячился, существует степень некоторого простого числа [m]p^s[/m], такая, что она делит [m](ka+lb,ma+nb)[/m], но не делит [m](a,b)[/m]; это не влияет на рассуждения. Действительно: Если [m](a,b)| (ka+lb,ma+nb)[/m], значит, существует такое число [m]q\in\mathbb{N}[/m], что [m](ka+lb,ma+nb) = q\cdot (a,b)[/m] если q=1, то доказывать нечего; иначе q раскладывается на простые сомножители, далее надо взять один из этих сомножителей в достаточно большой степени. Вообще, если подумать, то можно сразу брать это самое q, т.к. я, кажется, нигде не использовал простоту числа p. Второй пункт надо аккуратно записать. Пусть [m]q|b[/m] и [m]q \not| a[/m], тогда, т.к. [m]q| ka+lb[/m] и[m]q|ma+nb[/m], то [m]q| ka[/m] и [m]q|ma[/m] соответственно, но [m]a = a\cdot 1 = akn-lma[/m], значит [m]q|a[/m] --- противоречит с [m]q \not|(a,b)[/m]. |
👍 0 👎 |
Простые множители, степени — это видимо основная теорема арифметики? Ей пока нельзя пользоваться. Только НОД(a плюс-минус b,b)=НОД(a,b) и алгоритм Евклида.
|
👍 0 👎 |
> Простые множители, степени — это видимо основная теорема арифметики?
Она самая. > Ей пока нельзя пользоваться. Только НОД(a плюс-минус b,b)=НОД(a,b) и алгоритм Евклида. О!, ну не проблема. Тот факт, что [m](ka+lb,ma+nb)=q\cdot(a,b)[/m] следует из возможности деления с остатком в кольце [m]\mathbb{Z}[/m], т.е. эта возможность у Вас есть (иначе нет никакого алгоритма Евклида). Возьмите это самое q, тогда, если [m]q\ne 1[/m], то для него будут справедливы все мои рассуждения, которые я приводил для p (по факту там простота нигде не использовалась). Содержание следующего абзаца не относится к данной задаче. Отметим, что если в кольце есть деление с остатком, то оно называется евклидовом кольцом, а если в кольце справедлив аналог основной теоремы алгебры, то оно называется факториальным. Легко доказать, что любое евклидово кольцо является факториальным и можно привести пример (не простой!) факториального кольца, не являющегося евклидовым. |
👍 0 👎 |
А не подскажете еще, как доказать, что в случае применения алгоритма Евклида к двум двузначным числам потребуется не более девяти шагов (делений с остатком)? Я с теоремой Ламе разобралась, но по ней 10 получается. Надо как-то использовать, что второе число тоже двузначное, но я не могу придумать как.
|
👍 0 👎 |
Теорема Ламе утверждает, что число шагов в алгоритме Евклида для натуральных чисел a и b будет строго меньше, чем [m]5\cdot(\left \lfloor\log_{10}(\min\{a,b\}) \right \rfloor+1)[/m]. Т.к. там строго меньше, то для двух двухзначных получаем [m]\le 9[/m]
|
👍 0 👎 |
Я не понимаю этих обозначений, но на словах: число шагов не превышает пятикратного количества цифр в десятичной записи меньшего из двух чисел. Для двузначных получается не больше 10.
|
👍 0 👎 |
Скобки [m]\left \lfloor x \right \rfloor[/m] обозначают функцию пола (см.: http://en.wikipedia.org/wiki/Floor_and_ceiling_functions), а min{a,b} --- это минимум двух чисел; остальные обозначения должны быть понятны.
Так вот, теорема Ламе утверждает, что количество делений в алгоритме Евклида СТРОГО меньше чем [m]5\cdot(\left \lfloor\log_{10}(\min\{a,b\}) \right \rfloor+1)[/m] Так, если у вас a и b ---двухзначные, то [m]\lfloor\log_{10}(\min\{a,b\})\rfloor +1 \le \lfloor\log_{10}(99)\rfloor+1 = \lfloor 1,99564\rfloor+1 = 1+1 = 2[/m], значит число делений для таких чисел будет, по теореме Ламе, [m]<5\cdot2 = 10[/m]. Если <10, то это значит, что [m]\le 9[/m]. Отметим, что в теореме Ламе константа 5 может быть улучшена до [m]\frac{1}{\log_{10}(\frac{1+\sqrt{5}}{2})}\sim 4.7849719[/m]. |
👍 0 👎 |
Что-то не так у вас, вы не используете, что оба числа двузначные, и в вашем неравенстве ничего не изменится, если одно число трехзначное, а второе двузначное. По вашему неравенству и в этом случае число делений не больше 9, а между тем для a=144, b=89 получается
144=89*1+55 89=55*1+34 55=34*1+21 34=21*1+13 21=13*1+8 13=8*1+5 8=5*1+3 5=3*1+2 3=2*1+1 2=1*1+1 десять делений с остатком. |
👍 0 👎 |
Последнее деление 1) выполнено неверно: 2=2*1+0, это деление нацело, а не деление с остатком, 2) его делать не надо, т.к. 3=2*1+1, а на 1 делится любое целое число и если какой-то остаток от деления стал равным 1, то это сразу дает нам взаимную простоту исходных чисел, алгоритм останавливается, выдается ответ.
Итого, 9 делений с остатком. |
👍 +1 👎 |
Ок. А есть пример двух двузначных чисел, для которых нужно 9 делений с остатком?
|
👍 0 👎 |
Не знаю, думаю, что такого примера нет. Надо аккуратно через числа Фибоначчи оценить (это я на Вас оставляю) или перебрать все пары двузначных чисел, благо это не проблема для компьютера.
|
👍 0 👎 |
Приведу своё решение задачи из старт-поста.
Известно, что kn-lm=1. Требуется доказать, что НОД(ka+lb,ma+nb)=НОД(a,b). Перейдём от чисел a и b к числам A=a/НОД(a,b) и B=b/НОД(a,b). Легко видеть, что числа A и B — взаимно простые. А это означает, что существуют такие целые числа X и Y, что XA-YB=1. И остаётся доказать, что НОД(kA+lB,mA+nB)=1, или, что существуют такие целые числа x и y, что x(kA+lB)-y(mA+nB)=1. Положим x=Xn-Ym, y=Xl-Yk. Проверяем: (Xn-Ym)(kA+lB)-(Xl-Yk)(mA+nB) = (XnkA + XnlB -YmkA -YmlB) — (XlmA + XlnB -YkmA — YknB) = (XnkA -YmlB) — (XlmA — YknB) = (XnkA -XlmA) — (YmlB — YknB) = XA(nk-lm) — YB(ml — kn) = XA — YB = 1. Всё просто. Но если честно, то я сам до конца не осознал, что здесь произошло. Выражения, равные 1, очень похожи на определители матриц. Что здесь могли бы означать матрицы? Может ли результат как-то обобщаться на линейные комбинации не A и B, а большего количества чисел? А что, если рассматривать НОД не двух, а большего количества чисел? Спасибо за интересную задачу! |
👍 0 👎 |
К этой задаче есть указание. Используйте линейное представление НОД. Вы Юрий Анатольевич это и сделали.
|
👍 +1 👎 |
Геометрически задача решается устно.
Паре чисел (A,B) соответствует точка на координатной плоскости и радиус-вектор, соединяющий начало координат с этой точкой. Выражение XA-YB — это площадь параллелограмма, построенного на векторах (A,B) и (Y,X). Поэтому условие НОД(A,B)=1 равносильно существованию такого целочисленного вектора (Y,X), что площадь параллелограмма, построенного на векторах (A,B) и (Y,X), равна 1. Легко заметить, что вектор (kA+lB,mA+nB) получается из вектора (A,B) домножением слева на матрицу M=((k,l),(m,n)) (матрицу я здесь записал по строкам). Выражение kn-lm — это определитель этой матрицы. Для доказательства того, что НОД(kA+lB,mA+nB)=1, нужно подобрать такой вектор (u,v), чтобы площадь параллелограмма, построенного на векторах (kA+lB,mA+nB) и (u,v), была равна 1. Естественно в качестве (u,v) взять вектор, получающийся из вектора (Y,X) домножением слева на матрицу M, то есть (u,v) = (kY+lX,mY+nX). Тогда при линейном преобразовании, которое задаётся матрицей M, параллелограмм, построенный на векторах (A,B) и (Y,X) перейдёт в параллелограмм, построенный на векторах (kA+lB,mA+nB) и (u,v). Проверять длинными вычислениями, что площадь второго параллелограмма тоже равна единице, не нужно, так как по законам линейной алгебры при линейном преобразовании площади всех фигур увеличиваются во столько раз, чему равен определитель матрицы линейного преобразования. А в условии задачи сказано, что kn-lm=1. Получился длинный пост, длиннее, чем #17, — но всё это простые вещи, которые можно увидеть и осознать в уме. В #17 у меня получался параллелограмм не на векторах (kA+lB,mA+nB) и (u,v) = (kY+lX,mY+nX), а на векторах (kA+lB,mA+nB) и (y,x) = (Xl-Yk,Xn-Ym). Это говорит о том, что искомый вектор не единствен. |
👍 +2 👎 |
...Искомый вектор не единствен.
Если для вектора (u,v)=(kY+lX,mY+nX) верно, что площадь параллелограмма, построенного на нём и на векторе (kA+lB,mA+nB), равна 1, то этот же факт будет верен не только для вектора (u,v), но и для всех векторов (и только для них), которые получаются из вектора (u,v) прибавлением вектора (kA+lB,mA+nB), умноженного на любое число. (Для наших целей умножать нужно на целое число.) Я проверил это условие для вектора (y,x) = (Xl-Yk,Xn-Ym) и с ужасом обнаружил, что оно не выполняется. Оказывается, что вкралась ошибка в #17. Вместо "XA(nk-lm)-YB(ml-kn) = XA-YB = 1" должно быть XA(nk-lm)-YB(ml-kn) = XA + YB. Единицу не получаем. Ошибка не принципиальна, так как легко исправляется изменением знака перед Y, и тогда вместо вектора (y,x) получается вектор (u,v). Приношу свои извинения читателям форума. |
👍 0 👎 |
Большое спасибо, очень познавательно!
|
👍 0 👎 |
помогите найти НСД(792,702) = 792m+702n
|
👍 +1 👎 |
Коллеги, прошу помощи, забуксовал... Классическая геометрия.
|
👍 0 👎 |
Система
|
👍 0 👎 |
Уравнение
|
👍 +2 👎 |
Один король хотел сместить своего премьер-министра
|
👍 +3 👎 |
Геометрии 7 класс!
|
👍 0 👎 |
Планиметрия С4
|