数学ナビゲーター掲示板

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

[ 最新記事及び返信フォームをトピックトップへ ]

■52802 / inTopicNo.1) 　最大公約数
  ▼■
□投稿者/ すき家のねずみ 一般人(1回)-(2025/04/04(Fri) 18:08:03)
    mを2以上の自然数とするとき
    2^m-2, 3^m-3, 4^m-4, 5^m-5, 6^m-6, 7^m-7, …
    の最大公約数ってどう求めるのでしょうか？
引用返信/返信 [メール受信/OFF] 削除キー/
■52805 / inTopicNo.2) 　Re[1]: 最大公約数
□投稿者/ らすかる 一般人(13回)-(2025/04/05(Sat) 14:06:56)
    求め方はわかりませんが、
    2^m-2,3^m-3,4^m-4,…の最大公約数は
    「m-1がp-1で割り切れる」を満たす素数pの積
    となるようです。
    具体的には、m=2,3,4,5,6,7,8,9,10,11,12,13,14,…に対して
    最大公約数は2,6,2,30,2,42,2,30,2,66,2,2730,2,…のようになります。
    ↓参考
    oeis.org/A027760

引用返信/返信 [メール受信/OFF] 削除キー/
■52822 / inTopicNo.3) 　Re[2]: 最大公約数
□投稿者/ すき家のねずみ 一般人(2回)-(2025/04/19(Sat) 09:45:03)
    とても参考になりましたありがとうございます。
    偶数の場合ですら難しいですね。
解決済み!
引用返信/返信 [メール受信/OFF] 削除キー/
■52826 / inTopicNo.4) 　Re[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] 削除キー/
■52841 / inTopicNo.5) 　Re[2]: 最大公約数
□投稿者/ すき家のねずみ 一般人(3回)-(2025/04/30(Wed) 16:28:33)
    ありがとうございます。
    難しいですが、なんとなく雰囲気は分かりました。
解決済み!
引用返信/返信 [メール受信/OFF] 削除キー/


トピック内ページ移動 / << 0 >>

このトピックに書きこむ
Mode/　 Pass/

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

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