91が素数でないので素因数分解した7×13のそれぞれを法とした合同式で考えるのは常道ですね。 もし理系の入試なら x ≡ a (mod 7), x ≡ b (mod 13)を出した後は中国の剰余定理とユークリッドの互除法を使い、 2×7 - 13 = 1 から x ≡ -13a + 14b (mod 91)としてそれぞれを求めたいところです。
コメント（長文）失礼します あまりエレガントな解き方でもなく、また本質的にはあまり変わらない気もするのですが、こんな形のものはいかがでしょう？（以下の丸括弧は解いている際のお気持ちのようなものです） （まず、n^2+n+1をそのまま何度も計算する気も、掛け算も足し算も何度かすることになるのであまり起きず、n-1を掛けたらn^3-1になるので少しは楽かなぁ……と考えて整理してみます、というか最初に展開公式が出てきたのでそこから発想を飛ばせないかというのが原点でした） n^2+n+1≡0 (mod 91)……(☆)の同値な条件を考える。両辺にn-1をかければ (☆)⇒n^3-1≡0⇔n^3≡1(ここまでmod 91)……①⇒n^3≡1(mod 7)……②∧n^3≡1(mod13)……③ （ここで同値性が崩れていることには気をつける、特に91=7*13から、mod 7や mod 13でn-1≡0になるものは答えになるか怪しそう……という感覚です。やっていることは必要条件の絞込にすぎません） そこで、mod 7やmod 13でn^3≡1となるような、(☆)の候補を探すと、 （この過程は省略しますが三乗計算1回ずつだけなので±を利用して表でも書けばすぐだと思います。知識のある場合は平方剰余ならぬ立方剰余？のようなものを考えてもよいと思いますが……あまり詳しくないのでごめんなさい） ②⇔n≡1∨n≡2∨n≡-3(すべてmod 7) ③⇔n≡1∨n≡3∨n≡-4(すべてmod 13) となるので、(☆)を満たしうる候補は以下の9つとなる： (n mod 7, n mod 13)=(1,1),(1,3),(1,-4),(2,1),(2,3),(2,-4),(-3,1),(-3,3),(-3,-4)……④ （あとは④のそれぞれが十分条件を満たすか、逆である④⇒(☆)を個別に検証していけば終わりではあります。ここで、n-1≡0の時は少し怪しいという感覚に基づき、これを示してみることを考えてみます。示さずとも愚直に計算して不適であることを出せるのであまり重要ではないかもしれませんが……） (a)n-1が91と互いに素のとき i.e. n mod 7≠1∧n mod 13≠1のとき ①⇔n^3-1≡(n-1)(n^2+n+1)≡0⇔n^2+n+1≡0(ここまでmod 91):(☆) となるので、これに該当する (n mod 7, n mod 13)=(2,3),(2,-4),(-3,3),(-3,-4) については、全て求める条件を満足する。 （合同式では割る数と法が互いに素なら割っても合同というだけです） (b)そうでない場合 i.e. n mod 7=1∨n mod 13=1のとき {p,q}={7,13}とすると、n mod p=1と代表して一般性を失わない。このとき、特に n^2+n+1≡0(mod pq)⇒n^2+n+1≡0(mod p) であるのに対して n≡1(mod p)⇒n^2+n+1≡3(mod p) であって、3 mod p≠0なので、これに該当する④の候補は(☆)の解たりえず、問の条件を満足しない。そのような候補は、④のうち(a)で挙げられていないもの全てである。 （表現がなかなか難しいので良い書き方があったら教えてください。{p,q}={7,13}は集合の相等を用いることで、(p,q)=(7,13),(13,7)を意味するのですが、少し答案ならラクできるかと思って使いました） 従って、(a)に該当する各nを計算して、求める条件として【n≡9,16,74,81 (mod 91)】を得る。 （この計算は愚直にしてもよいでしょうし、大変そうだと見切りをつけてマイナスから考えていくのもありだと思います。あとはコメント欄で既に指摘されていますが、CRT：中国剰余定理とか連立合同式とかEuclidの互除法とかを使った処理も可能でしょう。せいぜい特殊解として 4つ見つければ合同式で表現できるので、これだけなら大袈裟な式を振り回さなくても良いかもしれません。） あと、完全なる余談なんですが、答の9と81、16と74、それぞれ小さい方は平方数同士で、ペアを足すと90になってるんですよね……何かここから上手い別解が作れそうな匂いはするのですが（対称性については動画でも触れられていましたが、それをもっと全面に押し出したような解答……？）、パッと出てこず……なにかアイディアがあればご教授いただけると幸いです！長文失礼しました……
n**2+n+1=n(n+1)+1で必ず奇数になるので91の偶数倍にはならないことが分かる。
よってn**2+n+1=182k+91(k:0以上の整数)を満たすnの条件を求めれば良い
n**2+n-90=182k
(n+10)(n-9)=182k
って感じで因数分解して解きました。気持ちよかったです。
プログラミングじゃないんだから
n^2の方がいいんじゃないですか？
因数分解、感動しました😳
因数分解すごいです。整数初めて面白いと思いました😊
おはようございます
早稲田もあと10日と少しですね。
私も創造理工学部を受けるので早稲田受ける方頑張りましょう！
これは解けました。
似たような問題を解いたことがあったので。
整数問題は多くの問題をこなすことで出来るようになります。
超難問以外はけっこうパターン決まってます。
解法に感動しました
91が素数でないので素因数分解した7×13のそれぞれを法とした合同式で考えるのは常道ですね。
もし理系の入試なら
x ≡ a (mod 7), x ≡ b (mod 13)を出した後は中国の剰余定理とユークリッドの互除法を使い、
2×7 - 13 = 1 から
x ≡ -13a + 14b (mod 91)としてそれぞれを求めたいところです。
mod7 について n²+n+1≡n²+8n+15≡(n+3)(n+5) , これが0と合同であるためにはn≡-3,2であればよい。
mod13について n²+n+1≡n²+14n+40≡(n+4)(n+10) , これが0と合同であるためにはn≡-4,3であればよい。
従ってn≡-3,2(mod 7) かつ n≡-4,3(mod 13)であればよい。までは絞れた(ものすごい遠回り)。
夏休みの時に行った理科大の数学の模擬授業で、
「ある整式に対してmod p で1次式の積に因数分解できるpはあるか」でやった覚えがあった。助かった。
最後の合同式の処理で、mod91を作るために、法にも同じ数字をかけることができることは知らなかったので違和感を抱きました。全パターン解説にはなかったような気がしましたのでまた取り上げていただけると嬉しいです
一次合同式は
係数がもう1つの数をかけると1になったこの2つの数は互い逆数と呼ぶ
合同式を解くのときに超役立つです
最初から91を引いて因数分解して解きました。不定方程式の解を見つけるのは得意なので大胆にやってみました。
コメ主じゃなくて申し訳ないです。
今やって見たんですが、
n²+n-90≡0
(n-9)(n+10)≡0
これでnが9,81は出ます(恐らくこっちがわかっていたんだと思います)
残りの2つですが、そこからさらに-182をしてみると
n²+n-272≡0
(n-16)(n+17)≡0
これでnが16,74も出ると思います！
この人は頭えぇからな。
@@とと-h8hてことはこれじゃ必要性は分かんないってことですか？
てか91って素数じゃないからn-9とn+10のどっちかが91の倍数っていうのは間違えてるくない？
@@user-toudaisibou
91の倍数⇒成り立つ
は真なので、方程式の解であることは間違いないと思います。
あとは
①他にも解が存在すること。
②残りの2つを見つけたら、4つで十分であること
の2つが解消しないといけない問題点ですが
他コメントにもあるように
modpでpが素数のときにはこの形の合同方程式の解は高々2つ(らしい)です。
動画のように、mod7のときとmod13のときを(頭の中で)考えるとmod91のときの解が高々4個であることがわかります。
なので、残りの2つを見つけたら解が全て見つかったことになるわけですが、上手く見つける事が出来た(コメ主はそれが得意？)って感じだと思います。
modpのときの解が高々2であることの理由はあんま分かりません。すみません。
質問です
合同式で因数分解して解出すときに0因子を考慮する必要があるとおもうんですがどうですか？
2次合同方程式を真面目にやると大学の整数論になるから、なかなか難しいな。
6:47 のところ、n≡3,9が結果的に出ましたが、それ以外に解がある場合を排除して考えてよいのでしょうか？
(n+4)(n-3)≡0……①まで与式から同値関係で続いているので問題ないですね
もし他に解があるのなら、①が偽になり、与式が偽になってしまいます
@@影牙 確かにそうですね！教えていただきありがとうございます！
いつも楽しく拝見してます。
『裏技』として御説明された因数分解の点、一般にℤ/nℤは整域ではないので、この結論付けはあくまで『3、7及び13は素数なので』という注釈が付くと認識しています。
動画内の説明はその点の説明を省いておられて少しリスキーに感じました。
私の受験は20数年前なので、現在は常識レベルなのかもしれませんが…
やっぱりそうですよね
不安だったので助かります
この方自身は暗黙の了解としてわかっているからこれらの例が出せるのでしょう。
そのポイントは間違いなく減点対象になると思います。それがまかり通ってしまうとmod4とかmod6とかは？みたいな話になりますし、一般論の範囲を超えている感覚です。
コメント（長文）失礼します
あまりエレガントな解き方でもなく、また本質的にはあまり変わらない気もするのですが、こんな形のものはいかがでしょう？（以下の丸括弧は解いている際のお気持ちのようなものです）
（まず、n^2+n+1をそのまま何度も計算する気も、掛け算も足し算も何度かすることになるのであまり起きず、n-1を掛けたらn^3-1になるので少しは楽かなぁ……と考えて整理してみます、というか最初に展開公式が出てきたのでそこから発想を飛ばせないかというのが原点でした）
n^2+n+1≡0 (mod 91)……(☆)の同値な条件を考える。両辺にn-1をかければ
(☆)⇒n^3-1≡0⇔n^3≡1(ここまでmod 91)……①⇒n^3≡1(mod 7)……②∧n^3≡1(mod13)……③
（ここで同値性が崩れていることには気をつける、特に91=7*13から、mod 7や mod 13でn-1≡0になるものは答えになるか怪しそう……という感覚です。やっていることは必要条件の絞込にすぎません）
そこで、mod 7やmod 13でn^3≡1となるような、(☆)の候補を探すと、
（この過程は省略しますが三乗計算1回ずつだけなので±を利用して表でも書けばすぐだと思います。知識のある場合は平方剰余ならぬ立方剰余？のようなものを考えてもよいと思いますが……あまり詳しくないのでごめんなさい）
②⇔n≡1∨n≡2∨n≡-3(すべてmod 7)
③⇔n≡1∨n≡3∨n≡-4(すべてmod 13)
となるので、(☆)を満たしうる候補は以下の9つとなる：
(n mod 7, n mod 13)=(1,1),(1,3),(1,-4),(2,1),(2,3),(2,-4),(-3,1),(-3,3),(-3,-4)……④
（あとは④のそれぞれが十分条件を満たすか、逆である④⇒(☆)を個別に検証していけば終わりではあります。ここで、n-1≡0の時は少し怪しいという感覚に基づき、これを示してみることを考えてみます。示さずとも愚直に計算して不適であることを出せるのであまり重要ではないかもしれませんが……）
(a)n-1が91と互いに素のとき i.e. n mod 7≠1∧n mod 13≠1のとき
①⇔n^3-1≡(n-1)(n^2+n+1)≡0⇔n^2+n+1≡0(ここまでmod 91):(☆)
となるので、これに該当する
(n mod 7, n mod 13)=(2,3),(2,-4),(-3,3),(-3,-4)
については、全て求める条件を満足する。
（合同式では割る数と法が互いに素なら割っても合同というだけです）
(b)そうでない場合 i.e. n mod 7=1∨n mod 13=1のとき
{p,q}={7,13}とすると、n mod p=1と代表して一般性を失わない。このとき、特に
n^2+n+1≡0(mod pq)⇒n^2+n+1≡0(mod p)
であるのに対して
n≡1(mod p)⇒n^2+n+1≡3(mod p)
であって、3 mod p≠0なので、これに該当する④の候補は(☆)の解たりえず、問の条件を満足しない。そのような候補は、④のうち(a)で挙げられていないもの全てである。
（表現がなかなか難しいので良い書き方があったら教えてください。{p,q}={7,13}は集合の相等を用いることで、(p,q)=(7,13),(13,7)を意味するのですが、少し答案ならラクできるかと思って使いました）
従って、(a)に該当する各nを計算して、求める条件として【n≡9,16,74,81 (mod 91)】を得る。
（この計算は愚直にしてもよいでしょうし、大変そうだと見切りをつけてマイナスから考えていくのもありだと思います。あとはコメント欄で既に指摘されていますが、CRT：中国剰余定理とか連立合同式とかEuclidの互除法とかを使った処理も可能でしょう。せいぜい特殊解として
4つ見つければ合同式で表現できるので、これだけなら大袈裟な式を振り回さなくても良いかもしれません。）
あと、完全なる余談なんですが、答の9と81、16と74、それぞれ小さい方は平方数同士で、ペアを足すと90になってるんですよね……何かここから上手い別解が作れそうな匂いはするのですが（対称性については動画でも触れられていましたが、それをもっと全面に押し出したような解答……？）、パッと出てこず……なにかアイディアがあればご教授いただけると幸いです！長文失礼しました……
さすがパスラボ！ 理屈はわかったんですが、これって証明になってるの？
工夫せずに、4通りくらいはやるかーって思って普通に不定方程式解きました。
答えはm正のときではなく，整数全体でないでしょうか。たとえば，m=-1のときのn=91m+81=-10を与式に入れると，91となり91の倍数になります。
91の周期だから〜のところから理解できないですが誰か説明してくれません7:45
合同式でmod91において、因数分解するのは良い方法だと思いますが、他にも解があることはどこで気づかなければならないのでしょうか？一方で、他の問題で、因数分解で必要十分であると判断できるのはどのような場合でしょうか？91に相当する数字が素数か素数でないか？ですか？因数分解はよい解法なのに。なんかすっきりしません、
後半部分は受験算数ぽいなーと。周期は考えたくなりますね。
Passlaboでvieta jumpingを解説した動画ってありましたっけ?
高級すぎるんじゃない？
mod100使ったら≡-9を探す旅になるから楽になりそう？？
mod 100とmod 91は本質的に影響しないはずでは？
いいえ、ならないです
91の倍数がmod100でいずれも-9になるわけないだろ
対称性があるって言うことはどう示せばいいんですか？
宇佐見さんがやったみたいに具代的に数字で示したら、証明したことになりますか？
最初からmod7とmod13で見たら結構簡単に解けました！でも実力がついてるか不安です。どうしたら実力がついてるか分かりますか？
周期なんでわかるんですか？
確かに10101=91*111（n=100）ですね。
7の倍数かつ13の倍数になればよい、と考えて
結局書き出す方法しか思いつかなかった。
modを使って解きました。
中2の時から見てて高1になった今初めてPASSLABOさんの動画でこんなに数学に驚かされました！！次は自力で解いてみたいです！！
7/60では合否を分けないのでは？？合格者が取ってくる問題を取るのが基本と思う
2023早稲商の中では個人的に1番簡単だったと思う。他の問題の考え方と何一つ変わらないのに大問1つ分の配点だったからこれ解ければ合格には十分だったのかなと予想。難易度にしては平均点が低すぎる
この年は確率が難しかった印象があります
modって、説明なしに使ってよかったっけ？。数年前はダメだけど最近は、OKって聞きました。調べても昔の記事しかなくてわかりません。知ってる方は教えて欲しいです
数字(modN)と書くor数字を法とするのどちらかが書かれていれば十分らしいです。
4:30みたいな表は、2次試験の解答用紙に書いても点貰えますか？
これ平均7/60は低くない？
論述でバンバン引かれるんかな
これは何故平均点が低いんだろう?
存外、難しいなも。
死ぬほどどうでもいいことなんですが、「かける2倍」という言い回しが気になります
基本的に後半の方早口過ぎて何説明してるか全くわからん。もっとゆっくり話せないのか？
話し方が早くて何言ってるかサッパリわからん。