Распечатать запись Распечатать запись

Определитель Смита

Генри Джон Стивен Смит (1826–1883) — английский математик, известный прежде всего своими работами по элементарным делителям, квадратичным формам и формулой Смита — Минковского — Зигеля для масс. В теории матриц используется нормальная форма Смита для матрицы.

Определитель Смита имеет вид

D=\left|\begin{array}{ccccc}<br />
(1,1)&(1,2)&(1,3)&\ldots&(1,n)\\<br />
(2,1)&(2,2)&(2,3)&\ldots&(2,n)\\<br />
(3,1)&(3,2)&(3,3)&\ldots&(3,n)\\<br />
\ldots&&&&\\<br />
(n,1)&(n,2)&(n,3)&\ldots&(n,n)<br />
\end{array}\right|,

где (i,j) обозначает наибольший общий делитель чисел i и j.

А равен этот определитель довольно красивой величине:

D=\varphi(1)\varphi(2)\varphi(3)\ldots\varphi(n),


где \varphi(n)функция Эйлера натурального числа n (т.е. количество чисел, не превосходящих n и взаимно простых с n).

Докажем сначала, что любое натуральное число n представимо в виде суммы значений функции Эйлера от его натуральных делителей:

\displaystyle n=\sum_{d|n}\varphi(d)

(здесь d|n обозначает, что d — делитель n).

Пусть разложение числа n на простые множители имеет вид

n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_m^{\alpha_m}.

Тогда любой делитель d числа n может быть записан в виде

d=p_1^{\beta_1}p_2^{\beta_2}\ldots p_m^{\beta_m},

где 0\le\beta_1\le\alpha_1,0\le\beta_2\le\alpha_2,\ldots,0\le\beta_m\le\alpha_m.

В силу мультипликативности функции Эйлера имеем

\varphi(d)=\varphi(p_1^{\beta_1}p_2^{\beta_2}\ldots p_m^{\beta_m})=\varphi(p_1^{\beta_1})\varphi(p_2^{\beta_2})\ldots \varphi(p_m^{\beta_m}).

Теперь рассмотрим выражение

(1+\varphi(p_1)+\varphi(p_1^2)+\ldots+\varphi(p_1^{\alpha_1}))(1+\varphi(p_2)+\varphi(p_2^2)+\ldots+\varphi(p_2^{\alpha_2}))\times\ldots

\times(1+\varphi(p_m)+\varphi(p_m^2)+\ldots+\varphi(p_m^{\alpha_1}))

После раскрытия скобок с учетом предыдущего замечания получаем, что это выражение равно \displaystyle \sum_{d|n}\varphi(d).

Далее воспользуемся формулой для вычисления функции Эйлера степени простого числа

\varphi(p^k)=p^k-p^{k-1}

(см. здесь):

\displaystyle \sum_{d|n}\varphi(d)=(1+(p_1-1)+(p_1^2-p_1)+\ldots+(p_1^{\alpha_1}-p_1^{\alpha_1-1}))\times

\times(1+(p_2-1)+(p_2^2-p_2)+\ldots+(p_2^{\alpha_2}-p_2^{\alpha_2-1}))\times\ldots

\times(1+(p_m-1)+(p_m^2-p_m)+\ldots+(p_m^{\alpha_m}-p_m^{\alpha_m-1}))

и после приведения подобных слагаемых в каждой большой скобке получим

\displaystyle \sum_{d|n}\varphi(d)=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_m^{\alpha_m}=n.

Отсюда следует, что

\displaystyle (i,j)=\sum_{d|(i,j)}\varphi(d).

Суммирование здесь производится по всем значениям d, которые являются делителями (i,j), иначе говоря, по всем общим делителям чисел i и j. Поэтому можно представить (i,j) в следующем виде:

(i,j)=a_{i1}a_{j1}\varphi(1)+a_{i2}a_{j2}\varphi(2)+a_{i3}a_{j3}\varphi(3)+\ldots+a_{in}a_{jn}\varphi(n),

условившись считать a_{ij}=1, когда i делится на j, и a_{ij}=0, когда i не делится на j (так что для всех значений i< j a_{ij}=0). В самом деле, при этих условиях коэффициент a_{i\nu}a_{j\nu} при \varphi(\nu) будет равен 1, когда i и j оба делятся на \nu, и равен нулю, когда \nu не является общим делителем чисел i и j, так что в правой части приведенной выше формулы будем иметь \sum\varphi(\nu), взятую по всем общим делителям \nu чисел i и j. Тогда

D=\left|\begin{array}{ccccc}<br />
a_{11}&a_{12}&a_{13}&\ldots&a_{1n}\\<br />
a_{21}&a_{22}&a_{23}&\ldots&a_{2n}\\<br />
a_{31}&a_{32}&a_{33}&\ldots&a_{3n}\\<br />
\ldots&&&&\\<br />
a_{n1}&a_{n2}&a_{n3}&\ldots&a_{nn}<br />
\end{array}\right|\cdot\left|\begin{array}{ccccc}<br />
a_{11}\varphi(1)&a_{12}\varphi(2)&a_{13}\varphi(3)&\ldots&a_{1n}\varphi(n)\\<br />
a_{21}\varphi(1)&a_{22}\varphi(2)&a_{23}\varphi(3)&\ldots&a_{2n}\varphi(n)\\<br />
a_{31}\varphi(1)&a_{32}\varphi(2)&a_{33}\varphi(3)&\ldots&a_{3n}\varphi(n)\\<br />
\ldots&&&&\\<br />
a_{n1}\varphi(1)&a_{n2}\varphi(2)&a_{n3}\varphi(3)&\ldots&a_{nn}\varphi(n)<br />
\end{array}\right|=

=\left|\begin{array}{ccccc}<br />
1&0&0&0&\ldots\\<br />
1&1&0&0&\ldots\\<br />
1&0&1&0&\ldots\\<br />
1&1&0&1&\ldots\\<br />
\ldots&&&&<br />
\end{array}\right|\cdot\left|\begin{array}{ccccc}<br />
a_{11}\varphi(1)&0&0&\ldots&0\\<br />
a_{21}\varphi(1)&a_{22}\varphi(2)&0&\ldots&0\\<br />
a_{31}\varphi(1)&a_{32}\varphi(2)&a_{33}\varphi(3)&\ldots&0\\<br />
\ldots&&&&\\<br />
a_{n1}\varphi(1)&a_{n2}\varphi(2)&a_{n3}\varphi(3)&\ldots&a_{nn}\varphi(n)<br />
\end{array}\right|=

=\varphi(1)\varphi(2)\ldots\varphi(n).

Источники: Чезаро Э. Элементарный учебник алгебраического анализа и исчисления бесконечно малых. Одесса, 1913.

И.М. Виноградов. Основы теории чисел. Лань, 2004.

http://en.wikipedia.org/wiki/Henry_John_Stephen_Smith

Оставьте свой отзыв

Добавить изображение