【気づけば一瞬?!】難問だけど面白い整数問題【九州大学 2015】

Рет қаралды 81,647

Күн бұрын

Пікірлер: 104

@cafe_rumba 3 жыл бұрын

k ≧ 3の整数のとき、2^k + 1と2^k - 1が互いに素であることを背理法で証明する。 2^k + 1と2^k - 1が互いに素でないと仮定する。このとき、2^k + 1と2^k - 1には2以上の公約数があり、それをgとおく。 2^k + 1 = ga, 2^k - 1 = gb(a, b:自然数)とおける。 2^k = ga - 1 = gb + 1よりg(a - b) = 2 ... (1) g, a, b:自然数かつg ≧ 2より(1)を満たすg, a, bの組は(g, a - b) = (2, 1)のみ。このとき2^k - 1 = 2bとなるが、左辺は奇数、右辺は偶数より矛盾。よって2^k + 1と2^k - 1が互いに素でないと仮定したことが誤りであるから証明終。

@10d1102022l 3 жыл бұрын

8:00 (2^k+1)(2^k-1)=9p のときの 2^k+1 と 2^k-1 の値の組の絞り方として，差が2になることから (9p,1)や(3p,3)は排除できるのでk>=3の条件がなくても奇数でさえあれば十分かと思います．宿題の解答 2^k+1 と 2^k-1の差が2なので最大公約数は2の約数(1か2)であり，kが自然数のときはどちらも奇数なので2は約数に持たないので，互いに素

@黒なすび 3 жыл бұрын

今日東大模試があって、日頃スバルさんの授業見てたおかげで整数問題完答できました！

@makimurasame7271 Жыл бұрын

ユークリッドの互除法と使うと2^k+1と2^k-1の最大公約数は2^k-1と2の最大公約数になる。2^k-1は奇数なので最大公約数は1になる。つまり互いに素

@福山浩範-y1i Жыл бұрын

「整数問題の３大解法」の例題として、最適な問題ですね❗ この問題を何度も復習するだけでも、実力が付きそうです。

@ぽち-s6q 3 жыл бұрын

個人的に素数と見たら2は最初にわけて考えることにしている

@yasu..... 9 ай бұрын

自分は、3もです。今年の九大整数でてほしい

@たんめん-p8n 9 ай бұрын

@@yasu..... くそ易化したなふざけた問題ばっかだったわ

@fclfc1039 3 жыл бұрын

q=3確定させたらグラフ書いて明らかに交点1つ、右辺の大きくなる速度がめちゃくちゃ大きいのでpに小さい順で素数入れていけばp=7で確定

@user-bj2yr3iq7t Жыл бұрын

なにそれおもしろい！

@イカバチ 3 жыл бұрын

2^(p-1)-1=pq^2……(☆) (☆)の左辺は奇数であるから、右辺も奇数となるので、p≠2,q≠2 よって、p-1は偶数となり、p-1=2k(kは自然数)とおける。したがって、 (☆)⇔2^2k-1=(2k+1)q^2 ⇔(2^k+1)(2^k-1)=(2k+1)q^2 ここで、2^k+1>2^k-1であることに注意すると、 (2^k+1,2^k-1)=((2k+1)q^2,1)……① =((2k+1)q,q)……② =(2k+1,q^2)……③ =(q^2,2k+1)……④ の4通りの組の可能性が考えられる。 ①の時、2^k-1=1より、k=1 このとき、2^k+1=3,(2k+1)q^2=3q^2 となり、これらが等しいので、 3q^2=3 ∴q=1 (∵q>0) しかし、これはqが素数であるという条件を満たしてないので不適。 ②の時、(2^k+1)-(2^k-1)=2であるから、(2k+1)q-q=2kq=2 しかし、q≧3であるから、この等式は成立しない。 ③の時、2^k+1=2k+1⇔2^k=2k……❇︎ ここで、関数f(x)=2^x-2xについて、 x≧3のとき、 f'(x)=(2^x/log2)-2>2^x-2≧2^3-2=6>0 より、f(x)はx≧3において単調に増加するので、x≧3の時、f(x)=2^x-2x≧2^3-2×3=2>0 よって、❇︎が成り立つのは、k=1,2の時のみである。 k=1の時、q^2=2^1-1=1、ゆえにq=1となるが、これはqが素数であることに反する。 k=2の時、q^2=2^2-1=3となるが、これを満たすqは存在しないので不適。 ④の時、2^k-1=2k+1……❇︎❇︎ k=1,2のとき、この等式は成り立たない。ここで関数g(x)=2^x-2x-2について、 x≧4の時、 g'(x)=(2^x/log2)-2>2^x-2≧14>0であるから、x≧4において、g(x)は単調に増加するので、g(x)=2^x-2x-2≧16-8-2=6>0 となる。したがって、k≧4の時、❇︎❇︎は成り立たない。また、k=3のとき、2^3-1=7 2×3+1=7となり、 ❇︎❇︎を満たす。よって、以上の議論より、k=3 となり、p=2×3+1=7 (これはpが素数であるという条件を満たしている。) このとき、q^2=2^3+1=9 ∴q=3(∵q>0) これはqが素数であるという条件を満たしており、さらに、p≠qである。 ∴求めるp,qの組は(p,q)=(7,3)………（答）

@samurai9363 3 жыл бұрын

大学入学して数学科でもないのにまだ見てます、、今となっては数学が趣味になってる

@opopo_dog 3 жыл бұрын

自分も一緒です！数学科入りたいとすら思ってます…

@ハンチョウ-p9j 3 жыл бұрын

か！ら！み！ざ！か！り！

@Pel_L 3 жыл бұрын

めっちゃ分かります！！ PASSLABOさんの整数動画がきっかけで今では数学科目指してます…( ⑉¯ ꇴ ¯⑉ )

@佐々木とりあえず 3 жыл бұрын

@@ハンチョウ-p9j 最高傑作ですよね

@ペン-f6p 3 жыл бұрын

これ今日解いたやつだ！問題集に載ってるのは導入付きだったけど、mod3mod4利用は導入なしでも解きたいところ

@石垣太郎-n9x 4 ай бұрын

一年前の自分は歯が立たなかったけど、今はすらすら解けるようになったの嬉しい。ちなみに自分はmod4でやりました

@yoooooshi152 Жыл бұрын

まさかの定期テストでそのままでて完答出来ました。本当にありがとうございます！

@hamacchochannel 7 ай бұрын

定期テストでこれ出すの驚愕

@ktsn1130 3 жыл бұрын

10:08 2^k-1と2^+1との差は2であることと、2数の最大公約数が仮にあるとすれば奇数にしかならないことが矛盾するので、2数は互いに素

@キノコ-v3o 3 жыл бұрын

初めに互いに素でないことを仮定しなければ矛盾するかなど判断することはできません。

@名無し-d7m5n 3 жыл бұрын

差が2だから、ユークリッドの互除法から最大公約数の候補的に2、1しかないから証明できてるように思うけどなぁ

@はる-z6p9b Жыл бұрын

差が2まで言えたら互いに素であることまで言わなくても、他の組だと明らかに差が2以上になるから、9とp の差が2であるものだけ考える方が楽だと思う

@mh35jp 6 ай бұрын

2^(p-1)-1は、p≧2の自然数の時、必ず奇数になる。したがって、右辺は奇数でなければならない。よって、p,qは奇数である次に、p≧3の奇数の時、2^(p-1)-1≡0(mod3)なので、pq^2も当然3の倍数でなければならない以上から、p=3もしくはq=3の少なくとも一方が成り立つ p=3の時、左辺=3、右辺=3q^2となり、q=1となるが、1は素数ではないため不適上記からq=3となるから、2^(p-1)-1=9p p=5の時、左辺=15、右辺=45となり不適 p=7の時、左辺=63、右辺=63となり適す p=11の時、左辺=1023、右辺=99となり不適 p=n(n≧11)の時、左辺>右辺とする。この時、p=n+1の時は、左辺が1024以上増加するのに対し右辺は9しか増加しないので、左辺>右辺が成り立つ。よって、p≧11ではあり得ない以上から、(p, q)=(7, 3)が唯一解である

@hirokimorita9153 6 ай бұрын

意外と、誘導のせいでわからなくなる場合もあるね。

@のえるん-y1y 4 ай бұрын

全然わかんない動画のテンポが早すぎても良くないな

@gamedaisukionce 3 жыл бұрын

フェルマーの小定理が浮かんだ

@command_tntoriginal9307 3 ай бұрын

同じくなんかいい解き方ないかな？

@大学受験特化-g2t 2 ай бұрын

⁠@@command_tntoriginal9307 ないと思います。フェルマーの小定理が (以下p,qは素数) 「2^(p-1)-1=p×nとなる自然数nが(必ず)存在する」であるのに対して今回の問は「2^(p-1)-1=p×q^2となる(p,q)を求めよ」であり、この問においてフェルマーの小定理にできることといえば言うなれば「q^2とも表せるかもしれない因数nが存在する」を示すことしかできません。今回は具体的にqを求める必要があるので、フェルマーの小定理はあまり有用ではないと考えられます。

@大学受験特化-g2t 2 ай бұрын

例えるなら、「ある条件Aを満たす人(そのような人をaとする)が、この世に必ず存在します」とする定理が手元にあったとしても、「そのaさんが条件Bを満たすとき、aさんは誰ですか？」という問には効力を持たないということです。

@ベスースラリン 5 ай бұрын

限界まで自然数を突き詰めると身に付きますね

@はる-z6p9b Жыл бұрын

7:23 (2^k+1)と(2^k-1)差が2だからp≧3であることを考慮してpと9の差が2であることが必要って絞る方が楽じゃないですか？

@2チャント Жыл бұрын

互いに素与えられたらもっと簡単になりますね

@カインなのよ-t5g 3 жыл бұрын

二項定理で2の偶数乗が3を法として1になることがわかるから、両辺は3の倍数になるがPが3の倍数つまり、P＝3のとき式は成り立たない。 2^P-1－1＝9P これを満たすものをP＝2.5.7と確認すると P＝7は満たすから、あとはP≧11のときに 2^P-1－1＞9P を帰納法で示すっていうのを考えてました

@ハル-f4e 3 жыл бұрын

細かいことをいうと左辺が2の因数をもっていないので、p=2は調べなくても良いですね😃

@epin9071 Жыл бұрын

良問ルート2日目フェルマーの小定理に縛られて何も出来なかった、、、😢

@kino785 3 ай бұрын

良かった暗算だったけど合ってた

@Lebes_Gue 3 жыл бұрын

ユークリッドの互除法で互いに素は示せそうですけどね～曖昧とか言われたら何も言えねぇ

@転結起承-y7o 3 жыл бұрын

2^(p-1)-1=9p まで行った後、p=7で成立してるのは分かってたからそれ以外にないと、数学的帰納法でゴリ押してしまった

@user-bj2yr3iq7t Жыл бұрын

どうやって示すんですか？教えてくださいー！

@user-zabifxaxb 6 ай бұрын

@@user-bj2yr3iq7t今更意味無いかもしれないけど、f(p)=2^p-1 -1-9pを考える。微分すると単調増加だと分かるから、解は1つ。文系だったら申し訳ない

@クリより凜功 3 жыл бұрын

おかげで整数問題に抵抗少なくなりました！！

@lcja7827 3 жыл бұрын

これ本番の時に解いた問題ですが、誘導を使って完答した覚えがあります。誘導無しだとmod3に気づかなくてこんなに難しかったっけってレベルになりますw。

@lcja7827 3 жыл бұрын

この時浪人してたのですが整数(mod等)、複素数平面はこの年から導入、行列が削除って時で、modを扱う問題は過去問に無く(誘導つきでmodを知らなくても解ける問題はありましたが)何を出されるか分からないって状態だった覚えがあります。

@ナルシソ家ペス Ай бұрын

気づけば一瞬と書いてあったから解けたけど九大にはオーバースペックです

@りか-x8i 3 жыл бұрын

準備できる時間あれば鉄壁の続きが見たいです🥺

@yamashitamizuki 2 жыл бұрын

美しい

@potatox2931 3 жыл бұрын

ユークリッドの互除法により2^k+1と2^k-1の最大公約数は2^k-1と2の最大公約数と等しいので互いに素と示せます！

@overcapacitywhale 3 жыл бұрын

pが5以上なら左辺が3の倍数なのでqが3の倍数→q=3 で解きました

@だっち-v2j 3 жыл бұрын

駿台の夏期講習！

@キノコ-v3o 3 жыл бұрын

mod、絞り込みなど使わずに完答できた。

@xxshibata3734 3 жыл бұрын

分かりやすい！ｗｗ

@ハル-f4e 3 жыл бұрын

6:33 私はここから関数で攻めました。f(x)=2^x-1,g(x)=9x+1を考えて、かたや指数関数かたや直線なのでpがある数値を越えると等号になることはないということでp>7でf(x)>g(x)を数学的帰納法で証明しました。いかがですか！？

@くまきち-g7v 3 жыл бұрын

その方が自然でしょう。なぜ指数と多項式が等号で結ばれている違和感を無視して因数分解しようとしたのか、むしろ疑問。(元の問題の誘導に流されたか？) 最初の方も、とつぜん偶奇で場合分け考え始める解説は謎すぎる。(mod 3で考えた末で、なら分かる。)

@なおT-k1m 3 жыл бұрын

さすがです。自分は高校で数学教えていますので参考にします。記述模試や大学の過去問の解説の時にかなり参考になります。

@atama.ga.torinosu Жыл бұрын

良問ルート2日目

@a._shu 3 жыл бұрын

高一現在、完答しました！

@まるまる-p5c2v 3 жыл бұрын

指数→a^2-b^2 平方数→mod3,mod4 って感じでまとめていいですか

@ターザン-b5f 3 жыл бұрын

実験の段階で合同式は考えれるようになったらいいかもですね。思わぬ解法がみちびきだされることもちらほらあります。でもやっぱり圧倒的にmod3,4がおおいですけどねw

@アセチルコリン-u1m 3 жыл бұрын

平方数はmod4よりmod8の方が美味しいことが屢々あるから知っておくと得

@まるまる-p5c2v 3 жыл бұрын

なるほどありがとうございます

@ETeppei 3 жыл бұрын

宿題：xとx+1が互いに素であるってのと同じですよね。

@r.kgalaxy7389 3 жыл бұрын

なんか感動しましたw

@勉強頑張るマン-k1j 3 жыл бұрын

実験で使った数字で条件絞るのか〜なるほど〜🧐

@道徳倫理 7 ай бұрын

解けたけど30分もかかってしまった

@INAKENinaken 3 жыл бұрын

九大は良問が多い

@らら-n9m 3 жыл бұрын

mod知らないけど理系大学いけたな。運が良かった

@レゼ推し-l1d Жыл бұрын

風呂場で解いた

@和泉大空-i1m 3 жыл бұрын

この問題、S塾のH大数学にあったなぁ

@半炒飯-h3k 3 жыл бұрын

行きの電車の10分間で解けたからうれしい

@ヘキサメチレンジアミン-b3g 3 жыл бұрын

共通テスト模試の前に河合とかZ会の共通テスト対策の本はやった方がいいのでしょうか？

@新井賢介 3 жыл бұрын

フェルマーの小定理じゃいけん？

@だいだい-f9x3w 3 жыл бұрын

岡山大学みたいです

@はこしん-t2t 3 жыл бұрын

この前の数検の整数問題でmod使えたから一瞬で倒せたの嬉しかった(大学生)

@ゴロゴロ素人 3 жыл бұрын

4:31 「もっど」

@ゴロゴロ素人 3 жыл бұрын

これ誘導

@らいひ-h1y 3 жыл бұрын

去年10月の東進北大模試で同じようなやつやってまったく手でなかったな〜

@kai-wo5ik 3 жыл бұрын

7と3かなってやったら当たった

@53matu7 3 жыл бұрын

初見でp=2k+1っておけるか？

@53matu7 2 жыл бұрын

@てるてるそういうことか！整数の問題の知識少ないでもっと入れなあかん

@ten4558 3 жыл бұрын

九大！！

@ぴえーんぴえん-i4q 3 жыл бұрын

なんか例えがでんがんのやつみたいだなぁ

@awake2455 3 жыл бұрын

オイラーの小定理使えそうと思ったけどどうだろう

@xiang0519 3 жыл бұрын

フェルマーじゃないですか？自分もそれで出来ないかなぁと直感的に思ったんですが…

@awake2455 3 жыл бұрын

@@xiang0519 ｱｯｽﾐﾏｾﾝﾃﾞｼﾀ

@Gold_bahha 3 жыл бұрын

mod3の匂いがする

@悠_ハル-d6k 3 жыл бұрын

誰か詳しい方添削お願いします！ (与式)⇔2^p-1=pq^2+1より左辺が偶数より右辺が偶数が必要。したがってp≠2、q≠2 ここで(右辺)≧5*3^2+1=46 よって2^p-1≧46 ∴p≧7 pは奇数よりp-1は偶数だから (与式)⇔{2^(p-1)/2 -1}{2^(p-1)/2 +1}=pq^2 よって{2^(p-1)/2 -1,2^(p-1)/2 +1}=(1,pq^2)(q,pq)(p,q^2)(q^2,p)(∵2^(p-1)/2 -1

@田中太郎-t6v5f 3 жыл бұрын

@仮面rider受験 2以外の素数で最小値をとるのはこの組だからね。このやり方で範囲で絞る時には最大値か最小値しかいらない。

@wc3722 3 жыл бұрын

こういう数学系の動画おもろいんだけどコメ欄がなぁ小学生、中学生ならできた事喜んでコメ欄に書き込んじゃうのは分かるけど

@かめやまむー 3 жыл бұрын

まあまあ、可愛いもんじゃない

@低-c1b 3 жыл бұрын

mod3 で瞬殺した

@ねむ祈り 3 жыл бұрын

互いに素の証明って言ったら、ねぇ、あの方法しか

@ランボルギーニ-c8u 3 жыл бұрын

どれ

@ox6303 3 жыл бұрын

次のように解いてみました． 2^(p-1)-1≡1(mod 2)であるから、pq^2≡1(mod 2)ゆえpもqもともに奇素数である． p-1は偶数であるから、 2^(p-1)-1=pq^2 ↔︎[ 2^{ ( p-1 )/2 }+1 ][ 2^{ ( p-1 )/2 }-1 ]=pq^2 …(＊) 2^{ ( p-1 )/2 }+1 > 2^{ ( p-1 )/2 }-1≧1 より、(＊)から ( 2^{ ( p-1 )/2 }+1 , 2^{ ( p-1 )/2 }-1 ) = ( pq^2 , 1) or ( pq , q ) or ( p ,q^2 ) or ( q^2 , p ) ⅰ) ( 2^{ ( p-1 )/2 }+1 , 2^{ ( p-1 )/2 }-1 ) = ( pq^2 , 1) のとき　2^{ ( p-1 )/2 }-1=1 ↔︎p=3 　このときq=1となり、不適である． ⅱ) ( 2^{ ( p-1 )/2 }+1 , 2^{ ( p-1 )/2 }-1 ) = (pq , q ) のとき　2^{ ( p-1 )/2 }+1=pq…① ，2^{ ( p-1 )/2 }-1=q…② とする．①-②より　2=(p-1)q となり、p-1=2 (∵p,qは奇素数)となるが、q=1 となり不適である． ⅲ) ( 2^{ ( p-1 )/2 }+1 , 2^{ ( p-1 )/2 }-1 ) = ( p ,q^2 ) のとき　 2^{ ( p-1 )/2 }+1=p…(ア) ，2^{ ( p-1 )/2 }-1=q^2…(イ) とする．　(ア)を満たすpを求める．ここで、f(x)=2^{ ( x-1 )/2 }-x+1 とすると f‘(x)=2{ (x-3)/2 }log2-1 である．　f’(x)≧0とすると　　　2{ (x-3)/2 }log2 ≧ 1 　　　　　　　　　　　2{ (x-3)/2 } ≧ 1/( log2 ) (∵log2>0) 　　　　　　　　　　log[2] 2{ (x-3)/2 } ≧ log[2] 1/( log2 ) = - log[2](log2) 　　　　　　　　　　　　　　(x-3)/2 ≧ - log[2](log2) 　　　　　　　　　∴ x≧ - 2log[2](log2)+3 　となる．ここで、log(√e)=1/2であり、√e ( p であるから、　 (ア)を満たす奇素数pがあるならばそれはp=3 or 5 である．p=3 のときも p=5 のときも(ア)は成り立つが、p=3,5 のとき(イ)を満たす奇素数qは存在しない． ⅳ) ( 2^{ ( p-1 )/2 }+1 , 2^{ ( p-1 )/2 }-1 ) = ( q^2 , p ) のとき　 2^{ ( p-1 )/2 }+1=q^2…(あ) ，2^{ ( p-1 )/2 }-1=p…(い) とする．　 (い)を満たす奇素数pを求める．ここでg(x)=2^{ ( x-1 )/2 }-x-1 とおくと g(x)=f(x)-2となるから、g(x)もf(x)同様 x≧6 で　単調増加である．これにより、p≧9 のとき g(p) ≧ g(9) ↔︎ 2^{ ( p-1 )/2 }-p-1≧6>0 ．　よってp≧9 ならば 2^{ ( p-1 )/2 }-1> p であるから、(い)を満たす奇素数pがあるならばそれは p= 3 or 5 or 7 である．　このうち(い)を満たすのは p=7 のみであり、このとき(あ)から奇素数qを求めると q=3 である．　以上 ⅰ)~ⅳ) より、求める素数の組 ( p , q ) は ( 7 , 3 ) である．…(答)