数学ナビゲーター掲示板

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

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

■52356 / inTopicNo.1) 　(x+1)^n-x^n
  ▼■
□投稿者/ plan:D 一般人(1回)-(2023/10/10(Tue) 20:20:47)
    nは3以上の奇数で、pはnを割り切る素数のうち最小のものとする。
    このとき、任意の整数xに対して(x+1)^n-x^nはpで割り切れない、
    というのは正しいでしょうか？
    反例か証明を教えてほしいです。よろしくお願いします。
引用返信/返信 [メール受信/OFF] 削除キー/
■52366 / inTopicNo.2) 　Re[1]: (x+1)^n-x^n
□投稿者/ WIZ 一般人(6回)-(2023/10/14(Sat) 22:36:21)
    # 証明できたような気がしますが、あまり自信がないので識者の方のツッコミをお願いします。

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

    x ≡ 0 (mod p)または、x+1 ≡ 0 (mod p)つまりx ≡ -1 (mod p)の場合、
    (x+1)^n-x^nがpで割り切れないことは容易に分かるので、
    以下でxは法pで0にも-1にも合同でない整数とします。

    xの法pで(剰余体Z/pZで)の逆元をyとします。つまりxy ≡ 1 (mod p)です。
    xは法pで0に合同ではないので、このようなyは必ず存在し、剰余類としては唯一に定まります。
    また、yも法pで0に合同ではありません。
    更に、xは法pで-1に合同ではないのと、-1の逆元は-1であることから、yは-1に合同ではありません。
    # 合同でない2つの剰余類の逆元同志も合同にはならない為。

    (x+1)^n-x^n = rとおくと、
    ⇒ (y(x+1))^n-(yx)^n ≡ (y^n)r (mod p)
    ⇒ (1+y)^n-1 ≡ (y^n)r (mod p)
    つまり、r ≡ 0 (mod p)であることと、(1+y)^n ≡ 1 (mod p)であることは同値です。

    yは法pで0にも-1にも合同ではないので、1+yは法pで1にも0にも合同ではありません。
    よって、1 < m ≦ p-1である自然数mが存在して、(1+y)^m ≡ 1 (mod p)となります。
    尚、mは(1+y)^m ≡ 1 (mod p)を満たす最小の自然数とします。
    # 上記はフェルマーの小定理の応用で、mはp-1の約数となります。

    (1+y)^n ≡ 1 (mod p)であるためにはnがmの倍数であることが必要です。
    しかし、nの最小因数がpであり、1 < m < pであるため、nはmで割り切れません。

    以上から、(1+y)^n ≡ 1 (mod p)であることは不可能であり、
    (x+1)^n-x^n = r ≡ 0 (mod p)であることも不可能と言えます。
引用返信/返信 [メール受信/OFF] 削除キー/


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

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

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

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