Найдите все такие P(x) что (x-2)P(x) сравнимо с 1 по модулю x^2+x+1

задан 21 Июн '17 15:40

10|600 символов нужно символов осталось
0

Для начала надо найти такие многочлены u и v, что (x-2)u+(x^2+x+1)v=1. Рассуждая стандартно, полагаем deg u < 2 и deg v < 1, и применяем метод неопределённых коэффициентов для u=ax+b, v=c. После раскрытия скобок и приравнивания коэффициентов получается система a+c=0, b-2a+c=0, c-2b=1, откуда a=-1/7, b=-3/7, c=1/7.

Теперь сравнение для многочленов (x-2)P(x)=1 (mod x^2+x+1) домножаем на u (это делать можно, так как u взаимно просто с x^2+x+1), и далее будет P(x)=u=-(x+3)/7 (mod x^2+x+1).

ссылка

отвечен 21 Июн '17 18:55

10|600 символов нужно символов осталось
0

Общее решение находится с помощью алгоритма Евклида: выражение представляется в виде $%(x-2)P(x) + (x^2 + x + 1)k = 1$%, затем применяется алгоритм для $%a = (x^2 + x + 1), b = (x - 2)$%. Вычислять значение k при этом необязательно, нам нужен P(x).
Нод = d = c = 1.

По алгоритму находим $%p_0 = \dfrac{3x^2}{7} + \dfrac{2x}{7} = -\dfrac{x + 3}{7} (mod[ x^2 + x + 1])$%.

$%P(x) = p_0 + (a/d) * m = p_0 + am = -\dfrac{x + 3}{7} + (x^2 + x + 1)m, m \in Z$%.

ссылка

отвечен 21 Июн '17 20:49

изменен 21 Июн '17 21:50

@log0: по-моему, у Вас неправильно найдено p0.

(21 Июн '17 21:08) falcao

@falcao: исправлено, спасибо.

(21 Июн '17 21:15) log0

@log0: а что изменилось? Там ведь проверка не проходит. И в качестве представителя лучше брать остаток от деления, то есть линейный многочлен.

(21 Июн '17 21:34) falcao

@falcao: почему же не проходит? Все вполне себе: http://www.wolframalpha.com/input/?i=PolynomialMod%5B(x-2)(3x%5E2%2F7+%2B+2x%2F7)+%2B+(x%5E2+%2B+x+%2B+1)k,+(x%5E2+%2B+x+%2B+1)%5D,+k+%3D1 Может мы о разных проверках?

(21 Июн '17 21:38) log0

@log0: если брать 3x^2/7, то всё сходится, но у Вас в ответе написано 3x^2/2. И линейный многочлен был бы для проверки попроще.

(21 Июн '17 21:43) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,697
×160

задан
21 Июн '17 15:40

показан
605 раз

обновлен
21 Июн '17 22:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru