Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Линейные диофантовы уравнения

Решение

Пример

Решение

Пример

Решение

Пример

Дано a = 161 и b = 28, надо найти НОД (a, b) и значения s и t.

r = r1 – q × r2 s = s1 – qs2 t = t1 – q × t2

Для отображения алгоритма мы используем следующую таблицу:

q r1 r2 R s1 s2 s t1 t2 t
                  -5
            -1   -5  
          -1   -5   -23
        -1       -23  

 

Мы получаем НОД (161, 28) = 7, s = –1 и t = 6. Ответы могут быть проверены, как это показано ниже.

(–1) × 161 + 6 × 28 = 7

 

Дано a = 17 и b = 0, найти НОД (a, b) и значения s и t.

Для отображения алгоритма мы используем таблицу.

 

q r1 r2 R s1 s2 s t1 t2 t
                   

 

Обратите внимание, что нам не надо вычислять q, r и s. Первое значение r2 соответствует условию завершения алгоритма. Мы получаем НОД (17, 0) = 17, s = 1 и t = 0. Это показывает, почему мы должны придавать начальные значения s1 — 1 и t1 — 0. Ответы могут быть проверены так, как это показано ниже:

(1 × 17) + (0 × 0) = 17

Даны a = 0 и b = 45, найти НОД (a, b) и значения s и t.

Для отображения алгоритма мы используем следующую таблицу:

 

q r1 r2 R s1 s2 s t1 t2 t
                   
                   

 

Мы получаем НОД (0,45) = 45, s = 0 и t = 1. Отсюда ясно, что мы должны инициализировать s2 равным 0, а t2 — равным 1. Ответ может быть проверен, как это показано ниже:

(0 × 0) + (1 × 45) = 45

 

Хотя очень важное приложение расширенного алгоритма Евклида будет рассмотрено далее, здесь мы остановимся на другом приложении — "нахождение решения линейных диофантовых уравнений двух переменных", а именно, уравнения ax + by = c. Мы должны найти значения целых чисел для x и y, которые удовлетворяют этому уравнению. Этот тип уравнения либо не имеет решений, либо имеет бесконечное число решений. Пусть d = НОД (a, b). Если d†c, то уравнение не имеет решения. Если d|c, то мы имеем бесконечное число решений. Одно из них называется частным, остальные — общими.

<== предыдущая лекция | следующая лекция ==>
Расширенный алгоритм Евклида | Модульная арифметика. Если d|c, то можно найти частное решение вышеупомянутого уравнения, используя следующие шаги
Поделиться с друзьями:


Дата добавления: 2014-01-03; Просмотров: 463; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.