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

@_MOHAX_ · Регистрация: 22.06.2013

Author24 — интернет-сервис помощи студентам

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

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
(Насчет этого (последнего) уравнения сильно сомневаюсь...)

@kabenyuk · 29.04.2014, 06:46

Сообщение от _MOHAX_

(Насчет этого (последнего) уравнения сильно сомневаюсь...)

Правильно сомневаетесь. Из такого равенства следовало бы, что 8 делит нацело единицу.

Добавлено через 1 минуту
Да и первые два равенства неверны.

@_MOHAX_ · 29.04.2014, 14:09 **[ТС]**

Опана, а можете сказать, где ошибки?)

@kabenyuk · 29.04.2014, 14:58

Сообщение от _MOHAX_

5^-1 mod 8 = 1

Сообщение от _MOHAX_

3^-1 mod 53 = 17

Оба равенства, если я их правильно понял, не верны.

@_MOHAX_ · 29.04.2014, 16:12 **[ТС]**

Сообщение от kabenyuk

Оба равенства, если я их правильно понял, не верны.

"5^-1 mod 8" и "3^-1 mod 53" - это задания, а "1" и "17" - это ответы, полученные в ходе решения, что под ними. Вот я и хочу узнать, где ошибка в этих решениях.

@kabenyuk · 29.04.2014, 16:35

Сообщение от _MOHAX_

это ответы, полученные в ходе решения, что под ними.

Вот об том и речь, что эти ответы - не ответы вовсе. Вы и сами могли бы это заметить. Так?

Сообщение от _MOHAX_

я и хочу узнать, где ошибка в этих решениях.

Думаю, что смог бы указать на ваши ошибки, при условии, что вы расшифруете записи ваших решений.

@_MOHAX_ · 29.04.2014, 16:49 **[ТС]**

Сообщение от kabenyuk

Думаю, что смог бы указать на ваши ошибки, при условии, что вы расшифруете записи ваших решений.

Я решал алгоритмом Евклида вычисления НОД. Что вам конкретно не понятно в моем решении?

@kabenyuk · 30.04.2014, 06:16

Сообщение от _MOHAX_

Что вам конкретно не понятно в моем решении?

Вам-то все понятно в вашем решении?

@_MOHAX_ · 04.05.2014, 20:25 **[ТС]**

Сообщение от kabenyuk

Вам-то все понятно в вашем решении?

мне да

Новые блоги и статьи Все статьи Все блоги /
std::vector в C++: от основ к оптимизации производительности NullReferenced 05.04.2025 Для многих программистов знакомство с std::vector происходит на ранних этапах изучения языка, но между базовым пониманием и подлинным мастерством лежит огромная дистанция. Контейнер std::vector. . .	Реляционная модель и правила Кодда: фундамент современных баз данных Codd 05.04.2025 Конец 1960-х — начало 1970-х годов был периодом глубоких трансформаций в области хранения и обработки данных. На фоне растущих потребностей бизнеса и правительственных структур существовавшие на тот. . .	Асинхронные операции в Django с Celery py-thonny 05.04.2025 Разработчики Django часто сталкиваются с проблемой, когда пользователь нажимает кнопку отправки формы и. . . ждёт. Секунды растягиваются в минуты, терпение иссякает, а интерфейс приложения замирает. . . .	Использование кэшей CPU: Максимальная производительность в Go golander 05.04.2025 Разработчикам хорошо известно, что эффективность кода зависит не только от алгоритмов и структур данных, но и от того, насколько удачно программа взаимодействует с железом. Среди множества факторов,. . .	Создаем Telegram бот на TypeScript с grammY run.dev 05.04.2025 Одна из его самых сильных сторон Telegram — это интеграция ботов прямо в экосистему приложения. В отличие от многих других платформ, он предоставляет разработчикам мощный API, позволяющий создавать. . .
Паттерны распределённых транзакций в Event-Driven микросервисах ArchitectMsa 05.04.2025 Современные программные системы всё чаще проектируются как совокупность взаимодействующих микросервисов. И хотя такой подход даёт множество преимуществ — масштабируемость, гибкость, устойчивость к. . .	Работа с объемным DOM в javascript Htext 04.04.2025 Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .	Оптимизация производительности Node.js с помощью кластеризации run.dev 04.04.2025 Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .	Управление зависимостями в Python с Poetry py-thonny 04.04.2025 Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .	Мониторинг с Prometheus в PHP Jason-Webb 04.04.2025 Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .

@_MOHAX_ 8 / 8 / 3 Регистрация: 22.06.2013 Сообщений: 173

	Алгоритм Евклида вычисления НОД - проверить корректность вычислений 28.04.2014, 21:33. Показов 1269. Ответов 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

@kabenyuk $Эксперт по математике/физике$ 4183 / 3051 / 918 Регистрация: 19.11.2012 Сообщений: 6,196
	29.04.2014, 06:46
	Сообщение от _MOHAX_ (Насчет этого (последнего) уравнения сильно сомневаюсь...) Правильно сомневаетесь. Из такого равенства следовало бы, что 8 делит нацело единицу. Добавлено через 1 минуту Да и первые два равенства неверны. 1

@_MOHAX_ 8 / 8 / 3 Регистрация: 22.06.2013 Сообщений: 173
	29.04.2014, 14:09 [ТС]
	Опана, а можете сказать, где ошибки?) 0

@kabenyuk $Эксперт по математике/физике$ 4183 / 3051 / 918 Регистрация: 19.11.2012 Сообщений: 6,196
	29.04.2014, 14:58
	Сообщение от _MOHAX_ 5^-1 mod 8 = 1 Сообщение от _MOHAX_ 3^-1 mod 53 = 17 Оба равенства, если я их правильно понял, не верны. 0

@_MOHAX_ 8 / 8 / 3 Регистрация: 22.06.2013 Сообщений: 173
	29.04.2014, 16:12 [ТС]
	Сообщение от kabenyuk Оба равенства, если я их правильно понял, не верны. "5^-1 mod 8" и "3^-1 mod 53" - это задания, а "1" и "17" - это ответы, полученные в ходе решения, что под ними. Вот я и хочу узнать, где ошибка в этих решениях. 0

@kabenyuk $Эксперт по математике/физике$ 4183 / 3051 / 918 Регистрация: 19.11.2012 Сообщений: 6,196
	29.04.2014, 16:35
	Сообщение от _MOHAX_ это ответы, полученные в ходе решения, что под ними. Вот об том и речь, что эти ответы - не ответы вовсе. Вы и сами могли бы это заметить. Так? Сообщение от _MOHAX_ я и хочу узнать, где ошибка в этих решениях. Думаю, что смог бы указать на ваши ошибки, при условии, что вы расшифруете записи ваших решений. 0

@_MOHAX_ 8 / 8 / 3 Регистрация: 22.06.2013 Сообщений: 173
	29.04.2014, 16:49 [ТС]
	Сообщение от kabenyuk Думаю, что смог бы указать на ваши ошибки, при условии, что вы расшифруете записи ваших решений. Я решал алгоритмом Евклида вычисления НОД. Что вам конкретно не понятно в моем решении? 0

@kabenyuk $Эксперт по математике/физике$ 4183 / 3051 / 918 Регистрация: 19.11.2012 Сообщений: 6,196
	30.04.2014, 06:16
	Сообщение от _MOHAX_ Что вам конкретно не понятно в моем решении? Вам-то все понятно в вашем решении? 0

@_MOHAX_ 8 / 8 / 3 Регистрация: 22.06.2013 Сообщений: 173
	04.05.2014, 20:25 [ТС]
	Сообщение от kabenyuk Вам-то все понятно в вашем решении? мне да 0