素数の証明 有名問題（一橋大後期）
Вставка
- Опубліковано 4 лип 2021
- 素数の証明は「背理法」と「対偶」
整数問題の全パターンでもこの手の証明はあるので
類題の演習にぜひどうぞ！
整数問題の全パターン解説はこちら
• 【整数問題】入試頻出解法を”４時間で”全パタ...
PASSLABOの数学特化チャンネル開講です！！
MathLABO〜東大発！「みんなで作る」数学ベスト良問集
ということで、TwitterやLINE、UA-camのコメントなどで
現在進行形で視聴者さんから頂いた良問やリクエストを中心に解説していきます。
数学関連のLIVEやPASSLABOではできないようなことも、リクエストも見ながらどんどん実験していきますので、ぜひみんなで一緒に楽しみましょう！
~~~~~~~~
■MathLABO〜東大発！「みんなでつくる」数学ベスト良問集〜
チャンネル登録はこちらから
→ / @mathlabo
■解説して欲しい良問を見つけた方はこちらまで
→ lin.ee/v9sRM5r
（勉強法や質問相談はLINE LIVEにて配信予定!!）
■解答解説のノート画像は公式Twitterから
→ / todai_igakubu
リクエストや企画はこちらから募集してます！
forms.gle/hYKGAnRz5jhgxjQo8
======
【君のコメントが、動画に反映されるかも！】
問題の解説希望やリクエストあれば、好きなだけ載せてください。
１つ１つチェックして、役立つものは動画にしていきますね^ ^
===========
■PASSLABOメンバー情報
「１」宇佐見すばる
→ / todai_igakubu
→ note.mu/pfsbr123/n/nb6fe7782cef8
「２」くまたん
東大文一１点落ち？/PASSLABO癒しキャラ
→ / passlabo3
→ note.mu/pfsbr123/n/n429b06b1d9b4
===========
#MathLABO
#みんなでつくる数学良問集
#リクエストは概要欄から
朝６時に毎日投稿！
一緒に動画で朝活しよう
![Kyoto University's famous integer problem [Instant kill with technique].](http://i.ytimg.com/vi/QZMmqpuufcg/mqdefault.jpg)
面白いし、タメになるし、わかりやすい、最高
さずがに一橋大学は良問が多いですね。私は大学工学部卒業なので😊答えはわかりましたが、解説がまたまた面白直ぐにくつい二度見しました。
実例を挙げてくださり、有難う御座います。
高校の時、逆、裏、対偶に関して、あまり、
詳しく習っていなかったので勉強になります。
定石や場合分けなどが凄く判りやすかったです。
合成数というのもこのチャンネルで初めて知りましたが、楽しかったです。
引き続き、よろしくお願い申し上げます。
問題文で「aが自然数」という条件が抜けている。この条件がないと、aが素数以外でも「2^a - 1 が素数」を満たす a が無数に存在し、問題文の命題自体が偽になってしまう。
また、単に「aが整数」と示されている場合は、素数でないというのは1の他に0や負数も忘れてはいけない。
素数は2以上の自然数でしか定義されないから問題ないのでは？
@@taiyo9274 「2^a - 1 が素数ならば」のところで a について何も言及されていない。
実際の試験問題では、おそらく「a が自然数」という条件が記されていたと思う。
だから、仮定のところで a についての条件が抜けているのはNG。結論の「a は素数である」のところでその結論が真か否かは確定していない（証明されていない）ので、a が自然数かどうかなんて議論する余地なし。
例えば、「円周率は素数でない」という命題は真。
@@shhi9379 a=log3/log2あたりが反例になりますね
よく分からんけど別にaを満たす値がいくつあっても良いのでは？
そのaが素数かどうかを知りたいのであって、
aが素数でなくても問題は無いんだし。
成る程なるほど・・・学ぶねエ‼️
対偶証明の得手不得手は本当に数学学習全体に大きな影響を及ぼしますね。
まぁ一言で言ってしまえば集合と論理という地味で高校生には軽視されやすい、論理おばけみたいな単元の内容にある程度通じておくといいです。
別コメントにも書きましたが、それが情報の世界でも基礎となりますし、集合論は大学では集合と位相という単元を通じて解析学と幾何学の基礎へと発展します。
最近、朝起きてこのチャンネル見るのが日課になりつつある……数学って面白いなやっぱり
今日からUA-camこのチャンネルしか見ないわ、面白すぎる
2017年の佐賀大理工後期の３番がまさにこれでした
a=pq・・・①とすると、nが素数ならば
「p=1またはq=1」・・・②
2^p≡1 (mod 2^p-1)
2^pq≡1 (mod 2^p-1)
①より、2^a≡1 (mod 2^p-1)
2^a-1=素数⇒2^p-1=1または2^p-1=2^a-1
よってp=1,a
①より、(p,q)=(1,a)(a,1)
②を満たす。
よって、aは素数
という解き方もありですか?
メルセンヌ素数ですね
一橋受ける人だと完答したい一問ですね
ありがとござます！！
今年の京大も似たような問題ありましたね。
青字で「か1」と書かれた瞬間崩れ落ちました。忘れてました。PASSLABOでもやってたのに・・・。
x^n - 1 = (x - 1) (x^n-1 + x^n-2 + ... +1) という公式を知らないと解けない解法ですね。
別解どうでしょうか。
n = bk と置くところまでは同じとして
2^b に着目し、m = 2^b - 1 と置くと、2^b ≡ 1 (mod m) である。
合同式の性質から、2^b ≡ 1 (mod m) なら、任意の x ∋ N について 2^bx ≡ 1 (mod m) が成立する。
よって a^n = a^bk ≡ 1 (mod m)
すなわち a^n - 1 ≡ 0 (mod m) 、つまりa^n - 1 は m で割り切れるため素数ではない。
nが素数ではない→a^n - 1 が素数ではないことが示されたため、対偶により元の命題が証明される。
(n =1 とか細かい部分は省略しました)
備忘録70G" 【 背理法 】
a ∈自然数, 2ª －1＝ (素数) ･･･① のとき、a が素数でないと仮定する。
( ⅰ ) a＝ 1 のとき、( ①の左辺 )＝ 2¹ －1＝ 1 となって ①に 矛盾する。
( ⅱ ) a＝ (合成数) のとき、 a＝ b･k ( b, k ∈2 以上の自然数 ) と表せる。
( ①の左辺 )＝ { (2^b) －1 }・{ (2^b)^k-1 ＋ ･･･ ＋ (2^b)¹ ＋1 }
これの 右辺の二つの因数は、共に 2 以上 となって ①に矛盾する。
以上より、何れにしても仮定は誤りである。 よって、a は素数である。■
【 急所 】
a＝ (合成数) のとき、
a＝ b･k
( b, k ∈2 以上の自然数 ) と表すことができる。
へえ。そういうことになってるって、初めて気づきました。いい問題ですね。
対偶を考える。aが素数でないとすると、aが少なくとも2つの因数b, cの積で表せて、
a=bc (b>1, c>1)とする。
このとき2^b=Bとおくと、
2^a-1=2^(bc)-1=B^c-1=(B-1)(B^(c-1)+B^(c-2)+...+B^2+B+1)
と表せて、ここでb>1よりB=2^b>2なので、B-1と(B^(c-1)+B^(c-2)+...+B^2+B+1)が
ともに1より大きい因数になる。aが素数でないと、2^a-1も素数でないと言える。
2^n-1って、なんで素数になるんだろう？
x^n-1=(x-1)(x^(n-1)+x^(n-2)+...+x^2+x+1)って因数分解できるから
素数にならなそうなのに・・・と思ったら、
「x=2のとき、x-1=1になるので、因数になってなかったんだ！」
と気づくので、そしたら解ける感じでした。
a=1のときは省略してんの？
おぉ、ご指摘ありがとうございます。
2^1-1=1だなとは思ったので、省略と言えば省略ですが、
＞対偶を考える。aが素数でないとすると、aが少なくとも2つの因数b, cの積で表せて、
＞a=bc (b>1, c>1)とする。
としているので、「a=1は対象範囲外である」と宣言してしまっていて、
要は「気付いてませんでした」ってことです。正しくは、
＞aが素数でないとすると、aが1であるか、少なくとも2つの因数b, cの積で表せて、
＞その場合a=bc (b>1, c>1)とする。
とすべき、ということですね。なるほどです。勉強になりました。
ほぼ、今年の京大の大問6やん。
東大でよく出る通過領域の問題など良ければ扱ってほしいです！
この問題の(3)も解説動画上げてほしいです。
体調大丈夫ですか？
フェルマーの小定理
それでどうやって証明するつもりなんでしょうか？
２進法で表すと、
(2^bk)-1は
111111111111（１がbk個並んでいる）
(2^b)-1は、
111111（１がb個並んでいる）
っていうのを私は途中で使いました
申し訳ないのですが、2進法をどのように利用しているのか教えていただけないでしょうか
@@user-zw4xf3zx9k
たとえば、b=3、k=4、bk=12のとき、
(2^bk)-1は2進法で、111111111111（１が１２個）です
(2^b)-1は2進法で、111（１が３個）です
111111111111は111×1001001001となります。
このように、割と直感的にbkが合成数の時（b≧2,k≧2の時）
(2^bk)-1＝(2^b)-1×（２以上の整数）っていうことがわかります。
記述の時は、１１１・・・・１１１って書いて下に｝を横にして１がbk個並んでいる、だとか書くのかなって思います。
@@user-cq3gp7mb4z なるほど、理解できました。わざわざありがとうございます。
証明はわかったのですが、最初の3秒で何と言っているのか何度聞いてもわからない。
ほかの分野の問題もあげて欲しい
動画投稿から１年後の書き込みで今更ではありますが、対偶をとる動機づけを私なりに書いてみます。
aが素数であることの定義が、aが1またはa以外の約数を持たないという数量的に不特定多数を扱うから、仮定も結論も不特定多数について言っていることになる。複雑。
対偶をとると、特定の約数（動画ではbと2^b-1に相当）についての条件になるので単純になる。
any の否定はexists
一階述語論理の考え方が隠れている。
ありがとうございます
おかげで完全数についての証明が書けそうです
感覚的な話になりますが2^aはaより複雑ですね。単純なものをもとに複雑なものを計算する方が楽かと思います。
nからのn^2みたいな。
そういう考えのもとだとaから先に考えたい、→を逆にしたい、そう考えられると待遇が思いつきやすいと思います。
夏休み中に青チャートで基礎固め頑張ります😱
三年生ですか？
同じくレジェンドで
@@user-qb2ux1xn4z 高二です(_ _)
３年以外は帰れ！(号泣
メルセンヌ素数ですね。名前を思い出すとき大体ドイツの某自動車ブランドを経由してしまいます()
完全数においても重要な数字ですね。
「ならば」の後ろがシンプルだったから対偶は思いついたけど「1」の存在を忘れてましたあああああ
a=log2 3
おおっ！？すげぇ～！
これどうなんの？
「素数の反対」という用語はおかしい。
素数でないもの、あるいは素数であることの逆と言うべきでは。
このセンセ、数学用語の使い方がしょっちゅうおかしい。数学用語は正確に使わないと減点されるでしょ。
対偶証明法がはやそうだなぁ。
P⇒Qっていう命題の証明の時には、待遇を考えてみるのはよくある……けどサムネ見る限り前提条件のaの指定の範囲は書いてないしなぁなんて考えました。(aはどの元？自然数全体？整数全体？有理数全体？実数全体？)
⇒aは素数であることを示せ
の部分からaが自然数であることは明らかでは無いでしょうか？
@@user-jd5ib6ji9q
いいえ。
他の人も指摘してますが、a=log(2)3のときは偽になります。
@@kiichiokada9973 確かにそうですね。すみませんでした。でもまぁ高校数学の話で、なおかつ入試問題なのである程度の忖度は必要かなと個人的には思います。
まぁ大学以降の深い数学を学ばれた方からすると定義不十分で気持ち悪く感じるのは必然とも思います😅
実際の入試問題には「a,bを正の整数とする」と入っているからセーフ
悪いのはこの人
1忘れてました😅
自分ならフェルマーの小定理証明してから、２を代入する（アホ）
おはようございます！29日目！
証明って手順だけだからアルゴリズムと整理できないかなあ？実験をする。素数であるコトを証明する。背理法・対偶で手順化する。素数でないなら素数でない。合成数か１である。
因数分解ってアルゴリズムだよね！
合成数である！ 5/20 点の配分 →アルゴリズムの価値観の方が広がりがあるよ！
たいぐう
2^bk-1=(2^b-1)(正の整数)のところ、因数分解すると自明ですが「正の整数の方も1でない」と断っておかないとダメかと思いましたがどうでしょうか。
それに代えて2^a-1>2^b-1を言ってるんだと思う
文系でこのレベルは特筆すべき。一橋出身は別格扱いすべきかも。
されてる
一対一対応って青チャートの難易度どの辺りですか？
北大九大神戸大には一対一対応いりますか？
二項定理使えないかなー
最近受けた某数学の試験にでたなぁ
2^bk-1=(2^b-1)×(正の整数)になる理由をどなたか教えていただけませんか？
メルセンヌ素数
黒茶におんなじ問題あった貴ガス
2進表記するとほぼ自明
くそー、最初2進表記で考えたのに、自明ってところまで
行きつきませんでした・・・残念。
自明って言われたら、分かりました。なるほど。
2進表記は出来ましたが、どうして自明となるのかが分かりません。
説明をお願い出来ますでしょうか。
せっかく分かったので、ご説明しようか、それとも岸部緑さん
にお任せしようかと思ったところでしたが、下の方の(古い？)
コメントを見ると、黒鉛燐 さんのコメントのところで、説明され
ていました。
自明かどうかは、2^a-1のaが2進数の桁数になることと、2進数
の繰り上がりのない掛け算を自明と思うかどうか、ですね。
スラロード
それぞれを二進数にしたものを掛け算の形に直して証明するんですね！
納得しました。教えていただきありがとうございます。
2^a-1が素数となる例を示さなくてもよいのですか？
「6aが素数ならば、aは素数」みたいなものも成り立ってしまうので
仮定が偽ならばその命題は真になるので
成り立ちますよ
p⇒q ⇔ p (否定)またはq
数学の論理と自然言語の感覚はしばしば解離します。
たとえば次の文章をあなたはどう解釈しますか？
「自然数Aは2と5以外の素因数を持ちません。」
多くの人は2^a×5^b(a,bは自然数)という形の数を思い浮かべるでしょうか。
あるいは、少し頭が数学的な人でもaかbのうちいずれかは自然数と考えるでしょう。
しかし数学では字句通り(「含み」を読み取らずに)文言を解釈しますから、実は1、つまりa=b=0でもAの条件を満たす数と考えるのです。
ただ、そのような解釈を日常会話でしたらたぶん対人関係がうまくいかず、嫌われてしまいますよね。
数学の日本語と自然言語の日本語は違う。そして数学の日本語(数学語)は「論理値(真偽値)が一致する限り真偽が一致する」、つまり「論理値」によって裏から支配されていると心得てください。
だから情報の世界には普通の人々が使う「または」のニュアンスに近づけた「exclusive or(排他的「または」)」なんてオプションもある訳です。
たとえば、「ランチにはサラダとコーヒーまたは紅茶が付きます」といえば、(ソフトドリンクがおかわりし放題の、有明ガーデンのフライデーズのような高級レストランを除き)「では、先にサラダとコーヒーと、食後に紅茶をお願いします！」とは言えない訳で、これなんかはまさに、現実におけるexclusive orの好例です。
合成数代入すると3の倍数にならんかな
それはaが偶数の時だけですね。a=9とかだったら2^a-1=2^9-1=511となって3の倍数になりません。
その着眼点は良いと思いますよ！
@@user-ih1wq3fb7w そうですね…有難うございます！
ちなみに「aが素数のとき、(2^a)-1は素数」は偽
意外と扱われない証明法だから高校2.3年生は忘れがちですよね。p⇒qのqの方が使いやすい条件のときは疑うべきですね。あと、コメントで2進数使っている人多かったですが、自分は気づかなかったので、おぉ！ってなりましたw
「aは整数である」の一文がないから「a = lb 3 のとき成り立たない。よって命題は偽。」
なにそれ
「aが整数では無い」ときは、命題の十分条件「2^a - 1 が素数ならば」をそもそも満たさないので、命題が偽とは言えない
a=log₂6
@@MJun21 aが整数でなくとも「2^a-1が素数」となることはあります。
具体例：a=log[2]3
確かに「aは整数とする」という文言は必要ですね。
@@user-bo2qk2sb7q たしかに
これできないと解けない問題が医科歯科であった