 |
|
Модераторы: Poseidon |
 
|
|
[Криптография] Диофантовое уравнение 1-го порядка, решение через цепные дроби 
| neosapient |
|
|||
 Опытный  Профиль Группа: Участник Сообщений: 672 Регистрация: 16.8.2006 Репутация: нет Всего: 4 |
Всех с праздниками.
 Вот задачка С помощью непрерывных дробей найти все целые решения диофантова уравнения 28x – 11y = 7.  (Ответ: x = 14 + 11t, y = 35 + 28t, где t — произвольное целое число. ) Как к ней подступиться, и с чего начать  Это сообщение отредактировал(а) neosapient - 1.1.2007, 15:53 |
|||
|
||||
Загрузка ...
| Kuvaldis |
|
|||
 механик-вредитель Профиль Группа: Участник Клуба Сообщений: 1189 Регистрация: 16.6.2006 Где: Минск Репутация: 32 Всего: 61 |
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 |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 672 Регистрация: 16.8.2006 Репутация: нет Всего: 4 |
Имелось в виду Задача Евклида нахождение НОД, наибольшего общего делителя Плохо понял, что делать после уравнения (*) Распиши пожалуйста по подробнее Это сообщение отредактировал(а) neosapient - 2.1.2007, 00:03 |
|||
|
||||
| Kuvaldis |
|
|||
|
механик-вредитель Профиль Группа: Участник Клуба Сообщений: 1189 Регистрация: 16.6.2006 Где: Минск Репутация: 32 Всего: 61 |
neosapient,
сорри, слегка тебя запутал, это я в писал алгоритмах Это сообщение отредактировал(а) Kuvaldis - 2.1.2007, 00:30 -------------------- Помни - когда ты спишь, враг не дремлет Спи чаще и дольше, изматывай врага бессоницей |
|||
|
||||
| neosapient |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 672 Регистрация: 16.8.2006 Репутация: нет Всего: 4 |
Кажется понял
НОД(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 |
|
|||
|
механик-вредитель Профиль Группа: Участник Клуба Сообщений: 1189 Регистрация: 16.6.2006 Где: Минск Репутация: 32 Всего: 61 |
neosapient,
Правильно решил. Молодец. Если нужно обоснование перехода к поиску решения в виде частное + общее и сам не понимаешь, то не стесняйся..... -------------------- Помни - когда ты спишь, враг не дремлет Спи чаще и дольше, изматывай врага бессоницей |
|||
|
||||
| neosapient |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 672 Регистрация: 16.8.2006 Репутация: нет Всего: 4 |
Я конечно знаю, что лучший лектор тот, у которого каждый год новые лекции.
Позавчера только пришел список вопросов на экзамене. Задолго до этого, я раздобыл список вопросов прошлого года и скан конспекта того же года. Ну вообщем хронология лекций мягко говоря перетасована, часть тем убрали, часть тем урезали (в основном докозательство теорем - сами должны найти  ), что то добавили.Так вот в списке вопросов есть билет "применение непрерывных дробей для решения диофантовых уравнений первой степени". Но нам этой темы небыло прочитано . Ладно нашел в скане за прошлый годВот что вышло: http://neosapient.narod.ru/univer/Kripto/kripto_8_2.JPG Либо прикрепил ниже За помошь + Это сообщение отредактировал(а) neosapient - 3.1.2007, 14:58 Присоединённый файл ( Кол-во скачиваний: 4 ) 
kripto_8_2.JPG 61,27 Kb |
|||
|
||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.0680 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |