数学ナビゲーター掲示板 [One Message View / Re[1]: 最大公約数]

数学ナビゲーター掲示板

■52826 / 1階層)

　最大公約数

□投稿者/ WIZ 一般人(5回)-(2025/04/25(Fri) 14:00:43)

# 解決済みになってるけど、解けた気がするので投稿しちゃいます!

べき乗演算子^は四則演算子より優先度が高いものとします。

{2^m-2, 3^m-3, 4^m-4, 5^m-5, 6^m-6, 7^m-7, …}の最大公約数をg(m)とします。
nを2以上の自然数とすれば、n^m-nは偶数なので、mの値に関わらずg(m)は2を因数に持ちます。

(1)mが偶数の場合
q = g(m)/2とおくと、qは自然数です。
g(m) = 2qは2^m-2 = 2(2^(m-1)-1)の約数なので、qは2^(m-1)-1の約数となります。
2^(m-1)-1は奇数なので、qも奇数となります。

qが素因数を持つと仮定し、その素因数のひとつをpとします。pは奇素数となります。
2からp-1までの自然数の中には法pの原始根が存在するので、原始根のひとつをaとします。
pはa^m-a = a(a^(m-1)-1)の約数となりますが、2 ≦ a ≦ p-1なので、pはa^(m-1)-1の約数となります。

a^(m-1)-1 ≡ 0 (mod p) つまり、a^(m-1) ≡ 1 (mod p)ならば、
フェルマーの小定理とaが法pの原始根であることから、m-1はp-1の倍数でなければなりません。

m-1は奇数で、p-1は偶数なので、m-1はp-1の倍数にはなり得ません。
よって、奇数qの素因数pが存在しないので、q = 1であり、g(m) = 2といえます。

(2)mが奇数の場合
g(m)が素因数pを持つと仮定します。(p = 2も含みます。)
つまり、nを2以上の自然数とするとき、n^m-n = n(n^(m-1)-1)はpを約数に持つと仮定します。

nとn^(m-1)-1は互いに素ですから、仮定の成立には以下の2通りの場合があります。
(2A) n ≡ 0 (mod p)
(2B) n^(m-1)-1 ≡ 0 (mod p)

nが法pで0に合同である場合、これは(2A)の成立そのものです。
nが法pで0に合同でない場合、nが法pの原始根である可能性もあることから、
(2B)の成立はフェルマーの小定理より、m-1がp-1の倍数であることが必要となります。

従って、nが法pで0に合同であるかないかに関わらず、m-1がp-1の倍数であれば、
n^m-nはpを約数に持ち、pはg(m)の因数であるといえます。

更に、p^m-p = p(p^(m-1)-1)がp^2で割り切れないため、p^2はg(m)の因数とはなり得ないといえます。
以上から、g(m) = Π{m-1がp-1の倍数である素数p}となります。
上記g(m)をmの式で表せるのかは分かりませんでした。

記事引用 [メール受信/OFF] 削除キー/

上記関連ツリー
前の記事(元になった記事)	次の記事(この記事の返信)
←最大公約数 /すき家のねずみ	→Re[2]: 最大公約数 /すき家のねずみ
最大公約数 / すき家のねずみ (25/04/04(Fri) 18:08) #52802
`├` Re[1]: 最大公約数 / らすかる (25/04/05(Sat) 14:06) #52805
`│└` Re[2]: 最大公約数 / すき家のねずみ (25/04/19(Sat) 09:45) #52822 解決済み!
`└` 最大公約数 / WIZ (25/04/25(Fri) 14:00) #52826 ←Now
`└` Re[2]: 最大公約数 / すき家のねずみ (25/04/30(Wed) 16:28) #52841 解決済み!
上記ツリーを一括表示 / 上記ツリーをトピック表示
上記の記事へ返信

入力内容にタグは利用できません。

数式の記述方法
TeX入力ができます。 \[ TeX形式数式 \]　あるいは，$ TeX形式数式 $　で数式を記述します。
　TeX形式数式には半角英数字のみです。詳しくは、ここを見てください。
Titleは質問の内容がわかりやすいように書いてください。
他人を中傷する記事は管理者の判断で予告無く削除されます。
半角カナは使用しないでください。文字化けの原因になります。
名前、Title、コメントは必須記入項目です。記入漏れはエラーになります。
入力内容の一部は、次回投稿時の手間を省くためブラウザに記録されます。
削除キーを覚えておくと、自分の記事の編集・削除ができます。
URLは自動的にリンクされます。
引用返信するときは不要な引用部分を削除してください。
記事中に No*** のように書くとその記事にリンクされます(No は半角英字/*** は半角数字)。
- No123 → 記事No123の記事リンクになります(指定表示)。
- No123,130,134 → 記事No123/130/134 の記事リンクになります(複数表示)。
- No123-130 → 記事No123～130 の記事リンクになります(連続表示)。

Name	/
E-Mail	/
└> 関連するレス記事をメールで受信しますか? / アドレス
Title	/
URL	/
Comment/ 通常モード->　図表モード-> (適当に改行して下さい/半角10000文字以内) ■No52826に返信(WIZさんの記事) > # 解決済みになってるけど、解けた気がするので投稿しちゃいます! > > べき乗演算子^は四則演算子より優先度が高いものとします。 > > {2^m-2, 3^m-3, 4^m-4, 5^m-5, 6^m-6, 7^m-7, …}の最大公約数をg(m)とします。 > nを2以上の自然数とすれば、n^m-nは偶数なので、mの値に関わらずg(m)は2を因数に持ちます。 > > (1)mが偶数の場合 > q = g(m)/2とおくと、qは自然数です。 > g(m) = 2qは2^m-2 = 2(2^(m-1)-1)の約数なので、qは2^(m-1)-1の約数となります。 > 2^(m-1)-1は奇数なので、qも奇数となります。 > > qが素因数を持つと仮定し、その素因数のひとつをpとします。pは奇素数となります。 > 2からp-1までの自然数の中には法pの原始根が存在するので、原始根のひとつをaとします。 > pはa^m-a = a(a^(m-1)-1)の約数となりますが、2 ≦ a ≦ p-1なので、pはa^(m-1)-1の約数となります。 > > a^(m-1)-1 ≡ 0 (mod p) つまり、a^(m-1) ≡ 1 (mod p)ならば、 > フェルマーの小定理とaが法pの原始根であることから、m-1はp-1の倍数でなければなりません。 > > m-1は奇数で、p-1は偶数なので、m-1はp-1の倍数にはなり得ません。 > よって、奇数qの素因数pが存在しないので、q = 1であり、g(m) = 2といえます。 > > (2)mが奇数の場合 > g(m)が素因数pを持つと仮定します。(p = 2も含みます。) > つまり、nを2以上の自然数とするとき、n^m-n = n(n^(m-1)-1)はpを約数に持つと仮定します。 > > nとn^(m-1)-1は互いに素ですから、仮定の成立には以下の2通りの場合があります。 > (2A) n ≡ 0 (mod p) > (2B) n^(m-1)-1 ≡ 0 (mod p) > > nが法pで0に合同である場合、これは(2A)の成立そのものです。 > nが法pで0に合同でない場合、nが法pの原始根である可能性もあることから、 > (2B)の成立はフェルマーの小定理より、m-1がp-1の倍数であることが必要となります。 > > 従って、nが法pで0に合同であるかないかに関わらず、m-1がp-1の倍数であれば、 > n^m-nはpを約数に持ち、pはg(m)の因数であるといえます。 > > 更に、p^m-p = p(p^(m-1)-1)がp^2で割り切れないため、p^2はg(m)の因数とはなり得ないといえます。 > 以上から、g(m) = Π{m-1がp-1の倍数である素数p}となります。 > 上記g(m)をmの式で表せるのかは分かりませんでした。
File	/ アップ可能拡張子=> /.gif/.jpg/.jpeg/.png/.txt/.lzh/.zip/.mid/.svg 1) 太字の拡張子は画像として認識されます。 2) 画像は初期状態で縮小サイズ250×250ピクセル以下で表示されます。 3) 同名ファイルがある、またはファイル名が不適切な場合、　　ファイル名が自動変更されます。 4) アップ可能ファイルサイズは1回200KB(1KB=1024Bytes)までです。 5) ファイルアップ時はプレビューは利用できません。 6) スレッド内の合計ファイルサイズ:[0/500KB] 残り:[500KB]
Icon	/ (画像を選択/サンプル一覧)
削除キー	/ (半角8文字以内)
解決済み! BOX/ 解決したらチェックしてください!
プレビュー/

- Child Tree -
Edit By 数学ナビゲーター