問題
を相異なる素数 の積とする。 を の約数とするとき， の最大公約数を ，最小公倍数を とし，
とする。
(1) が の約数であることを示せ。
(2) ならば， であることを示せ。
(3) を自然数とするとき， の約数であるような素数の個数を とする。 が偶数であることを示せ。
出典：東京工業大学 2015年度 前期日程 理系 第5問
方針
が相異なる素数の積であることから， は各 を使うか使わないかだけで決まる。各素数について， のどちらにも含まれる場合は最大公約数と最小公倍数で打ち消され，片方だけに含まれる場合だけ に残る。この「素数ごとの分類」で (1) から (3) までを処理する。
解答
(1)
は相異なる素数 の積であるから， の約数である では，各 はそれぞれ高々1回だけ現れる。ある について見ると， が の両方を割るときは と の両方に が1回ずつ現れるので， には現れない。 が のちょうど一方だけを割るときは， には現れ， には現れないので， に1回現れる。どちらも割らないときは現れない。
したがって は， のうちいくつかを1回ずつ掛けた数である。よって は の約数である。
(2)
とする。もしある素数 が を割るなら，次の2通りがある。
まず が も割る場合， は と の両方に現れるので を割らない。しかし は を割るから， に反する。
次に が を割らない場合， は を割るが を割らない。これも に反する。
したがって を割る素数 は存在しない。 は の約数であるから， である。
(3)
各素数 について， への寄与を調べる。
いずれの場合も寄与は偶数である。すべての についてこれらの寄与を加えたものが であるから，この数は偶数である。