Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 8 ] |
|
Автор | Сообщение | |
---|---|---|
_Meddle |
|
|
Никак не могу разобраться, как к нему подступаться. Проверял здесь Онлайн решение сравнений по модулю |
||
Вернуться к началу | ||
Sonic |
|
|
Как пытались решить, напишите.
Сравнение стандартное, решается через поиск обратного элемента алгоритмом Евклида, описание его есть в учебниках и в интернетах. Пробовали? Получилось? Формулы оформляйте, пожалуйста, тегом math, а то я отвечать не буду. |
||
Вернуться к началу | ||
За это сообщение пользователю Sonic "Спасибо" сказали: _Meddle |
||
_Meddle |
|
|
[math]101X \equiv 1 (mod 13297)[/math]
[math]NOD(101,13297)=1[/math], значит имеем одно решение, пытался прибавлять к правой части число модуля, искать [math]NOD(101,1+13297*k)[/math] чисел. Раз 15 я эту операцию выполнил и за отсутствием результата вынужден был прекратить тщетные попытки. Уважаемый Sonic, объясните, пожалуйста, как решать такое сравнение. |
||
Вернуться к началу | ||
Sonic |
|
|
_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] операций, т.е. очень быстро. |
||
Вернуться к началу | ||
За это сообщение пользователю Sonic "Спасибо" сказали: _Meddle |
||
_Meddle |
|
|
Благодарю вас за содержательный и чёткий ответ, очень полезный способ решения, буду разбирать сей метод.
|
||
Вернуться к началу | ||
Alexdemath |
|
|
Должны получить [math]x\equiv 3423~(\operatorname{mod}13297)[/math].
Проверить можно с помощью онлайн-сервиса http://mathhelpplanet.com/static.php?p=onlain-naiti-nod-i-nok |
||
Вернуться к началу | ||
vorvalm |
|
|
Можно значительно упростить решение, если
решать обратное сравнение [math]13297x\equiv-1\pmod{101}[/math] [math]x=26+101k[/math] и т.д |
||
Вернуться к началу | ||
ammo77 |
|
|
_Meddle писал(а): Будьте добры, помогите решить сравнение: 101*X[math]\equiv[/math]1 (mod 13297) Никак не могу разобраться, как к нему подступаться. Проверял здесь Онлайн решение сравнений по модулю то что вы называете сравнение я называю упорядоченое произведение вычетов 101*Х здесь х второй вычет при 1 (mod 13297) образуется цикл несколких разных главных фундаментальных арифметических прогрессии у каждой из которых есть свой х при 101*X =1mod 13297 --когда вы будете знать и изучите эти прогрессии то и суть поимете и решать будете моментально ---хотя теория чисел на сегодняшный момент не распологает этими знаниями хотя имеет все инструменты для этого 1+13297k содержит все главные прогрессии и цикл идет 31n - я больше чем уверен что вы не понимаете что я сейчась обьясняю |
||
Вернуться к началу | ||
[ Сообщений: 8 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Решить сравнение по модулю 3x = -14 (mod 1)
в форуме Теория чисел |
8 |
716 |
27 май 2019, 21:02 |
|
Решить сравнение по модулю
в форуме Теория чисел |
9 |
1371 |
27 июн 2018, 03:58 |
|
Сравнение по модулю
в форуме Теория чисел |
1 |
321 |
04 июн 2020, 00:36 |
|
Сравнение по модулю
в форуме Линейная и Абстрактная алгебра |
3 |
284 |
27 окт 2020, 17:03 |
|
Сравнение по модулю
в форуме Теория чисел |
1 |
500 |
04 фев 2017, 18:16 |
|
Сравнение по модулю
в форуме Теория чисел |
1 |
595 |
07 ноя 2015, 20:09 |
|
Сравнение по модулю
в форуме Алгебра |
2 |
437 |
09 дек 2017, 11:25 |
|
Сравнение по модулю
в форуме Теория чисел |
5 |
863 |
07 ноя 2015, 20:27 |
|
Сравнение чисел по модулю
в форуме Теория чисел |
4 |
657 |
23 ноя 2016, 19:53 |
|
Задача на сравнение по модулю
в форуме Линейная и Абстрактная алгебра |
12 |
508 |
05 янв 2023, 19:09 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 16 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |