- ベストアンサー
素数の問題
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
質問の意図が分からないんですが、 「強帰納法」(この言葉は初めて聞きました。)と、 帰納法は同値なので、実は全然「強」くないですね。 強帰納法⇒帰納法は明らかで、 帰納法⇒強帰納法は、 命題A(n)：「n以下の全ての値で成り立つ。」とすれば nについての帰納法は強帰納法になります。 つまり、この問題についていえば、 命題A(n)：「n以下の全ての値で素因数分解できる。」 とすれば、nについての帰納法で証明できます。 「n以下の全ての値で」というところを命題の中に 置くかそうでないかの違いだけです。
関連するQ&A
- 帰納法と背理法の注意点について
「nを正整数とする。(2^n) + 1は１５で割り切れないことを示せ。」という問題です。 解答は帰納法で解くのではなく、nを具体化していくと１５で割ったあまりが3,5,9,2・・・のパターンで推移していくのを証明すればいい問題なのですが、これに対して私は帰納法と背理法をミックスして以下のように解こうと思ったのですがだめですか。 (2^n) + 1は１５で割り切れると仮定し、それを帰納法で表す。 n=1のとき3となり15で割り切れない。 n=kのとき１５で割り切れると仮定する。つまり (2^k) + 1=15m ⇔2^k=15m-1・・・(1)が成り立つと仮定する。 (1)より (2^k+1)=2(15m-1) =15・2m - 2 となり矛盾する。よって(2^n) + 1は１５で割り切れない・・・(終） どこかおかしそうな気がするのですが、結論として帰納法は帰納法単独でしか使えないのでしょうか。この問題は帰納法単独だけでは「(2^n) + 1は１５で割ると１３余る数ではない」ということしか証明できないので困ります。 よろしくおねがいします。
- ベストアンサー
- 数学・算数
- 証明の問題です
「nを自然数とする。nが３の倍数の時2^nを７で割ったあまりは１であることを示せ。」という問題なのですが、解答では「n=3mとして、等比数列和の公式より(8^m) - 1 =7(8^m-1 + 8^m-2 + 8^m-3 ・・・・・・・・+1)＝7・(整数) から2^nを７で割ったあまりは１である」としているのですが、これに対して帰納法で証明してもよいのでしょうか。というか帰納法のほうが自然な気がしますが。 (8^m)について m=1のとき8=7・１ + 1より成立 m=kのとき７で割って1余る数と仮定する。つまり(8^k)=7m+1とする。 m=k+1のとき8^k+1=8(8^k) =8(7m+1) =7(8m+1) + 1 より m=k+1のときも成立。 以上の結果よりnが３の倍数の時2^nを７で割ったあまりは１である・・・（終）
- ベストアンサー
- 数学・算数
- 数学的帰納法でこの問題に詰まっています
連続したｋ個の整数の積はｋ！で割り切れることを数学的帰納法で証明せよ。 という問題です。数学的帰納法というからには、ｎやｎ+1を使うのだと思うのですがよくわかりません。どなたか解法と解答をお願いします。
- ベストアンサー
- 数学・算数
- 『3^x=5を満たすxは無理数』の証明（※数IIの内容）
『3^x=5を満たすxは無理数であることを示せ。』の証明問題を解いています。 解答での疑問があるのですが、 僕は塾には行っておらず、５連休で学校にも行けないので、利用させてもらいます。 載っている解答（一部）は以下です。 3^x=5を満たす有理数xが存在すると仮定する。 3^x=5>1であるから、x>0である。・・・（★） ゆえに、x=m/n（m、nは正の整数）と表せる。 よって、3^m=5^n これを満たすm、nの値はないから、有理数xは存在しない。 ・ ・ ・ と続いていくのですが、（★）の部分は必要でしょうか。 言い換えると、 x>0を言わずに、x=m/n（m、nは整数かつn≠0 ⇒有理数の定義）として、 証明を進めていっても、3^m=5^nを満たすm、nは存在しないのではないでしょうか。 また、これを満たす整数m、n（n≠0）があるのであれば、教えてください。 整数の範囲で考えると、m=0、n=0の場合がありますが、 これも、x=m/n=0/0となるので、xの値は存在しないですよね？ 自分でもいろいろ考えてみましたが、これくらいしか出てきません・・・ わかる方いましたら、教えてください。
- ベストアンサー
- 数学・算数
- 関数の問題
関数gは任意の非負整数mに関して以下の性質を持ちます。 g(2m)=g(g(m)) g(2m+1)=g(2m)+1 例えば、もしg(0)=0なら、g(k)は任意の非負整数ｋに対して非負整数の値を返します。（これは数学的帰納法で証明できます） しかしながら、もしg(0)=１とすると、関数ｇは矛盾をはらむのでg(0)は１に等しくならないことが分かります。（これも比較的簡単に証明できます） また同様に任意の非負整数ｋに対して、g(0)=2^k としたり、g(0)=2^k + 2 としたりすると、矛盾を導きます。 それでは、どのような非負整数にg(0)が等しければ、関数gは矛盾をはらまずに任意の非負整数ｋに対してg(k)が非負整数の値を返すでしょうか。 もし何かそのようなg(0)の値に決まった性質があったら教えてください。
- 締切済み
- 数学・算数
- 素数の判定
自然数Nが√Nを越えない最大の整数以下のすべての素数で割り切れなければ、Nは素数である。 この定理の証明について、わからないことがあるので質問します。本の証明では√Nを越えない最大の整数をnとし、Nがnより大きい素数qで割り切れたとすると、そのときの商をpとして、N=pqである。ここで1<p≦n＜q<Nに注意すると、 pが素数ならNは素数pで割り切れるはずだし、pが合成数ならNはpの素因数で割り切れていたはずであり、いずれにしても不合理である。証明終わり。 自分は不合理を示す証明は、背理法を使っていると思ったのですが、その場合自然数Nが素数でないと仮定して証明を始めると思いました。しかし√Nを越えない最大の整数をnとし、Nがnより大きい素数qで割り切れたとすると、という仮定で始まっています。また√Nを越えない最大の整数をnとし、Nがnより大きい素数q以外では割り切れないとすると、という文章の解釈でよいのかと思いましたが、はたして正しい証明なのか疑問が残りました。最後に対偶をとってそれを背理法で証明しているのかと思いました、対偶は、Nが素数でないならば、√Nを越えない最大の整数をnとし、Nはn以下の素数いずれかで割り切れる。ですが、これを背理法で証明しようとすると、 Nはn以下の素数いずれかで割り切れない、という仮定から始まるとおもいました。本の証明の書き出しと違いました。自分で考えた方針では、本の証明とだいぶ違います。 だれか本に書かれた証明で、pで割り切れると何が不合理なのかと、自分の証明の方針のまちがいを指摘してください、お願いします。
- ベストアンサー
- 数学・算数
- 素数は無限
質問２点。 １． 「素数は無限に存在する」証明をwikipediaで調べると、 背理法で素数が無数にあることを証明した、 素数の積に1を加えた数が素数であることを証明した」などの誤解をする者がいるが、 いずれも正しくない と書かれています。 wikipediaが常に真実とは限りませんが、 Google検索で素数の無限である証明で検索すると、上記の誤解している人による解説ばかりです。 何を（どちらを）信じればよいか分からずに困っています。 ２． wikipediaによる正しい証明によると、、、 素数の個数が有限と仮定し、p1, … pn が素数の全てとする。その積 P = p1 × … × pn に 1 を加えた数 P + 1 は、p1, …, pn のいずれでも割り切れないので、素数でなければならない。しかし、これは p1, …, pn が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無数に存在する。 これは、背理法による証明だと思うのですが、、、、 お手数ですが、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素数の問題（場合の数）
nが整数のとき、多項式n^3-10n^2-84n+840で表すことのできる素数はいくつあるか？ 因数分解すると(n+2√21)(n-2√21)(n-10) と３つの積なりますが、( )の中身がみな違うので１*１*(なんとか)の3数の積で表すのは無理がある、と考えているで解き方の突破口が開けま せん。また、ルートがある( )の部分はnが整数なので３つの積が素数 になる、というのも納得がいきません。。 もしかしたら因数分解そのものが間違っていたり、解答の指針そのものが 間違っているかもしれませんが、この問題が解ける方、何通りあるのか教えてくれませんか？！
- ベストアンサー
- 数学・算数
お礼
遅くなって申し訳ありません． 命題は同じで２通りの解き方をしなければ ならないと思っていたので，この質問をさせて もらったのですが，ibm_111さんが教えてくだ さったとおりでした．ありがとうございました．