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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 11 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Решение сравнений
СообщениеДобавлено: 31 окт 2013, 20:41 
Не в сети
Начинающий
Зарегистрирован:
31 окт 2013, 20:32
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте, помогите решить сравнение: [math]14x\equiv 5 \pmod{ 19 }[/math]
Все время получается ответ 5, а ошибку в вычислениях не могу найти.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение сравнений
СообщениеДобавлено: 31 окт 2013, 21:07 
Не в сети
Последняя инстанция
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Добавить очки репутацииУменьшить очки репутации
Очевидно, что

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение сравнений
СообщениеДобавлено: 31 окт 2013, 21:31 
Не в сети
Начинающий
Зарегистрирован:
31 окт 2013, 20:32
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Если я правильно делаю, то т.к. [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, который тоже правильный, не знаю.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение сравнений
СообщениеДобавлено: 31 окт 2013, 22:25 
Не в сети
Последняя инстанция
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Добавить очки репутацииУменьшить очки репутации
Посмотрите внимательно гл. "Сравнения 1-ой степени" (А.А.Бухштаб)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение сравнений
СообщениеДобавлено: 31 окт 2013, 23:02 
Не в сети
Начинающий
Зарегистрирован:
31 окт 2013, 20:32
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение сравнений
СообщениеДобавлено: 07 ноя 2013, 01:51 
Не в сети
Начинающий
Зарегистрирован:
05 ноя 2013, 11:29
Сообщений: 9
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
[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]

подскажите правильно ли решаю сравнение и есть ли другие методи решения?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение сравнений
СообщениеДобавлено: 07 ноя 2013, 06:15 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
badai, Ваше решение правильно. При малых коэффициентах и модуле так можно ручками решать.
Однако, если Вы алгоритм в общем виде распишите, то увидите, что Вы используете факторизацию коэффициента при [math]x[/math], что в общем случае есть много времени. С другой стороны, все линейные сравнения [math]ax\equiv b\pmod m[/math] решаются алгоритмом Евклида за логарифмическое время очень быстро в общем случае - этот алгоритм нужно знать, именно он чаще всего и используется для решения сравнений.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение сравнений
СообщениеДобавлено: 12 ноя 2013, 16:47 
Не в сети
Начинающий
Зарегистрирован:
05 ноя 2013, 11:29
Сообщений: 9
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
по Теорему Ейлера получаю

[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]

дальше не могу продолжить :-(

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение сравнений
СообщениеДобавлено: 12 ноя 2013, 18:10 
Не в сети
Последняя инстанция
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Добавить очки репутацииУменьшить очки репутации
При решении подобных сравнений методом перебора можно
применять и отрицательные значения Х.
В данном случае [math]x\equiv{-2}\pmod {59}[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решение сравнений
СообщениеДобавлено: 13 ноя 2013, 09:33 
Не в сети
Начинающий
Зарегистрирован:
05 ноя 2013, 11:29
Сообщений: 9
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
но ведь 28 и 59 взаимно простие, значит есть только одно решение. Откуда взялось второе?

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

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

в форуме MathCad

Olga_sh

10

655

26 фев 2020, 12:59

Решение степенных сравнений

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

Ta3ik

9

639

23 дек 2019, 09:09

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

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

black80

7

2258

01 дек 2015, 13:20

Решение сравнений методом Эйлера

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

emert

8

482

10 янв 2021, 09:30

Найти решение системы сравнений

в форуме Численные методы

pomogite_reshit

1

341

03 мар 2021, 01:04

Система сравнений

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

yidajiwi

2

371

01 дек 2017, 19:42

Система сравнений

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

AndreyStepanenko1234

2

459

23 ноя 2017, 18:04

Система сравнений

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

huffy

7

636

05 ноя 2017, 16:34

Решить систему сравнений

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

vldkarpv

2

185

27 дек 2022, 19:23

Решить систему сравнений

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

Wolkov Andrey

1

822

14 июн 2015, 19:59


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



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

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


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

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

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

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