＃7 良問日誌〜2016 東工大④〜

東工大の問題だから数Ⅲで文系の自分には関係ないと思った人がいるかもしれないが、整数問題であるため文系範囲です。東工大の中ではかなり簡単な問題なので最後まで見ていってください！
問題はこちら


$${ n }$$ を $${ 2 }$$ 以上の自然数とする.
(1)$${ n }$$ が素数または $${ 4 }$$ のとき, $${ (n - 1)! }$$ は $${ n }$$ で割り切れないことを示せ.
(2) $${ n }$$ が素数でなくかつ $${ 4 }$$ でもないとき,$${ (n - 1)! }$$ は $${ n }$$ で割り切れることを示せ.

2016 東工大 第4問

前回の＃6 良問日誌とおなじで〇〇で割り切れないという問題です。

前回の記事で〇〇で割り切れるか？と聞かれたら $${ \mod 〇〇 }$$ を思い浮かべると言いましたが、今回は関係ないです。個人的には $${ \mod }$$ 使わない時の方が多い気がするので、前回の補足的な感じでこの問題を扱ってます。

(1)は実際に確かめてみるだけです。
(2) 「素数でない数」というのをどう表すかが重要です。素数でない数、つまり合成数は2つ以上の素数の積なので、
$${ n = 2^a + 3^b + 5^c + ... }$$
と表せますが、これじゃあキリがないです。素直に
$${ n = ab (a < b) }$$ ,
$${ n = a^2 (a = b) }$$
とおきましょう。
今回は少し工夫してみました。条件が強い方が扱いやすいことが多いです。(今回はそこまで変わりませんでした)

---

解答

(1) $${ n }$$ が素数のとき、 $${ n = p ( p は素数) }$$ とおけ、
$${ (p - 1)! }$$ は $${ p }$$ を因数に含まないため、$${ n }$$ が素数のとき、$${ (n - 1)! }$$ は $${ n }$$ で割り切れない。
$${ n = 4 }$$ のとき、$${ (4 - 1)! = 6 }$$ は $${ 4 }$$ で割り切れない。
よって、$${ n }$$ が素数または $${ 4 }$$ のとき, $${ (n - 1)! }$$ は $${ n }$$ で割り切れない。

(2) 下画像参照

質問等あればコメントまで。