СПРОСИ ПРОФИ
👍
+2
👎 221

Задача из листка "Алгоритм Евклида"

Пусть kn-lm=1. Докажите, что тогда НОД(ka+lb,ma+nb)=НОД(a,b).
Частные случаи понимаю, общий доказать не могу. Заранее спасибо!
математика обучение     #1   06 ноя 2014 12:57   Увидели: 131 клиент, 3 специалиста   Ответить
👍
0
👎 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
👎 0
Если подумать, что утверждение
[m](ab,c) = \frac{(a,c)(b,c)}{((a,b),c)}[/m]
неверно. Значит надо как-то по-другому.
👍
0
👎 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
👎 0
Большое спасибо за ответ. Я только не поняла насчет того, что существует простое p, которое делит большой НОД и не делит малый. Это как-то просто следует из алгоритма Евклида или из свойств НОД?
  #5   06 ноя 2014 22:42   Ответить
👍
0
👎 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
👎 0
Простые множители, степени — это видимо основная теорема арифметики? Ей пока нельзя пользоваться. Только НОД(a плюс-минус b,b)=НОД(a,b) и алгоритм Евклида.
  #9   07 ноя 2014 07:09   Ответить
👍
0
👎 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
👎 0
А не подскажете еще, как доказать, что в случае применения алгоритма Евклида к двум двузначным числам потребуется не более девяти шагов (делений с остатком)? Я с теоремой Ламе разобралась, но по ней 10 получается. Надо как-то использовать, что второе число тоже двузначное, но я не могу придумать как.
  #6   06 ноя 2014 22:50   Ответить
👍
0
👎 0
Теорема Ламе утверждает, что число шагов в алгоритме Евклида для натуральных чисел a и b будет строго меньше, чем [m]5\cdot(\left \lfloor\log_{10}(\min\{a,b\}) \right \rfloor+1)[/m]. Т.к. там строго меньше, то для двух двухзначных получаем [m]\le 9[/m]
👍
0
👎 0
Я не понимаю этих обозначений, но на словах: число шагов не превышает пятикратного количества цифр в десятичной записи меньшего из двух чисел. Для двузначных получается не больше 10.
  #10   07 ноя 2014 07:14   Ответить
👍
0
👎 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
👎 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
десять делений с остатком.
  #13   07 ноя 2014 13:28   Ответить
👍
0
👎 0
Последнее деление 1) выполнено неверно: 2=2*1+0, это деление нацело, а не деление с остатком, 2) его делать не надо, т.к. 3=2*1+1, а на 1 делится любое целое число и если какой-то остаток от деления стал равным 1, то это сразу дает нам взаимную простоту исходных чисел, алгоритм останавливается, выдается ответ.
Итого, 9 делений с остатком.
👍
+1
👎 1
Ок. А есть пример двух двузначных чисел, для которых нужно 9 делений с остатком?
  #15   07 ноя 2014 14:09   Ответить
👍
0
👎 0
Не знаю, думаю, что такого примера нет. Надо аккуратно через числа Фибоначчи оценить (это я на Вас оставляю) или перебрать все пары двузначных чисел, благо это не проблема для компьютера.
👍
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
👎 0
К этой задаче есть указание. Используйте линейное представление НОД. Вы Юрий Анатольевич это и сделали.
👍
+1
👎 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
👎 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
Большое спасибо, очень познавательно!
  #21   16 ноя 2014 11:54   Ответить
👍
0
👎 0
помогите найти НСД(792,702) = 792m+702n
  #22   29 ноя 2016 22:19   Ответить

Задайте свой вопрос по математике
профессионалам

Сейчас онлайн 75 репетиторов по математике
Получите ответ профи быстро и бесплатно

Другие вопросы на эту тему:

👍
+1
👎 12

Коллеги, прошу помощи, забуксовал... Классическая геометрия.   2 ответа

Помогите, пожалуйста!
Геометрическое чутьё — как музыкальный слух. Ну не Аполлоний Пергский я...
Две окружности касаются внутренним образом в точке K, при этом меньшая проходит через центр большей. Хорда MN большей окружности касается меньшей в точке C. Хорды KM и KN пересекают меньшую окружность в точках A и B соответственно, а отрезки KC и AB пересекаются в точке L. Доказать, что CN:CM = LB:LA.
👍
0
👎 07

Система   7 ответов

Найти х из системы
k=(sqrt(28,5^2-9x^2/4))/4
a+ka=3,5
b+kb=0,5x
a^2=b^2+625
  23 ноя 2016 13:49  
👍
0
👎 010

Уравнение   10 ответов

Как решать уравнение, не представляю.

[math]ctg\frac{\sqrt{2}}{2}-\cos 2x=0[/ma
  19 май 2016 17:40  
👍
+2
👎 26

Один король хотел сместить своего премьер-министра   6 ответов

Один король хотел сместить своего премьер-министра, но при этом не хотел его слишком обидеть. Он позвал премьер-министра к себе, положил при нем два листка бумаги в портфель и сказал: "На одном листке я написал "Уходите", а на втором — "Останьтесь". Листок, который вы вытащите, решит вашу судьбу". Премьер-министр догадался, что на обоих листках было написано "Уходите". Как же, однако, умудрился он при этих условиях сохранить свое место?
👍
+3
👎 32

Геометрии 7 класс!   2 ответа

Пожалуйтса подробный решение!
Задача 1
В треугольнике LKM , Р лежит на стороне LM, причем KP=PM, <M=40 градус.Найти внешний угол треугольника при вершине K, если КР-биссектриса <LKM
  31 мар 2013 19:28  
👍
0
👎 08

Планиметрия С4   8 ответов

Задача
На сторонах треугольника АВ, ВС и АС треугольника АВС взяты точки K, L, M. Причем AK:KB=2:3; BL:LC=1:2; CM:MA=3:1.
В каком отношении отрезок KL делит отрезок BM?

Пытаюсь составить векторные уравнения, но не получается.
  12 сен 2012 10:00  
ASK.PROFI.RU © 2020-2024