Fussy's Diary

暑くなったり、寒くなったり。調子が悪くなりそうです。

金曜日に飲み会があり、今日はしんどい一日でした。いや、二日酔いになるほど飲んではないんですけど、終了後すぐに電車に飛び乗って、座ることもできなかったので体の方は相当まいっていた模様。それでも、飲み会のおかげで作成できなかった週報を帰宅後に家で書いていました。しかし、途中で休憩を入れたら眠ってしまい、気がついたら朝の 8 時過ぎ。とりあえず週報を作成するためそのまま起きることに。昼食・夕食後に仮眠をとったので、だいぶマシな状態にはなりました。

さて、「数学問題 bot」から 2003 年の名古屋大の問題を選択してみました。

---

n を自然数とするとき m ≤ n で m と n の最大公約数が 1 となる自然数の個数を f(n) とする。
(中略)
2) p, q を互いに異なる素数とする。このとき f(pq) を求めよ。

pq 以下の自然数で、pq と互いに素ではない (最大公約数が 1 でない) 数は、0 < n < p の範囲の自然数 n と q の積 nq と 0 < m < q の範囲の自然数 m と p の積 mp、最後に pq そのものの 3 種類あります。
nq の個数は q から ( p - 1 )q までの p - 1 個。
mp の個数は p から ( q - 1 )p までの q - 1 個。

よって、pq 以下の自然数で pq と互いに素でない数は ( p - 1 ) + ( q - 1 ) + 1 = p + q - 1 個あり、1 から pq までは pq 個の数があるので、pq 以下の自然数で pq と互いに素となる数の個数 f(pq) は

f(pq) = pq - ( p + q - 1 ) = ( p - 1 )( q - 1 )個

になります。

---

さらに、素数 p のべき乗に対して、f( p^k ) を求めてみましょう。

p^k 以下の自然数で p^k と互いに素でない数は、0 < n ≤ p^k-1 の範囲の自然数 n と p の積 np となる数なので、その数は p^k-1 個です。したがって、p^k 以下の自然数で p^k と互いに素となる数の個数 f( p^k ) は

f( p^k ) = p^k - p^k-1

になります。実は、任意の自然数 m と n が互いに素であれば、

f(mn) = f(m)f(n)

が成り立ちます。また、この関数 f の正体は「オイラーのφ関数 φ(m)」で、数学者オイラー ( Leonhard Euler ) が最初に紹介したと言われています。

a と m が互いに素であれば、a の φ(m) 乗を m で割った時の余りは必ず 1 になります。これを

a^φ(m) ≡ 1 ( mod m )

と表します。m が素数 p のとき φ(p) = p - 1 なので、上式は

a^p-1 ≡ 1 ( mod p )

です。これは「フェルマーの小定理」という有名な定理です。

もし、詳細を知りたいという方は「はじめての数論」という書籍を紹介しておきます。大学入試にも出題される可能性があるので、受験生の方も読んでおいて損はないと思います。

はじめての数論 原著第3版 -- 発見と証明の大航海-ピタゴラスの定理から楕円曲線まで