Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 2 |
[ Сообщений: 11 ] | На страницу 1, 2 След. |
|
Автор | Сообщение | |
---|---|---|
just_moment |
|
|
Все время получается ответ 5, а ошибку в вычислениях не могу найти. |
||
Вернуться к началу | ||
vorvalm |
|
|
Очевидно, что
[math]x\equiv {-1}\pmod{19}[/math] |
||
Вернуться к началу | ||
just_moment |
|
|
Если я правильно делаю, то т.к. [math]\varphi (19)=18[/math], то получаем, что:
[math]x \equiv 14^{18} \times 5 \pmod{ 19 }[/math]. Так как [math]14^{2} \equiv 6 \pmod{ 19 }[/math], то сравнение будет [math]x \equiv 6 \times 14^{16} \times 5 \pmod{ 19 }[/math]. Аналогичными действиями получаю ответ: [math]x \equiv 5 \pmod{ 19 }[/math]. Как получить вычислениями ответ -1 или 18, который тоже правильный, не знаю. |
||
Вернуться к началу | ||
vorvalm |
|
|
Посмотрите внимательно гл. "Сравнения 1-ой степени" (А.А.Бухштаб)
|
||
Вернуться к началу | ||
just_moment |
|
|
Все получилось, спасибо за помощь.
|
||
Вернуться к началу | ||
badai |
|
|
[math]28 \cdot x \equiv 3 \pmod{59}[/math]
(28,59)=1, есть только одно решение прибавляем 59 [math]28x \equiv 3 + 59 \pmod{59}[/math] [math]28x \equiv 62 \pmod{59}[/math] [math]\left( 28,62 \right) = 2 ,\left( 2,59 \right) = 1[/math], делить на 2 [math]14x \equiv 31 \pmod{59}[/math] [math]14x \equiv 31 + 59 \pmod{59}[/math], снова прибавляем 59 [math]14x \equiv 90 \pmod{59}[/math] (14,90)=2 (59,2)=1, снова делить на 2 [math]7x \equiv 45 \pmod{59}[/math] [math]7x \equiv 45 + 59 \pmod{59}[/math] [math]7x \equiv 104 \pmod{59}[/math] , (7, 104)=1 [math]7x \equiv 104 + 59 \pmod{59}[/math] [math]7x \equiv 163 \pmod{59}[/math] [math]7x \equiv 163 + 59 \pmod{59}[/math] [math]7x \equiv 222 \pmod{59}[/math] [math]7x \equiv 222 + 59 \pmod{59}[/math] [math]7x \equiv 281 \pmod{59}[/math] [math]7x \equiv 281 + 59 \pmod{59}[/math] [math]7x \equiv 340 \pmod{59}[/math] [math]7x \equiv 340 + 59 \pmod{59}[/math] [math]7x \equiv 399 \pmod{59}[/math] , (7,399)=7, делить на 7 ответ: [math]x \equiv 57 \pmod{59}[/math] подскажите правильно ли решаю сравнение и есть ли другие методи решения? |
||
Вернуться к началу | ||
Sonic |
|
|
badai, Ваше решение правильно. При малых коэффициентах и модуле так можно ручками решать.
Однако, если Вы алгоритм в общем виде распишите, то увидите, что Вы используете факторизацию коэффициента при [math]x[/math], что в общем случае есть много времени. С другой стороны, все линейные сравнения [math]ax\equiv b\pmod m[/math] решаются алгоритмом Евклида за логарифмическое время очень быстро в общем случае - этот алгоритм нужно знать, именно он чаще всего и используется для решения сравнений. |
||
Вернуться к началу | ||
badai |
|
|
по Теорему Ейлера получаю
[math]x = 3 \cdot 28^\left( {\varphi \left( 59 \right)}- 1 \right) \pmod{59}[/math] [math]x = 3 \cdot 28^{58 - 1}\pmod{59}[/math] [math]x = 3 \cdot 28^{57} \pmod{59}[/math] дальше не могу продолжить |
||
Вернуться к началу | ||
vorvalm |
|
|
При решении подобных сравнений методом перебора можно
применять и отрицательные значения Х. В данном случае [math]x\equiv{-2}\pmod {59}[/math] |
||
Вернуться к началу | ||
badai |
|
|
но ведь 28 и 59 взаимно простие, значит есть только одно решение. Откуда взялось второе?
|
||
Вернуться к началу | ||
На страницу 1, 2 След. | [ Сообщений: 11 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Решение системы сравнений
в форуме MathCad |
10 |
655 |
26 фев 2020, 12:59 |
|
Решение степенных сравнений
в форуме Теория чисел |
9 |
639 |
23 дек 2019, 09:09 |
|
Решение сравнений по модулю
в форуме Теория чисел |
7 |
2258 |
01 дек 2015, 13:20 |
|
Решение сравнений методом Эйлера
в форуме Теория чисел |
8 |
482 |
10 янв 2021, 09:30 |
|
Найти решение системы сравнений
в форуме Численные методы |
1 |
341 |
03 мар 2021, 01:04 |
|
Система сравнений
в форуме Теория чисел |
2 |
371 |
01 дек 2017, 19:42 |
|
Система сравнений
в форуме Теория чисел |
2 |
459 |
23 ноя 2017, 18:04 |
|
Система сравнений
в форуме Теория чисел |
7 |
636 |
05 ноя 2017, 16:34 |
|
Решить систему сравнений | 2 |
185 |
27 дек 2022, 19:23 |
|
Решить систему сравнений
в форуме Теория чисел |
1 |
822 |
14 июн 2015, 19:59 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 15 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |