Форум программистов, компьютерный форум, киберфорум
Наши страницы

Алгебра, теория чисел

Войти
Регистрация
Восстановить пароль
 
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
#1

Алгоритм Евклида вычисления НОД - проверить корректность вычислений - Алгебра

28.04.2014, 21:33. Просмотров 540. Ответов 8
Метки нет (Все метки)

Проверьте, пожалуйста, мое решение, кому не составит труда? Просто решил, а правильно или нет - могу узнать только здесь от добрых людей

1) 5^-1 mod 8 = 1 (q=1)
8 1 0
5 0 1
3 1 -1 q=1
2 -1 2
1 2 1
------------------------------------------
2) 3^-1 mod 53 = 17 (q=17)
53 1 0
3 0 1 q=17
2 1 -17
------------------------------------------
3) 24x+40y=1 (q=1)
40 1 0
24 0 1
16 1 -1 q=1
8 -1 2
8 2 -1
0 -3 1
(Насчет этого (последнего) уравнения сильно сомневаюсь...)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.04.2014, 21:33
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм Евклида вычисления НОД - проверить корректность вычислений (Алгебра):

Алгоритм Евклида - Алгебра
Ребят, собственно нужна помощь. У преподавателя по теории чисел есть 2 любимых вопроса, без которых он сразу отправляет на пересдачу. ...

Алгоритм Евклида - Алгебра
Как решить данную задачу: Надо доказать, что NOD(a^n - 1; a^m - 1) = {a}^{NOD(n;m)}-1, где NOD = НОД. Я пытался решать чисто...

Алгоритм Евклида - Алгебра
Извиняюсь, если спрашиваю очень уж очевидные вещи. Вот тут http://e-maxx.ru/algo/euclid_algorithm объясняется доказательство gcd(a,b) =...

Алгоритм Евклида NOD - Математика
Данный алгоритм можно реализовывать через остаток от деления, пока результат не станет равен нулю, а можно через отрицание, почему его...

Расширенный Алгоритм Евклида - Алгебра
Кто может объяснить "Расширенный Алгоритм Евклида" на примере решения уравнения вида: 37х=17(mod 137), буду очень благодарен.

Проверить корректность определения - Алгебра
На арифметическом пространстве R4 {x1,x2,x3,x4} задано скалярное произведение: (x,y) = 2x1 y1 + x2y2 + 3x3y3 — x1 y2 — x2y1 + x4y4....

8
kabenyuk
1719 / 1298 / 308
Регистрация: 19.11.2012
Сообщений: 2,541
29.04.2014, 06:46 #2
Цитата Сообщение от _MOHAX_ Посмотреть сообщение
(Насчет этого (последнего) уравнения сильно сомневаюсь...)
Правильно сомневаетесь. Из такого равенства следовало бы, что 8 делит нацело единицу.

Добавлено через 1 минуту
Да и первые два равенства неверны.
1
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
29.04.2014, 14:09  [ТС] #3
Опана, а можете сказать, где ошибки?)
0
kabenyuk
1719 / 1298 / 308
Регистрация: 19.11.2012
Сообщений: 2,541
29.04.2014, 14:58 #4
Цитата Сообщение от _MOHAX_ Посмотреть сообщение
5^-1 mod 8 = 1
Цитата Сообщение от _MOHAX_ Посмотреть сообщение
3^-1 mod 53 = 17
Оба равенства, если я их правильно понял, не верны.
0
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
29.04.2014, 16:12  [ТС] #5
Цитата Сообщение от kabenyuk Посмотреть сообщение
Оба равенства, если я их правильно понял, не верны.
"5^-1 mod 8" и "3^-1 mod 53" - это задания, а "1" и "17" - это ответы, полученные в ходе решения, что под ними. Вот я и хочу узнать, где ошибка в этих решениях.
0
kabenyuk
1719 / 1298 / 308
Регистрация: 19.11.2012
Сообщений: 2,541
29.04.2014, 16:35 #6
Цитата Сообщение от _MOHAX_ Посмотреть сообщение
это ответы, полученные в ходе решения, что под ними.
Вот об том и речь, что эти ответы - не ответы вовсе. Вы и сами могли бы это заметить. Так?

Цитата Сообщение от _MOHAX_ Посмотреть сообщение
я и хочу узнать, где ошибка в этих решениях.
Думаю, что смог бы указать на ваши ошибки, при условии, что вы расшифруете записи ваших решений.
0
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
29.04.2014, 16:49  [ТС] #7
Цитата Сообщение от kabenyuk Посмотреть сообщение
Думаю, что смог бы указать на ваши ошибки, при условии, что вы расшифруете записи ваших решений.
Я решал алгоритмом Евклида вычисления НОД. Что вам конкретно не понятно в моем решении?
0
kabenyuk
1719 / 1298 / 308
Регистрация: 19.11.2012
Сообщений: 2,541
30.04.2014, 06:16 #8
Цитата Сообщение от _MOHAX_ Посмотреть сообщение
Что вам конкретно не понятно в моем решении?
Вам-то все понятно в вашем решении?
0
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
04.05.2014, 20:25  [ТС] #9
Цитата Сообщение от kabenyuk Посмотреть сообщение
Вам-то все понятно в вашем решении?
мне да
0
04.05.2014, 20:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.05.2014, 20:25
Привет! Вот еще темы с ответами:

Теория чисел, алгоритм Евклида - Алгебра
Придумайте два трехзначных числа, на которых алгоритм Евклида делает наибольшее число итераций.

Кратные корни полинома(алгоритм Евклида) - Алгебра
Всем приятного времени суток:) Имеется задача: найти кратные корни полинома x^6-3x^5+2x^4-4x^3+15x^2-17x+6 с помощью алгоритма Евклида. ...

Ищу теорию: расширенный алгоритм Евклида и нахождение обратных по модулю - Алгебра
Помогите найти понятное объяснение расширенного алгоритма Евклида и применение его к нахождению обратного мультипликативного элемента по...

Самый быстрый алгоритм Евклида вычисления НОД - C (СИ)
Заинтересовал вопрос о различных реализациях алгоритма Евклида для неотрицательных целых чисел. Ниже привожу алгоритмы, собственноручно...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru