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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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




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

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

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

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

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

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

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

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

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

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

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Решить сравнение по модулю

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

K1b0rg

9

310

27 июн 2018, 04:58

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

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

rita

6

1287

19 май 2013, 23:06

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

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

max2000

2

133

09 дек 2017, 12:25

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

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

Chemist

1

244

04 фев 2017, 19:16

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

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

Julia124

1

294

07 ноя 2015, 21:09

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

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

Julia124

5

414

07 ноя 2015, 21:27

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

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

KeepCalm

4

329

23 ноя 2016, 20:53

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

в форуме Дискретная математика, Теория множеств и Логика

feuran

2

651

22 сен 2013, 22:34

Сравнение по модулю, доказать или опровергнуть

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

K1b0rg

4

184

27 июн 2018, 22:08

Сравнение по модулю - отрицательное число и число меньшее

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

afraumar

19

2836

12 авг 2013, 19:24


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



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

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


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

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

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

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