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

九州大学の数学は標準的で良問多めです。
今回完答できなかった方はこちらをぜひ！
↓整数問題の全パターン解説↓
• 【整数問題】入試頻出解法を”４時間で”全パタ...
今日のパスチャレはこちら↓
note.com/pfsbr123
~~~~~~~~
■ 東大現役合格→トップ成績で医学部に進学した僕の超戦略的勉強法
（宇佐見天彗＋PASSLABO著）
amzn.to/2FOboO3
全国の書店でもご購入いただけます。
■ 早期購入者特典受け取りフォーム（2020年10月24日まで）
forms.gle/hENMLjpHi9E6tdeUA
↑
このフォームからしか受け取れません。
お手元に書籍が届いてからご記入ください。
■サイン本プレゼント企画
（2020年10月3日まで）
todai_igakubu/sta...
■試し読みはこちら
todai_igakubu/sta...
~~~~~~~~~~~~~~~~
■東大医学部発「朝１０分」の受験勉強cafe
PASSLABOのチャンネル登録
→ / @passlabo
■東大生たちと一緒に勉強したい方必見！
公式LINE@登録はコチラから
→ line.me/R/ti/p/@subaru_todai
（勉強法や質問相談はLINE LIVEにて配信予定!!）
======
【君のコメントが、動画に反映されるかも！】
問題の解説希望やリクエストあれば、好きなだけ載せてください。
１つ１つチェックして、役立つものは動画にしていきますね^ ^
======
■偏差値43から東大合格までの勉強法がまとめて知りたい方
→ amzn.to/2GRW3tL
■公式Twitterはコチラ
→ / todai_igakubu
===========
■PASSLABOメンバー情報（note）
＊気になるメンバーのnoteをチェック!!
「１」宇佐見すばる
東大医学部 / PASSLABO室長
→ note.mu/pfsbr123/n/nb6fe7782cef8
「２」くぁない
早稲田 / PASSLABO切り込み隊長
→ note.mu/pfsbr123/n/n5f377ebad8d2
「３」あいだまん
東大逆転合格/ PASSLABO歌のお兄さん
→ note.mu/pfsbr123/n/n410cc19c6d54
「４」くまたん
東大文一１点落ち？/PASSLABO癒しキャラ
→ note.mu/pfsbr123/n/n429b06b1d9b4
===========
#PASSLABO
#東大医学部発
#概要欄も見てね♪
朝６時半にほぼ毎日投稿！
一緒に動画で朝活しよう

[@cafe_rumba]

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が互いに素でないと仮定したことが誤りであるから証明終。

[@user-ij4ig9mm6v]

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

[@user-vc9fn3vx5p]

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

[@10d1102022l]

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は約数に持たないので，互いに素

[@yoooooshi152]

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

[@hamacchochannel]

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

[@user-fy1ru4tp1q]

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

[@user-dj2vq5ol2j]

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

[@yasu.....]

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

[@user-fr3iq9pj4c]

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

[@fclfc1039]

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

[@user-bj2yr3iq7t]

なにそれおもしろい！

[@user-ih1wq3fb7w]

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)………（答）

[@makimurasame7271]

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

[@user-dk3kk7jq8z]

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

[@user-tx3xv9vc3j]

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

[@samurai9363]

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

[@opopo_dog]

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

[@user-hl2or2dt3z]

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

[@user-ro4qz5vz7i]

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

[@user-fr9xn1ne6w]

@@user-hl2or2dt3z 最高傑作ですよね

[@mh35jp]

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)が唯一解である

[@Lebes_Gue]

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

[@gamedaisukionce]

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

[@2chanto]

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

[@user-bs5fn8ez8f]

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

[@user-sw9vx6hw8i]

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

[@ktsn1130]

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

[@user-jc6nm8tb3m]

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

[@user-mv8kb1jc6q]

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

[@user-dk3kk7jq8z]

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

[@epin9071]

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

[@user-im3iv4wq7s]

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

[@hirokimorita9153]

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

[@xxshibata3734]

分かりやすい！ｗｗ

[@user-xn3ez6hq6r]

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

[@user-bj2yr3iq7t]

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

[@user-zabifxaxb]

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

[@yamashitamizuki]

美しい

[@lcja7827]

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

[@lcja7827]

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

[@user-sk4em5zn7s]

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

[@user-ly7qj9gq3x]

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

[@user-ht2lu8zw8o]

二項定理で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 を帰納法で示す っていうのを考えてました

[@user-sk4em5zn7s]

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

[@ETeppei]

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

[@overcapacitywhale]

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

[@r.kgalaxy7389]

なんか感動しましたw

[@YY-nf3ys]

合同式はいちいち証明しないと減点の可能性が大なので、使わない方法で解く方法を知っておかないと1点に泣くんですよね。

[@user-jc6nm8tb3m]

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

[@user-wi1zk5vq5t]

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

[@user-te3vn4qq2y]

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

[@user-wn3gm2dr5j]

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

[@user-wi1zk5vq5t]

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

[@user-bz6lk1tb1u]

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

[@atama.ga.torinosu]

良問ルート2日目

[@user-lr7uu3ky9s]

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

[@potatox2931]

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

[@user-ep1tk7jk5h]

駿台の夏期講習！

[@user-li5vn1bv5v]

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

[@yucchi2005]

この問題ってmod無しで解けますかね？

[@user-jw4bf9vw3t]

nじょう　ひく　nじょう　の因数分解使えばいけると思います

[@a._shu]

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

[@user-fd5xq2ly6f]

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

[@INAKENinaken]

九大は良問が多い

[@user-je3gw8fq9x]

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

[@user-qp4gm3ee9q]

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

[@ten4558]

九大！！

[@user-rp4mc7kp3k]

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

[@user-gi1yv7pj1r]

風呂場で解いた

[@user-fl1bv2sy9r]

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

[@53matu7]

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

[@53matu7]

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

[@user-xk4iz4vf5f]

岡山大学みたいです

[@user-vi6ll6ds9c]

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

[@kai-wo5ik]

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

[@user-bq2zs3bc3e]

誰か詳しい方添削お願いします！ (与式)⇔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

[@user-yt8gw3nw8q]

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

[@awake2455]

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

[@xiang0519]

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

[@awake2455]

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

[@user-lg9gy8zf2x]

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

[@user-su7tr9mn9b]

4:31 「もっど」

[@user-su7tr9mn9b]

これ誘導

[@Gold_bahha]

mod3の匂いがする

[@user-dv9vk9iy4p]

mod3 で瞬殺した

[@ox6303]

次のように解いてみました． 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 ) である．…(答)

[@user-ib7zv6mr2g]

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

[@user-dr7gi6xk5f]

どれ

[@user-wn3gm2dr5j]

平方数で察した

[@lawrenceezpz5737]

フェルマーの小定理見えた

[@wc3722]

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

[@user-ft2rw4ms5q]

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

[@victorymountain72]

自慢させてください、暗算で解けました

[@Good.efforter]

すごいです！

[@dasukesi]

えっぐ

[@victorymountain72]

暖かい世界だった(੭ु ˃̶͈̀ д ˂̶͈́)੭ु⁾⁾

[@user-yt8gw3nw8q]

答えが分かっても全て、っていう証明がいるのが数学の難しさだよね。 逆に言えば答え分かっちゃえばそれになるように何とか持っていけばいいから楽になる。