Сравнение первой степени

@zohxan · Регистрация: 02.12.2018

Author24 — интернет-сервис помощи студентам

$https://www.cyberforum.ru/cgi-bin/latex.cgi?32x\equiv 63 (mod 119)$

Начал я так: ищу НОД(63, 119). Он равен единице, значит искомый икс единственный.

Осталось найти x = $https://www.cyberforum.ru/cgi-bin/latex.cgi?63*32^{\phi(119)-1}$ = 63*32^95. Считать я с ума сойду. Что можно сделать?

@kabenyuk · 20.01.2019, 17:45

Сообщение от zohxan

Считать я с ума сойду. Что можно сделать?

Не считать.

@wer1 · 20.01.2019, 18:06

Уважаемый zohxan
мне кажется, что надо стремиться уменьшить коэффициент при икс.
Итак, дано
32x = 63 (mod 119)
умножим на 4
128x = 252 (mod 119)
9x = 14 (mod 119)
умножим на 13
117x = 182 (mod 119)
2x = 56 (mod 119)
x = 28 (mod 119)
надеюсь, что не ошибся (всё сосчитано в уме)

@zohxan · 20.01.2019, 18:18 **[ТС]**

Я прошу прощения, но мне ничего не ясно
UPD: хотя что-то в этом есть. Вы отнимали от каждого числа 119. Не видел ранее такого, но если такое всегда справедливо, то благодарю!

@kabenyuk · 20.01.2019, 18:29

Сообщение от zohxan

но мне ничего не ясно

Бывает. Предлагаю еще так сделать, раз готовы считать: 32=2^5 ==> 32^95=2^475. После этого разделите 475 с остатком на 96.

@zohxan 0 / 0 / 0 Регистрация: 02.12.2018 Сообщений: 22
		1
	Сравнение первой степени 20.01.2019, 17:39. Показов 1112. Ответов 4 Метки нод, остаток, сравнение (Все метки) $https://www.cyberforum.ru/cgi-bin/latex.cgi?32x\equiv 63 (mod 119)$ Начал я так: ищу НОД(63, 119). Он равен единице, значит искомый икс единственный. Осталось найти x = $https://www.cyberforum.ru/cgi-bin/latex.cgi?6332^{\phi(119)-1}$ = 6332^95. Считать я с ума сойду. Что можно сделать? 0

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	20.01.2019, 17:45	2
	Сообщение от zohxan Считать я с ума сойду. Что можно сделать? Не считать. 0

@wer1 1104 / 480 / 33 Регистрация: 05.07.2018 Сообщений: 1,870 Записей в блоге: 7
	20.01.2019, 18:06	3
	Уважаемый zohxan мне кажется, что надо стремиться уменьшить коэффициент при икс. Итак, дано 32x = 63 (mod 119) умножим на 4 128x = 252 (mod 119) 9x = 14 (mod 119) умножим на 13 117x = 182 (mod 119) 2x = 56 (mod 119) x = 28 (mod 119) надеюсь, что не ошибся (всё сосчитано в уме) 0

@zohxan 0 / 0 / 0 Регистрация: 02.12.2018 Сообщений: 22
	20.01.2019, 18:18 [ТС]	4
	Я прошу прощения, но мне ничего не ясно UPD: хотя что-то в этом есть. Вы отнимали от каждого числа 119. Не видел ранее такого, но если такое всегда справедливо, то благодарю! 0

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	20.01.2019, 18:29	5
	Сообщение от zohxan но мне ничего не ясно Бывает. Предлагаю еще так сделать, раз готовы считать: 32=2^5 ==> 32^95=2^475. После этого разделите 475 с остатком на 96. 0