Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Решить сравнение по модулю: 101*X = 1 (mod 13297)
СообщениеДобавлено: 11 янв 2014, 13:28 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2014, 13:19
Сообщений: 3
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Будьте добры, помогите решить сравнение: 101*X[math]\equiv[/math]1 (mod 13297)
Никак не могу разобраться, как к нему подступаться.

Проверял здесь Онлайн решение сравнений по модулю

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решить сравнение по модулю: 101*X = 1 (mod 13297)
СообщениеДобавлено: 11 янв 2014, 14:31 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Как пытались решить, напишите.
Сравнение стандартное, решается через поиск обратного элемента алгоритмом Евклида, описание его есть в учебниках и в интернетах. Пробовали? Получилось?
Формулы оформляйте, пожалуйста, тегом math, а то я отвечать не буду.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Sonic "Спасибо" сказали:
_Meddle
 Заголовок сообщения: Re: Решить сравнение по модулю: 101*X = 1 (mod 13297)
СообщениеДобавлено: 11 янв 2014, 16:40 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2014, 13:19
Сообщений: 3
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
[math]101X \equiv 1 (mod 13297)[/math]
[math]NOD(101,13297)=1[/math], значит имеем одно решение, пытался прибавлять к правой части число модуля, искать [math]NOD(101,1+13297*k)[/math] чисел. Раз 15 я эту операцию выполнил и за отсутствием результата вынужден был прекратить тщетные попытки. Уважаемый Sonic, объясните, пожалуйста, как решать такое сравнение.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решить сравнение по модулю: 101*X = 1 (mod 13297)
СообщениеДобавлено: 11 янв 2014, 17:38 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
_Meddle писал(а):
[math]101X \equiv 1 (mod 13297)[/math]
[math]NOD(101,13297)=1[/math], значит имеем одно решение
Да, правильно.

_Meddle писал(а):
пытался прибавлять к правой части число модуля, искать [math]NOD(101,1+13297*k)[/math] чисел. Раз 15 я эту операцию выполнил и за отсутствием результата вынужден был прекратить тщетные попытки. ... объясните, пожалуйста, как решать такое сравнение.
Ага, ну вот - это Вы сейчас пытались искать решение уравнения [math]1+101k=13297t[/math], причем простым перебором, а не алгоритмом Евклида, потому этот метод будет работать долго ([math]O(m)[/math], где [math]m[/math] - модуль (у Вас [math]m=13297[/math])).
Так вот, есть такая шутка - алгоритм Евклида (помните, я Вам о нем говорил): это алгоритм, находящий для двух данных чисел [math]a,b[/math] найти их наибольший общий делитель [math]d=\gcd(a,b)[/math] ([math]\gcd[/math] - это НОД). Более того, есть чуть более сложный расширенный алгоритм Евклида, который для двух данных чисел [math]a,b[/math] возвращает такие [math]d,x,y[/math], что [math]ax+by=d[/math].
Описание алгоритма есть в книжках по теории чисел и в интернете, м.б. даже на этом сайте. Вот я нагуглил, например, самостоятельно: http://www.liveexpert.ru/topic/view?topic_id=70626
У Вас [math]a=101, m=13297[/math], [math]\gcd(a,m)=1[/math] применяя к этой паре чисел расширенный алгоритм Евклида, получите пару чисел [math]u,v[/math] такую, что [math]au+mv=1[/math]. Из последнего соотношения следует, что [math]au\equiv 1\pmod m[/math], т.е. [math]X\equiv u \pmod m[/math] - это будет искомое решение.
Расширенный алгоритм Евклида работает за [math]O(\ln m)[/math] операций, т.е. очень быстро.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Sonic "Спасибо" сказали:
_Meddle
 Заголовок сообщения: Re: Решить сравнение по модулю: 101*X = 1 (mod 13297)
СообщениеДобавлено: 11 янв 2014, 18:18 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2014, 13:19
Сообщений: 3
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Благодарю вас за содержательный и чёткий ответ, очень полезный способ решения, буду разбирать сей метод.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решить сравнение по модулю: 101*X = 1 (mod 13297)
СообщениеДобавлено: 13 янв 2014, 19:09 
Не в сети
Администратор
Аватара пользователя
Зарегистрирован:
23 фев 2010, 22:52
Сообщений: 6003
Cпасибо сказано: 3247
Спасибо получено:
3150 раз в 2273 сообщениях
Очков репутации: 652

Добавить очки репутацииУменьшить очки репутации
Должны получить [math]x\equiv 3423~(\operatorname{mod}13297)[/math].
Проверить можно с помощью онлайн-сервиса

http://mathhelpplanet.com/static.php?p=onlain-naiti-nod-i-nok

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решить сравнение по модулю: 101*X = 1 (mod 13297)
СообщениеДобавлено: 10 май 2019, 15:07 
Не в сети
Последняя инстанция
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Добавить очки репутацииУменьшить очки репутации
Можно значительно упростить решение, если
решать обратное сравнение

[math]13297x\equiv-1\pmod{101}[/math]

[math]x=26+101k[/math]
и т.д

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решить сравнение по модулю: 101*X = 1 (mod 13297)
СообщениеДобавлено: 12 май 2019, 21:01 
Не в сети
Beautiful Mind
Зарегистрирован:
17 апр 2019, 04:57
Сообщений: 1208
Откуда: Грузия
Cпасибо сказано: 99
Спасибо получено:
41 раз в 41 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
_Meddle писал(а):
Будьте добры, помогите решить сравнение: 101*X[math]\equiv[/math]1 (mod 13297)
Никак не могу разобраться, как к нему подступаться.

Проверял здесь Онлайн решение сравнений по модулю

то что вы называете сравнение я называю упорядоченое произведение вычетов 101*Х здесь х второй вычет при 1 (mod 13297) образуется цикл несколких разных главных фундаментальных арифметических прогрессии у каждой из которых есть свой х при 101*X =1mod 13297 --когда вы будете знать и изучите эти прогрессии то и суть поимете и решать будете моментально ---хотя теория чисел на сегодняшный момент не распологает этими знаниями хотя имеет все инструменты для этого 1+13297k содержит все главные прогрессии и цикл идет 31n -
я больше чем уверен что вы не понимаете что я сейчась обьясняю

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 8 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Решить сравнение по модулю 3x = -14 (mod 1)

в форуме Теория чисел

turok412

8

716

27 май 2019, 21:02

Решить сравнение по модулю

в форуме Теория чисел

K1b0rg

9

1371

27 июн 2018, 03:58

Сравнение по модулю

в форуме Теория чисел

Reaver

1

321

04 июн 2020, 00:36

Сравнение по модулю

в форуме Линейная и Абстрактная алгебра

mar_chokidar

3

284

27 окт 2020, 17:03

Сравнение по модулю

в форуме Теория чисел

Chemist

1

500

04 фев 2017, 18:16

Сравнение по модулю

в форуме Теория чисел

Julia124

1

595

07 ноя 2015, 20:09

Сравнение по модулю

в форуме Алгебра

max2000

2

437

09 дек 2017, 11:25

Сравнение по модулю

в форуме Теория чисел

Julia124

5

863

07 ноя 2015, 20:27

Сравнение чисел по модулю

в форуме Теория чисел

KeepCalm

4

657

23 ноя 2016, 19:53

Задача на сравнение по модулю

в форуме Линейная и Абстрактная алгебра

ferio23

12

508

05 янв 2023, 19:09


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 16


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved