【予想の証明】


mを正の整数とします。mと互いに素な任意の正整数kを定めた時、
(m^n-1)がkで割り切れるような正の整数nが必ず存在する…、と予想しました。

※「m^n」とは、mのn乗の事とします。

これは正しいですか?
自分でも証明してみたんですが、いまいち信じられないので…

・もし正しければ(この予想が定理ならば)、

 イ. 勉強不足でお恥ずかしいですが、この定理はありふれたものですか?
    もしそうなら定理の名称や証明した人の名前を教えてください。

 ロ. 私の証明は除算の余りに鳩の巣原理を適用したものですが、
    それ以外の証明法があれば、教えてください。

・もし正しくなければ、

 ハ. 反例を教えてください。

回答の条件
  • 1人1回まで
  • 登録:2010/06/10 21:04:36
  • 終了:2010/06/11 06:42:53

ベストアンサー

id:akagi_paon No.4

akagi_paon回答回数143ベストアンサー獲得回数132010/06/11 01:26:10

ポイント60pt

オイラーの定理

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Euler...

オイラーは n がオイラー関数で表せることまで示してますね。

しかも証明も簡単。

オイラーすげえ。マジぱねえ。

id:kuro-yo

ありがとうございます。

まさしくこれです。

(…俺、不勉強すぎるorz)

2010/06/11 06:40:55

その他の回答(3件)

id:ecp No.1

ecp回答回数1ベストアンサー獲得回数02010/06/10 22:28:36

ポイント10pt

おそらく、「ハ」 なのではないかと思います。

m = 2 のとき、成り立たなそうです。


m = 2 のとき

m と互いに素な任意の数 k は必ず奇数である。


n = 1 のとき m ^ (n - 1) = 2 ^ (1 - 1) = 1 である。

これは 1 のみで割り切れるが、 k > 1 なのでNG


n > 2 のとき、m ^ (n - 1) は 2以外の素因数を含まない。

k は必ず奇数なので、k では割り切れないためNG

※ k に何を掛けても、2以外の素因数を含んでしまう


m = 2 のとき、全ての n において条件を満たす k は存在しない。

つまり、どのように k を選んでも条件を満たす n は存在しない。


となります。

自信ないですが、多分間違っていないと思います。。

id:kuro-yo

ごめんなさい、勘違いされているようですが、

「m^(n-1)」

ではなく、

「m^n-1」

ですよ。

2010/06/10 22:59:54
id:wsx-1234 No.2

natu~BZG~回答回数18ベストアンサー獲得回数02010/06/10 22:44:13

そういうのは大人の私でもわかりませんよ??

id:kuro-yo

わかる範囲で結構ですよ。

2010/06/10 23:01:28
id:rsc96074 No.3

rsc回答回数4394ベストアンサー獲得回数4022010/06/10 23:18:14

ポイント20pt

 m^n-1=(m-1){m^(n-1)+m^(n-2)+・・・+m+1}と因数分解できるから割り切れる、じゃ駄目でしょうか。(^_^;

 mをxに変えると、x^n-1。これなら、見覚えあるはず。(^_^;

●TETRA'S MATH | 因数分解から等比数列へ

http://math.artet.net/?eid=845803

id:kuro-yo

本質的には、その右側の因数がkで割り切れるようにnを決定できるかという問題なのですが…

できれば、コメント欄で補足していただけないでしょうか。

2010/06/10 23:29:01
id:akagi_paon No.4

akagi_paon回答回数143ベストアンサー獲得回数132010/06/11 01:26:10ここでベストアンサー

ポイント60pt

オイラーの定理

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Euler...

オイラーは n がオイラー関数で表せることまで示してますね。

しかも証明も簡単。

オイラーすげえ。マジぱねえ。

id:kuro-yo

ありがとうございます。

まさしくこれです。

(…俺、不勉強すぎるorz)

2010/06/11 06:40:55
  • id:kuro-yo
    補足:k>1、m>1です。
  • id:rsc96074
    k=(m-1)、または、{m^(n-1)+m^(n-2)+・・・+m+1}と選べばいいと思っていましたが、もしかして、はじめに、mとkを決めて、それに対するnが存在するかという意味ですか?早とちりしたようです。やっぱり、奥が深かったのですね。(^_^;
  • id:T_SKG
    p を素数,xをpで割り切れない整数とする。 このとき,x^(p-1)-1はpで割り切れる。

    という、「フェルマーの小定理」の変形版のような気がします、でも、本日は、頭が働きません。
    コメントで失礼。
  • id:rsc96074
     フェルマーの小定理、使えそうですね。ちょっと試しにやってみました。(^_^;
    ●フェルマーの小定理
    >>
    p を素数とし、a を p の倍数でない整数(a と p は互いに素)とするときに、
    a^(p-1)≡1 (mod p)
    <<
    http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86

     上記定理にて、a=m,p=kと置くと、
    m^(k-1)≡1 (mod k)
    が成り立つ。
    ∴m^(k-1)-1≡0 (mod k)
     よって、mとk(m と k は互いに素)を任意に決めれば、n=k-1と決まる。
  • id:kuro-yo
    > フェルマーの小定理

    あっ、確かにそうですよね。全然気付いてませんでした。orz
  • id:kuro-yo
    そっかー、オイラーの定理ってこれの事かぁ。自分の不勉強を露呈しただけの恥ずかしい質問になってしまった。
    また出直してきます。
  • id:kuro-yo
    続きの質問を登録しました。
    http://q.hatena.ne.jp/1277238070

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません