黄昏より暗きもの、血の流れより赤きもの

読者です 読者をやめる 読者になる 読者になる

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

入試問題をプログラムで解いてみる(2):ちょっと無理矢理な不定方程式(早稲田実業高校)

(1):a,b自然数とし、p素数とする。
このときx二次方程式ax^2-x-8ab=0x=pを解に持つとする。このときp=ap \geq 3であることの必要十分条件であるか?
(2):a,b自然数とし、pp > aを満たす素数とする。
このときx二次方程式ax^2-x-8ab=0x=pを解に持つ。条件を満たす (a,b,p)の組のうち、pが最小のものを答えよ。(早稲田実業高校 問題追加及び改訂)

C言語で総当たり

プログラム

結果

探索範囲 1 \leq a,b,p\leq 50にて探索。その結果(a,b,p)=(1,7,8),(1,9,9),(1,30,16),(1,34,17),(2,31,16),
(3,1,3),(5,3,5),(7,6,7),(9,10,9),(11,15,11),(13,21,13),(15,28,15),(17,36,17),(19,45,19)より、条件を満たす(a,b,p)の組は14組
見つかる。

C言語Javaに強い皆さん程、一旦プログラムで不定方程式の解の候補を総当たりさせると良い。そうするとデータから問題以外の発見ができたりする。

小さい(a,b,p)に対して探索(実験)を行ったところ14通りの候補が見つかった。こうして見るとp \geq 3のときp=aとなっていることが分かり、pが素数p>aを満たすものはレアケースである事が分かる。そうなる理由を以下に追ってみよう。

答えを検証

(1)の答え

十分性の証明(=>)

p=aのとき、ap^2 - p - 8ab = 0よりp^3 - p - 8pb = 0

b \geq 1を満たす必要があり、p^2 = 8b+1 \geq 9 ∴p \geq 3 である事が必要。

必要性の証明(<=)

逆にp \geq 3のとき、ap^2-p-8ab=0b = \frac{(ap-1)(p)}{8}p \geq 3より、ap-1が8の倍数である事が必要。kは自然数として、ap-1=8kとおく。

ここでk=1のときap=9となる。ここで(a,p)=(1,9),(3,3)の2通り考えられる。しかし(a,p)=(1,9)の場合はa=pとならず、常に成り立つとは限らず成立しない。

この事からp=ap \geq 3であることの十分条件である(必要十分条件ではない)

(2)の答え

式変形より、b = \frac{p(ap-1)}{8}

p=2のとき、b = \frac{(2a-1)}{4}となり、分母が奇数よりbが自然数となりえない。

p \geq 3が必要なので、pは奇数より、(ap-1)が8の倍数であることが必要。これよりap-1=8k (k \geq 1)とおく。ap=8k+1より右辺も奇数。このときp \geq aより、a=1以外となり得ない。

k=1のとき、p=9よりpが素数ではないので不適。k=2のとき、p-1=16 より、p=17、一方bは、b = 16*17/8= 34より、(a,b,p)=(1,34,17)