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

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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Решить сравнение по модулю: 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
Сообщений: 5975
Откуда: Москва
Cпасибо сказано: 3231
Спасибо получено:
3096 раз в 2259 сообщениях
Очков репутации: 650

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

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

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

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

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

K1b0rg

9

339

27 июн 2018, 03:58

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

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

rita

6

1332

19 май 2013, 22:06

Как решить сравнение по модулю 27x=16 (mod 58)

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

MarieLoengreen

3

10967

24 май 2010, 20:19

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

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

Julia124

5

416

07 ноя 2015, 20:27

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

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

max2000

2

139

09 дек 2017, 11:25

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

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

Julia124

1

298

07 ноя 2015, 20:09

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

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

Chemist

1

246

04 фев 2017, 18:16

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

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

feuran

2

658

22 сен 2013, 21:34

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

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

KeepCalm

4

338

23 ноя 2016, 19:53

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

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

dslink

7

71

11 ноя 2018, 18:01


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



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

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


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

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

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

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