Французький математик Адріен-Марі Лежандр запропонував ввести зручний символ (a/p), який читається: “символ Лежандра а по пе”.

Визначення. Нехай а не кратне р. Тоді символ Лежандра визначається як:

Теорема. (Критерій Ейлера) Нехай а не кратне р. Тоді:

a^(p-1)/2º(a/p)(mod p).

Доказ. За теоремою Ферма, a^p-1º1(mod p) тобто

. В лівій частині останнього порівняння один співмножник ділиться на р, адже обидва співмножники на р ділитися не можуть, інакше їхня різниця, що дорівнює двом, ділилася б на р>2. Отже, можливе одне і тільки одне з порівнянь:

a^(p-1)/2º1(mod p)

a^(p-1)/2º-1(mod p)

Але довільний квадратний лишок а задовольняє при деякому х порівняння aºx²(mod p) і, отже, задовольняє також одержаному з нього почленним піднесенням до степеня (p-1)/2 порівнянню

a^(p-1)/2ºx^p-1º1(mod p) (знову теорема Ферма). При цьому, квадратні лишки є всіма розв’язками порівняння

a^(p-1)/2º1(mod p), оскільки, будучи порівнянням степеня (p-1)/2, воно не може мати більше (p-1)/2   розв’язків.    Це означає,   що   квадратні   нелишки задовольняють порівнянню a^(p-1)/2º-1(mod p)

(Властивість a^(p-1)/2º(a/p)(mod p), що дає критерій Ейлера, можна прийняти за визначення символу Лежандра, показавши попередньо за теоремою Ферма, що a^(p-1)/2º±1(mod p).

Приклад. Чи буде число 5 квадратом за модулем 7?

5^(7-1)/2=5³=125=18× 7-1º-1(mod7),

тобто порівняння x²º5(mod7) розв’язків не має і 5 - квадратний нелишок за модулем 7. Перелічимо найпростіші властивості символу Лежандра.

Властивість 1. Якщо aºb(mod p), то (a/p)=(b/p).

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

Властивість 2. (1/p)=1.

Доказ очевидний, адже одиниця є квадратом.

Властивість 3. .

Доказ цієї властивості випливає з критерію Ейлера при а=-1. Оскільки (p-1)/2 – парне, якщо р виду 4n+1, і непарне, якщо р виду 4n+3, то число -1 є квадратним лишком за модулем р тоді і тільки тоді, коли р виду 4n+1.

Властивість 4. .

Дійсно, лишками. Властивість 4 поширюється на будь-яке число співмножників у чисельнику символу Лежандра, взаємно простих з р. Крім того, з неї випливає

Властивість 5. , тобто в чисельнику символу Лежандра можна відкинути будь-який квадратний множник. Дійсно:

.