6. Алгоритм розв’язування нерівність першого степеня з одним невідомим. Формулювання китайської теореми про залишки.

Двочленною квадратичною нерівністю називається нерівність вигляду , де - невідомі лишки.

Ціле число а називається квадратичним лишком по модулю n, якщо нерівність вирішувана. Якщо нерівність вирішуваниа, то для складеного модуля кількість рішень, як правило, більше двох.

У загальному випадку, не тільки дане завдання, але навіть питання про вирішення квадратичної нерівності по складеному модулю, факторизація якого невідома, є невирішеною проблемою.

В той же час для модулів, що є простими числами, завдання легко піддається аналізу.

Визначення і властивості символу Лежандра. Хай .

Існують алгоритми для визначення, чи є дане число а квадратичним лишком по простому модулю чи ні. Один з алгоритмів пов'язаний з обчисленням значення т.з. символу Лежандра, який для непарного простого визначається так:

Значення називається квадратичним характером числа по модулю .

Основні властивості символу Лежандра.

;

Критерій Ейлера: ;

; ;

, ; .

Квадратичний закон взаємності Гауса: для будь-яких простих непарних чисел і виконується рівність . Символ Лежандра можна обчислити за допомогою наступної послідовності дій. (1) Якщо , то виділяємо співмножник ; (2) приводимо по модулю ; (3) розкладаємо в добуток степенів простих чисел, використовуючи мультипликативність| символу Лежандра: , потім видаляємо співмножники що є квадратами; (4) виділяємо двійки, наприклад, якщо , обчислюємо ; (5) для кожного непарного співмножника застосовуємо квадратичний закон взаємності (зменшуємо величини чисел, що беруть участь в обчисленнях); (6) при необхідності, переходимо до п.(1).

7. Двочленні квадратичні порывняння. Властивості символу Лежандра.

Двочленною квадратичною нерівністю називається нерівність вигляду , де - невідомі лишки.

Ціле число а називається квадратичним лишком по модулю n, якщо нерівність вирішувана. Якщо нерівність вирішувана, то для складеного модуля кількість рішень, як правило, більше двох.

У загальному випадку, не тільки дане завдання, але навіть питання про вирішення квадратичної нерівності по складеному модулю, факторизація якого невідома, є невирішеною проблемою.

В той же час для модулів, що є простими числами, завдання легко піддається аналізу.

Властивості символу Якобі.

Хай n непарне і має наступне канонічне розкладання .

Символ Якобі числа x по модулю n, при , визначається як добуток значень символів Лежандра . Він володіє практично всіма тими ж властивостями, що і символ Лежандра, але по значенню символу Якобі рівному одиниці, не можна стверджувати, що відповідне вирахування – квадратичне.

Для квадратичних лишків символ Якобі рівний одиниці. Отже, якщо , то - квадратичні лишки по модулю .

Хай - цілі, - непарні числа, великі одиниці.

Властивості символу Якобі наступні.

; ;

; , ;

; .

Крім того, має місце квадратичний закон взаємності Гауса: для будь-яких непарних чисел m>1 і n>1 виконується рівність .

Обчислення символу Якобі полягає у використанні його властивостей для зниження величин чисел, що беруть участь в обчисленнях.

На відміну від символу Лежандра, критерій| Ейлера відсутній.