東京工業大学 2016年 理系 第4問 解説

方針・初手

階乗 $(n-1)!$ が $n$ で割り切れるかどうかは、$(n-1)!$ の積を構成する $1, 2, \ldots, n-1$ のなかに、$n$ の約数がどのように含まれているかを考えることで判定できる。 (1)は $n=4$ の場合を具体的に計算し、$n$ が素数の場合は素数の性質（自身より小さい自然数と互いに素であること）を利用して背理法等で示す。 (2)は $n$ が素数でなく $4$ でもない（つまり $6$ 以上の合成数である）ため、$n = ab$ ($2 \leqq a \leqq b < n$) と表せる。$a \neq b$ の場合と $a = b$ の場合に分けて、$(n-1)!$ の積の中に $n$ の素因数が十分に存在することを示す。

解法1

(1)

$n$ が $4$ のときと素数のときに分けて示す。

(i)

$n=4$ のとき

$$ (4-1)! = 3! = 6 $$

$6$ は $4$ で割り切れない。よって、$n=4$ のとき命題は成立する。

(ii)

$n$ が素数のとき

$n$ は素数であるから、$n$ の正の約数は $1$ と $n$ のみである。 もし $(n-1)!$ が $n$ で割り切れると仮定すると、ある整数 $k$ を用いて次のように表せる。

$$ (n-1)! = kn $$

すなわち、

$$ 1 \cdot 2 \cdot 3 \cdots (n-1) = kn $$

$n$ は素数であるから、左辺の積を構成する自然数 $1, 2, \ldots, n-1$ のいずれかが $n$ の倍数でなければならない。 しかし、$1, 2, \ldots, n-1$ はすべて $n$ より小さい自然数であり、$n$ の倍数となるものは存在しない。 これは矛盾である。 したがって、$(n-1)!$ は $n$ で割り切れない。

（i）, （ii） より、$n$ が素数または $4$ のとき、$(n-1)!$ は $n$ で割り切れない。

(2)

$n$ は素数でなくかつ $4$ でもない $2$ 以上の自然数であるから、$n$ は $6$ 以上の合成数である。 したがって、$n$ はある自然数 $a, b$ を用いて $n = ab$ と表すことができる。ただし、$2 \leqq a \leqq b < n$ とする。

$a$ と $b$ の大小関係について、次の2つの場合に分けて考える。

(i)

$a < b$ のとき

$2 \leqq a < b < n$ であるから、$a$ と $b$ はともに $n-1$ 以下の相異なる自然数である。 $(n-1)!$ は $1$ から $n-1$ までのすべての自然数の積であるから、その積の中には $a$ と $b$ がそれぞれ独立に因数として含まれる。

$$ (n-1)! = 1 \cdot 2 \cdots a \cdots b \cdots (n-1) $$

よって、$(n-1)!$ は $ab$、すなわち $n$ の倍数となる。 したがって、$(n-1)!$ は $n$ で割り切れる。

(ii)

$a = b$ のとき

$n = a^2$ となる。 $n \neq 4$ であり、$a \geqq 2$ であるから、$a \geqq 3$ である。 ここで、$a$ と $2a$ の大きさを比較する。 $a \geqq 3$ のとき、$a^2 - 2a = a(a - 2) \geqq 3 \cdot 1 = 3 > 0$ であるから、

$$ 2a < a^2 $$

が成り立つ。すなわち、$2a \leqq a^2 - 1 = n - 1$ である。 また、$a \geqq 3$ より $a < 2a$ であるから、$a$ と $2a$ は $n-1$ 以下の相異なる自然数である。 したがって、$(n-1)!$ の積の中には $a$ と $2a$ が因数として含まれる。

$$ (n-1)! = 1 \cdot 2 \cdots a \cdots 2a \cdots (n-1) $$

よって、$(n-1)!$ は $a \cdot 2a = 2a^2 = 2n$ の倍数となる。 とくに、$(n-1)!$ は $n$ の倍数であるから、$(n-1)!$ は $n$ で割り切れる。

（i）, （ii） のいずれの場合も $(n-1)!$ は $n$ で割り切れる。 以上より、$n$ が素数でなくかつ $4$ でもないとき、$(n-1)!$ は $n$ で割り切れる。

解説

階乗と素数・合成数の関係を問う、整数分野における非常に有名なテーマの証明問題である。 合成数 $n$ の場合、$(n-1)!$ が $n$ を因数として含むかどうかは、$n$ を構成する約数が $(n-1)!$ の中に互いに異なる数として存在するかどうかが鍵となる。 特に $n=p^2$ （$p$ は素数）の形をした平方数の場合、$p$ が2つ必要になるため、積の中に $p$ と $2p$ が存在できるかどうかの確認が必要になる。ここで $n=4$ （$a=2$ のとき）だけは $2a = 4 > n-1$ となってしまい、$2a$ が階乗の積に含まれないため例外となる。この例外性が(1)と(2)の条件の違いとして現れている。

答え

(1)

$(4-1)! = 6$ は $4$ で割り切れず、$n$ が素数のときは $(n-1)!$ の素因数に $n$ が含まれないため割り切れないことを示した。 (2)

$n$ を $ab$ ($2 \leqq a \leqq b$) とし、$a \neq b$ のときと $a = b$ ($a \geqq 3$) のときに場合分けし、いずれも $(n-1)!$ の積の中に因数として $a, b$ （または $a, 2a$）が含まれることから $n$ で割り切れることを示した。