2020-06-20    esa    約数    整数    互いに素  

整数$m$の約数と互いに素な数の個数を、$m$の約数すべてについて足し合わせると$m$に等しくなる。

定理

\(m\)を正の整数とします。

正の整数\(d\)が\(m\)の約数であることを\(d|m\)と表します。

また、正の整数\(d\)と互いに素である正の整数の個数を\(\varphi(d)\)で表します。

このとき、 \[ \sum_{d|m}\varphi(d) = m \] が成り立ちます。

例

\(m = 20\)の場合を考えましょう。

\(d|m\)が成り立つ正の整数\(d\)（すなわち\(m\)の約数\(d\)）は、 \[ d = 1,2,4,5,10,20 \] です。このそれぞれの\(d\)について\(\varphi(d)\)を求めると、 \[ \begin{align*} \varphi( 1) &= 1 && \text{（$1$と互いに素である正 $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ 整数は$1$ $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ $1$個 $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ み）} \\ \varphi( 2) &= 1 && \text{（$2$と互いに素である正 $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ 整数は$1$ $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ $1$個 $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ み）} \\ \varphi( 4) &= 2 && \text{（$4$と互いに素である正 $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ 整数は$1$と$3$ $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ $2$個）} \\ \varphi( 5) &= 4 && \text{（$5$と互いに素である正 $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ 整数は$1,2,3,4$ $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ $4$個）} \\ \varphi(10) &= 4 && \text{（$10$と互いに素である正 $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ 整数は$1,5,7,9$ $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ $4$個）} \\ \varphi(20) &= 8 && \text{（$1$と互いに素である正 $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ 整数は$1,3,7,9,11,13,17,19$ $\!\unicode[sans-serif,STIXGeneral]{x306E}\!$ $8$個）} \\ \end{align*} \] となります。 すると、 \[ \begin{align*} \sum_{d|20}\varphi(d) &= \varphi( 1) + \varphi( 2) + \varphi( 4) + \varphi( 5) + \varphi(10) + \varphi(20) \\ &= 1 + 1 + 2 + 4 + 4 + 8 \\ &= 20 \end{align*} \] となって確かに、 \[ \sum_{d|20}\varphi(d) = 20 \] が成り立っています。

動画

参考

• 中島匠一,『代数と数論の基礎』, 共立出版, ISBN978-4-320-01561-6, 2000年.

 2020-06-20    esa    約数    整数    互いに素