Форум программистов, компьютерный форум, киберфорум
Дискретная математика
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 13.05.2014
Сообщений: 15
1

Алгоритм Эвклида

13.05.2014, 20:30. Показов 1227. Ответов 5
Метки нет (Все метки)

показать, что для произвольных целых чисел а и б, уравнение ах+бу=НОД(а,б) разрешимо в целых числах
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.05.2014, 20:30
Ответы с готовыми решениями:

Алгоритм Эвклида
Такой вопрос. Мне нужно написать программу , которая находит НОД(наибольший общий делитель) для 3-х...

алгоритм эвклида
как работает этот код? int gcd(int a, int b) { while(b) b^=a^=b^=a%=b; return a; }

Алгоритм Эвклида
Как оценить сложность алгоритма Эвклида для поиска наибольшего общего делителя?

Задание на алгоритм Эвклида
Заданы целочисельные массивы А(n), B(n).Построить массив С(n), каждый элемент которого является...

5
2523 / 1749 / 152
Регистрация: 11.08.2012
Сообщений: 3,349
14.05.2014, 13:18 2
Пусть а=а1*НОД(а,б), б=б1*НОД(а,б), тогда исходное уравнение приведем к а1*х+б1*у=1, поделив на НОД(а,б).
Выразим х: х=1 - б1*у/а1. Тогда, очевидно, достаточно чтобы у делилось на а1, чтобы решением была пара целых чисел.
0
Эксперт по математике/физике
3915 / 2905 / 881
Регистрация: 19.11.2012
Сообщений: 6,021
14.05.2014, 14:03 3
Цитата Сообщение от cmath Посмотреть сообщение
Тогда, очевидно, достаточно чтобы у делилось на а1, чтобы решением была пара целых чисел.
Это замечание нисколько не приближает к решению задачи.
Задачу решил Ферма и потому назвал метод ее решения алгоритмом Евклида.
0
2523 / 1749 / 152
Регистрация: 11.08.2012
Сообщений: 3,349
14.05.2014, 14:35 4
В смысле? Надо же доказать существование решения, а не искать само решение.
0
Эксперт по математике/физике
3915 / 2905 / 881
Регистрация: 19.11.2012
Сообщений: 6,021
14.05.2014, 15:01 5
Цитата Сообщение от cmath Посмотреть сообщение
Надо же доказать существование решения
Конечно. Но ваше замечание не доказывает существование решения. Ведь после деления на НОД сформулированное ТС утверждение сводится к такому. Если а и b взаимно просты, то существуют целые х и у, для которых ax+by=1.
0
2523 / 1749 / 152
Регистрация: 11.08.2012
Сообщений: 3,349
15.05.2014, 08:01 6
Цитата Сообщение от kabenyuk Посмотреть сообщение
Если а и b взаимно просты, то существуют целые х и у, для которых ax+by=1.
Был не прав.
***
ТС:
Расширенный алгоритм Евклида тут
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.05.2014, 08:01

Алгоритм Эвклида (в чем ошибка)
вот программа Program prost_chisla; uses crt; const m=5000; var A:array of integer; ...

Алгоритм Эвклида. 10 пар чисел
Как сгенерировать 10 пар чисел, в промежутках от 0 до 100, чтобы потом применить алгоритм Эвклида к...

Вычислить выражение в поле, используя алгоритм Эвклида
найти 20 (в степени -1) в поле Z/ mod 73 используя алгоритм Эвклида

Алгоритм эвклида для чисел с любым знаком
Нашел такой код: int gcd05(int first, int second) { while (first != second) { if (first >...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru