Формула Лежандра

Выражение теории чисел

В математике формула Лежандра дает выражение для показателя наибольшей степени простого числа p , делящей факториал  n !. Она названа в честь Адриена-Мари Лежандра . Иногда ее также называют формулой де Полиньяка , в честь Альфонса де Полиньяка .

Заявление

Для любого простого числа p и любого положительного целого числа n пусть будет показателем наибольшей степени p , которая делит n (то есть p -адической оценкой n ) . Тогда ${\displaystyle \nu _{p}(n)}$

${\displaystyle \nu _{p}(n!)=\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ,}$

где — функция пола . В то время как сумма в правой части является бесконечной суммой, для любых конкретных значений n и p она имеет только конечное число ненулевых членов: для каждого i, достаточно большого, что , имеем . Это сводит бесконечную сумму выше к ${\displaystyle \lfloor x\rfloor }$ ${\displaystyle p^{i}>n}$ ${\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =0}$

${\displaystyle \nu _{p}(n!)=\sum _{i=1}^{L}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \,,}$

где . ${\displaystyle L=\lfloor \log _{p}n\rfloor }$

Пример

Для n = 6 имеем . Показатели степени и можно вычислить по формуле Лежандра следующим образом: ${\displaystyle 6!=720=2^{4}\cdot 3^{2}\cdot 5^{1}}$ ${\displaystyle \nu _{2}(6!)=4,\nu _{3}(6!)=2}$ ${\displaystyle \nu _{5}(6!)=1}$

${\displaystyle {\begin{aligned}\nu _{2}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{2^{i}}}\right\rfloor =\left\lfloor {\frac {6}{2}}\right\rfloor +\left\lfloor {\frac {6}{4}}\right\rfloor =3+1=4,\\[3pt]\nu _{3}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{3^{i}}}\right\rfloor =\left\lfloor {\frac {6}{3}}\right\rfloor =2,\\[3pt]\nu _{5}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{5^{i}}}\right\rfloor =\left\lfloor {\frac {6}{5}}\right\rfloor =1.\end{aligned}}}$

Доказательство

Так как является произведением целых чисел от 1 до n , то мы получаем по крайней мере один множитель p в для каждого кратного p в , которых имеется . Каждый кратный вносит дополнительный множитель p , каждый кратный вносит еще один множитель p и т. д. Сложение числа этих множителей дает бесконечную сумму для . ${\displaystyle n!}$ ${\displaystyle n!}$ ${\displaystyle \{1,2,\dots ,n\}}$ ${\displaystyle \textstyle \left\lfloor {\frac {n}{p}}\right\rfloor }$ ${\displaystyle p^{2}}$ ${\displaystyle p^{3}}$ ${\displaystyle \nu _{p}(n!)}$

Альтернативная форма

Можно также переформулировать формулу Лежандра в терминах p- разложения числа n . Пусть обозначает сумму цифр в p- разложении числа n ; тогда ${\displaystyle s_{p}(n)}$

${\displaystyle \nu _{p}(n!)={\frac {n-s_{p}(n)}{p-1}}.}$

Например, записывая n = 6 в двоичной системе как 6 ₁₀ = 110 ₂ , мы имеем это и так ${\displaystyle s_{2}(6)=1+1+0=2}$

${\displaystyle \nu _{2}(6!)={\frac {6-2}{2-1}}=4.}$

Аналогично, записывая 6 в троичной системе как 6 ₁₀ = 20 ₃ , мы имеем это и так ${\displaystyle s_{3}(6)=2+0=2}$

${\displaystyle \nu _{3}(6!)={\frac {6-2}{3-1}}=2.}$

Доказательство

Запишите в основании p . Тогда , и поэтому ${\displaystyle n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}}$ ${\displaystyle \textstyle \left\lfloor {\frac {n}{p^{i}}}\right\rfloor =n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}}$

${\displaystyle {\begin{aligned}\nu _{p}(n!)&=\sum _{i=1}^{\ell }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \\&=\sum _{i=1}^{\ell }\left(n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}\right)\\&=\sum _{i=1}^{\ell }\sum _{j=i}^{\ell }n_{j}p^{j-i}\\&=\sum _{j=1}^{\ell }\sum _{i=1}^{j}n_{j}p^{j-i}\\&=\sum _{j=1}^{\ell }n_{j}\cdot {\frac {p^{j}-1}{p-1}}\\&=\sum _{j=0}^{\ell }n_{j}\cdot {\frac {p^{j}-1}{p-1}}\\&={\frac {1}{p-1}}\sum _{j=0}^{\ell }\left(n_{j}p^{j}-n_{j}\right)\\&={\frac {1}{p-1}}\left(n-s_{p}(n)\right).\end{aligned}}}$

Приложения

Формула Лежандра может быть использована для доказательства теоремы Куммера . Как один частный случай, ее можно использовать для доказательства того, что если n — положительное целое число, то 4 делится тогда и только тогда, когда n не является степенью 2. ${\displaystyle {\binom {2n}{n}}}$

Из формулы Лежандра следует, что p -адическая показательная функция имеет радиус сходимости . ${\displaystyle p^{-1/(p-1)}}$

Ссылки

• Лежандр, AM (1830), Théorie des Nombres , Париж: Firmin Didot Frères
• Молл, Виктор Х. (2012), Числа и функции , Американское математическое общество , ISBN 978-0821887950, г-н  2963308, страница 77
• Леонард Юджин Диксон , История теории чисел , том 1, Институт Карнеги в Вашингтоне, 1919, стр. 263.

Внешние ссылки

• Вайсштейн, Эрик В. «Факториал». MathWorld .