Нелинейные сравнения общего вида

Пусть f (x) = а₀ + а_лх + … + а"х" — многочлен над Z степени п > 1. Нелинейными называют сравнения вида f (x) = O (modra), где число п — степень сравнения, если а_п не делится на т.

Теорема 5.8. Сравнение f (x) = O (modp) при простом модуле р:

• а) равносильно сравнению степени не выше р — 1;
• б) имеет не более п решений, где п = deg/(x), если хоть один коэффициент не кратен р.
• 4 а) разделим с остатком f (x) па хр — х: /(х) = (хр — х) с/(х) + г (х), где degr (x) < р — 1. Поскольку хР — х = O (modp), то исходное сравнение равносильно сравнению r (x) = O (modp);
• б) пусть сравнение имеет не менее п + 1 решений, обозначим через …, х_п, х_п+{ вычеты этих решений. Тогда, используя п раз деление с остатком, представим /(х) в виде

где fj (x) = (х — х_{)…(х ~ х_{). Коэффициенты с_х вычисляются так: положим r_n(x) = f (x) и разделим с остатком г_х(х) на f_x(x), частное есть c_jf а остаток — Tj_i (x), i = 1, …, п с₀ есть остаток от деления г_{(х) на f (x). Полагая в (5.4) последовательно х = х_{> х₂,…, х_п, х_п+и получим соответственно, что коэффициенты с₀, q,…, с_п кратны р. Значит, кратны р и все коэффициенты многочлена f (x) как сумма чисел с_г, кратных р. ?

. При простом р — (р — 1)! + 1 = O (modp).

4 При р = 2 сравнение верно. При р > 2 рассмотрим сравнение степени не выше р — 2:

По малой теореме Ферма решения сравнения суть все вычеты 1, 2, …, р — 1, тогда по теореме 5.86 кратен р каждый его коэффициент, в частности свободный член, равный (р — 1)! + 1. ?

Теорема 5.9. Пусть сравнение f (x) = 0(modm,) имеет t_t решений, i = = 1, …, г, и модули т, …, т_г попарно взаимно простые, тогда эта система сравнений равносильна сравнению f (x) = 0(modmj…m_r), имеющему t = = решений.

Л Следует из свойетв сравнений 4), 8) (параграф 2.5). Множество решений сравнения f (x) = 0(modm₁…m_r) есть декартово произведение множеств решений исходных сравнений. ?