Вот задачка
С помощью непрерывных дробей найти все целые решения диофантова уравнения 28x – 11y = 7.
(Ответ: x = 14 + 11t, y = 35 + 28t, где t — произвольное целое число. )
Как к ней подступиться, и с чего начать
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Криптография] Диофантовое уравнение 1-го порядка |
| Автор: neosapient 1.1.2007, 15:50 |
| Всех с праздниками. Вот задачка С помощью непрерывных дробей найти все целые решения диофантова уравнения 28x – 11y = 7. (Ответ: x = 14 + 11t, y = 35 + 28t, где t — произвольное целое число. ) Как к ней подступиться, и с чего начать |
| Автор: Kuvaldis 1.1.2007, 19:27 | ||
neosapient,
Через непрерывные дроби не знаю, как, но нас на 1 курсе учили решать подобные вещи так (а вдруг и это тебе пригодится) 28x – 11y = 7 уравнение вида A * x + B * y = с Это линейное диофантовое уравнение. Значит, его общее решение можно представить как общее решение однородного + частное решение неоднородного (как и для любого ЛИНЕЙНОГО уравнения. будь это алгебра, Дифф. уравнение или еще чего) общее решение однородного уравнения, т.е. A * x + B * y = 0 это X = B * t Y = - A * t Для твоего случая: x = 11 * t y = 28 * t Теперь ищем частное решение неоднородного уравнения. Нетрудно заметить, что коэффициенты 28 и -11 - взаимно простые числа (можно доказать через алгоритм Евклида), т.е. их НОД = 1 Существует теоремка, что существуют числа M и N, что 28 * M - 11 * N = 1 (*) Они находятся через тот же алгорим Евклида (посмотри в Центре помощи, я похожую задачку объяснял приблизительно в июле, подробно) Находим данные числа M и N В примере у нас справа не 1, а 7. Тогда просто умножим уравнение (*) с уже найденными коэффициентами на 7, и будем нам счастье... как можешь заметить, в решении (Ответ: x = 14 + 11t, y = 35 + 28t, где t — произвольное целое число. ) как раз константная часть и умножена на 7  |
| Автор: neosapient 2.1.2007, 00:01 | ||
Имелось в виду http://forum.vingrad.ru/topic-115685/unread-1/hl/%25D0%2595%25D0%25B2%25D0%25BA%25D0%25BB%25D0%25B8%25D0%25B4%25D0%25B0/index.html Плохо понял, что делать после уравнения (*) Распиши пожалуйста по подробнее |
| Автор: Kuvaldis 2.1.2007, 00:29 |
| neosapient, сорри, слегка тебя запутал, это я в писал http://forum.vingrad.ru/index.php?showtopic=108780&hl=%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4 |
| Автор: neosapient 2.1.2007, 13:48 |
| Кажется понял НОД(28,11) = 28M - 11N = 1 28 = 11*2 + 6 (1) 11 = 6*1 + 5 (2) 6 = 5*1 + 1 (3) Из (3) НОД = 6 + 5*(-1) Из (2) 5 = 11 + 6*(-1) Тогда НОД = 6 + (11 + 6*(-1))*(-1)=11*(-1) + 6*(2) Из (1) 6 = 28 + 11*(-2) Тогда НОД = 11*(-1) + (28 + 11*(-2))*(2) = 28*(2) + 11*(-5) Получили (НОД=1) 28*(2) - 11*(5) = 1 Вспомним что ищем 28x – 11y = 7 Умножим на 7 28*(2*7) - 11*(5*7) = 7 Частное решение x=2*7=14, y=5*7=35 Остается объединить с общим решением... Кажется что-то такое было на первом курсе, эх... как все быстро забывается |
| Автор: Kuvaldis 2.1.2007, 14:34 | ||
neosapient,
Правильно решил. Молодец. Если нужно обоснование перехода к поиску решения в виде частное + общее и сам не понимаешь, то не стесняйся..... |
| Автор: neosapient 3.1.2007, 14:54 |
| Я конечно знаю, что лучший лектор тот, у которого каждый год новые лекции. Позавчера только пришел список вопросов на экзамене. Задолго до этого, я раздобыл список вопросов прошлого года и скан конспекта того же года. Ну вообщем хронология лекций мягко говоря перетасована, часть тем убрали, часть тем урезали (в основном докозательство теорем - сами должны найти  ), что то добавили.Так вот в списке вопросов есть билет "применение непрерывных дробей для решения диофантовых уравнений первой степени". Но нам этой темы небыло прочитано . Ладно нашел в скане за прошлый годВот что вышло: http://neosapient.narod.ru/univer/Kripto/kripto_8_2.JPG Либо прикрепил ниже За помошь + |