数学ナビゲーター掲示板

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

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

■46659 / inTopicNo.1)  素数
  
□投稿者/ 大蛇 一般人(1回)-(2015/01/09(Fri) 17:58:05)
    pを素数とすると、2^p-1の素因数は全てpより大きいことを示せ。

    教えて下さい。
引用返信/返信 [メール受信/OFF] 削除キー/
■46660 / inTopicNo.2)  Re[1]: 素数
□投稿者/ WIZ 一般人(7回)-(2015/01/09(Fri) 18:57:12)
    2015/01/09(Fri) 18:58:02 編集(投稿者)

    qを(2^p)-1の素因数とすると、(2^p)-1 ≡ 0 (mod q)です。
    qは素数ですからフェルマーの小定理より、pはq-1の倍数でなくてはなりません。
    1 ≦ q-1 < pと仮定すると、pより小さいpの正の約数は1のみですので、
    q-1 = 1よりq = 2となりますが、(2^p)-1は奇数ですのでq = 2を因数として持ち得ません。
    よって、1 ≦ q-1 < pという仮定が誤りであって、p ≦ q-1つまり、p < qであると言えます。
引用返信/返信 [メール受信/OFF] 削除キー/
■46661 / inTopicNo.3)  Re[2]: 素数
□投稿者/ 大蛇 一般人(2回)-(2015/01/09(Fri) 20:56:53)
    ありがとうございます。

    すみません、
    > pはq-1の倍数でなくてはなりません。
    ここがよくわからないのですが…
引用返信/返信 [メール受信/OFF] 削除キー/
■46662 / inTopicNo.4)  Re[1]: 素数
□投稿者/ WIZ 一般人(8回)-(2015/01/09(Fri) 22:26:50)
    「フェルマーの小定理」というキーワードで調べれば多分分かると思いますが、
    自然数の素数qに対して、aをqと互いに素な整数とすると、
    a^1, a^2, a^3, ・・・, a^(q-1)は全て法qで非合同で、特に
    a^(q-1) ≡ 1 (mod q)
    が成立するという定理です。

    上記を使うとnを自然数としてa^n ≡ 1 (mod q)ならばnはq-1の倍数と言えます。
    何故なら、nをq-1で割った商をs, 余りをr、但し0 ≦ r < q-1とすると、
    a^n = a^{s(q-1)+r} = {(a^(q-1))^s}{a^r} ≡ {1^s}{a^r} = a^r (mod q)
    もし、0 < r < q-1とすれば、q-1より小さい自然数rで、a^r ≡ 1 (mod q)となり、
    フェルマーの小定理に反しますので、r = 0となることが必要です。
    よって、n = s(q-1)となります。
引用返信/返信 [メール受信/OFF] 削除キー/
■46663 / inTopicNo.5)  Re[2]: 素数
□投稿者/ 大蛇 一般人(3回)-(2015/01/09(Fri) 22:31:50)
    > 上記を使うとnを自然数としてa^n ≡ 1 (mod q)ならばnはq-1の倍数と言えます。

    a=3, n=3, q=13 としたら
    3^3 ≡ 1 (mod 13)
    ですけど、3は13の倍数じゃないですよね?
引用返信/返信 [メール受信/OFF] 削除キー/
■46664 / inTopicNo.6)  Re[3]: 素数
□投稿者/ 大蛇 一般人(4回)-(2015/01/09(Fri) 22:33:57)
    すみません、訂正です。

    3は13の倍数じゃないですよね?

    3は12の倍数じゃないですよね?
引用返信/返信 [メール受信/OFF] 削除キー/
■46665 / inTopicNo.7)  Re[1]: 素数
□投稿者/ WIZ 一般人(9回)-(2015/01/10(Sat) 00:51:37)
    スレ主さんの仰る通りですね。
    「a^1, a^2, a^3, ・・・, a^(q-1)は全て法qで非合同」になるのは
    aが法qの原始根の場合だけですね。

    pが2を原始根として持つ素数ならば私の提示した方法で説明できてるけど、
    それ以外の素数はアウトですね!

    よって、私の書き込みは無視してください。申し訳ありません。
引用返信/返信 [メール受信/OFF] 削除キー/
■46667 / inTopicNo.8)  Re[1]: 素数
□投稿者/ みずき 一般人(16回)-(2015/01/10(Sat) 02:35:07)
    次のようにできると思います。

    qを2^p -1の任意の素因数とすると、2^p≡1 (mod q)。
    ここで、集合Uを
    U={n|nは正の整数で、2^n -1が素因数qで割り切れる}
    で定め、Uの中で最小な正の整数をeとする。

    ここで次の命題を証明する。
    「Uの任意の元をmとするとき、mがeで割り切れる」
    (命題の証明)
    mがeで割り切れないと仮定する。
    mをeで割ったときの商をs、余りをrとするとm=es+r(0<r<e)と表せる。
    このとき2^r≡2^r*1≡2^r*{(2^e)^s}≡2^(es+r)≡2^m≡1 (mod q)
    だから、2^r -1はqで割り切れる。
    0<r<eだから、rはeより小さなUの要素となるが、これはeの最小性に反する。
    従って、仮定が誤りで、mはeで割り切れる。
    (命題の証明終了)

    2^p≡1 (mod q)と命題によりpはeで割り切れるから、eはpの約数。
    pは素数だから、e=1,pのいずれか。
    e=1とすると、2-1=1がqで割り切れることになり不合理なので、e=p。
    2^p -1は奇数だから、qは奇素数。よって、2とqは互いに素だから、
    フェルマーの小定理より、2^(q-1)≡1 (mod q)が言えて、
    命題によりq-1はe=pで割り切れる。
    よって、p≦q-1なので、p<qが言えました。
引用返信/返信 [メール受信/OFF] 削除キー/
■46668 / inTopicNo.9)  Re[1]: 素数
□投稿者/ WIZ 一般人(10回)-(2015/01/10(Sat) 04:33:48)
    スレ汚し申し訳ありません。

    自然数aが素数qと互いに素な場合、ある自然数eが存在して
    a^e ≡ 1 (mod q) (フェルマーの小定理の系(カーマイケルの定理?))
    となります。eはq-1の約数となりますので、1 ≦ e ≦ q-1です。
    e = 1となるのはa = 1の場合だけですので、a = 2ならば1 < e ≦ q-1となります。

    q ≦ pつまりq-1 < pと仮定すると、1 < e < pです。
    ここで2^p ≡ 1 (mod q)ならばpはeの倍数となり、これはpが素数であることに反します。
    よって、q ≦ pは不可能です。
引用返信/返信 [メール受信/OFF] 削除キー/
■46688 / inTopicNo.10)  Re[2]: 素数
□投稿者/ 大蛇 一般人(6回)-(2015/01/14(Wed) 07:51:17)
    ありがとうございました。
引用返信/返信 [メール受信/OFF] 削除キー/
■47842 / inTopicNo.11)  素数の勉強会します
□投稿者/ Tommy. P.N. 一般人(1回)-(2016/12/24(Sat) 02:48:57)
http://youtu.be/WNyZwjk5KCw
    http://youtu.be/WNyZwjk5KCw
    突然ですが、今週日曜日に素数の勉強会を開催します。
    素数の好きな方歓迎します。
    ヨロシクお願い致します。
引用返信/返信 [メール受信/OFF] 削除キー/



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

このトピックに書きこむ

Mode/  Pass/

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

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