4n－1の形の自然数は、必ず4m－1の形の素因数があることを証明せよ。 という問題が分かりません。

4n－1の形の自然数は、必ず4m－1の形の素因数があることを証明せよ。

という問題が分かりません。
教えていただけると幸いです。

No.1 ベストアンサー 回答者： ありものがたり 回答日時： 2020/05/17 23:15

これも、背理法でできますよ。

4n-1 の素因数分解を考えます。
各素因数を 4 で割った余りを考えると、
素因数は 2, 4m-1, 4m+1 の形の 3種類に分類されます。
4m-2, 4m+2 (m≠0) は、素因数 2 を持つので、素数ではありません。
4n-1 は奇数です。4n-1 と 2 の最大公約数は 1 なので、
2 は 4n-1 の素因数にはなりません。
よって、4n-1 の素因数は全て 4m-1 か 4m+1 の形をしています。

それが全て 4m+1 のタイプだと仮定すると
4n-1 = (4m₁+1)(4m₂+1)...(4mₓ+1) となるはずですが、
この左辺を 4 で割った余りは -1,
右辺を 4 で割った余りは +1 なので、式は成り立ちません。
よって背理法により(以下同文