Символом Лежандра називається мультиплікативна функція, що використовується в теорії чисел. Названа на честь французького математика Адрієна-Марі Лежандра.
Визначення Нехай a деяке ціле число і p просте число. Символ Лежандра визначається таким чином: , якщо ділиться на . , якщо є квадратичним лишком за модулем , тобто існує таке ціле , що . , якщо є квадратичним нелишком за модулем .
Властивості Мультиплікативність: Якщо , то
перший додатковий закон () другий додатковий закон () Доведення Нехай , і розглянемо рівнянь
Тут ми обираємо знак так, щоб мати правильний знак результату.
Зараз множимо рівнянь разом. Ліворуч отримуємо . Праворуч, маємо і якісь від'ємні непарні числа. Але зауважимо, що , , і т.д., отже, ці від'ємні числа є іншими парними числами за модулем , але прихованими. Отже права частина становить (кожна двійка парна до одного з членів факторіалу, щоб представити парні числа за модулем ).
Залишилось лише зауважити, що і перенести в ліву частину.
Збираючи все до купи, ми отримуємо , або по скороченні факторіалів . І , отже ми насправді маємо . Якщо — просте число, не рівне , то — частковий випадок квадратичного закону взаємності. Серед чисел рівно половина має символ Лежандра, рівний +1, а інша половина — –1. Символ Лежандра при можна обчислити за допомогою критерію Ейлера:
Обчислення Безпосереднє застосування критерію Ейлера для обчислення символу Лежандра потребує піднесення до степеня, що для великих значень і є доволі складним (зокрема, доводиться застосувати довгу арифметику) та вельми трудомістким. Набагато ефективніше обчислювати символи Лежандра через їх узагальнення — символи Якобі.
Приклад
Див. також Символ Кронекера — Якобі
Джерела
Література