２００５年東大 整数問題

質問

3以上9999以下の奇数aで、a^2-aが10000で割り切れるものをすべて求めよ。
～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

赤本では
a^2-a=a（a-1）と分解しaと（a-1）が互いに素である・・・(1)という証明から
はじまります。

(1)を求めようと考える必然性はありますか？

因みに私は合同式でやってみました。↓
a=2m-1（２≦ｍ≦５０００）
a^2-a=4m^2-6m+2
∴4m^2-6m+2≡１００００

でいきづまりました。

(1)の必然性
と
別解として、合同式での解き方を
どうか教えて下さい。

回答No.1

JOUNIN · ベストアンサー

整数問題の解法の定石として因数分解形に持ち込む、というのがあります
たとえば、よくある不定方程式で
ab-2a-4b-1=0(a,b∈Z)
をみたすa,bを求めたければ
(a-4)(b-2)=9
と変形すれば簡単に求まります
このように整数問題では因数分解形に持ち込むことで
見通しがよくなることが往々にしてあります
その背景を知っていればa^2-a=a(a-1)=10000
のように変形することは自然です
また、整数問題は普通の問題では条件が足りないのに
特殊な条件が加わることで解を決定する、という特徴があります
代表的な特殊条件として、素数、互いに素、奇数、偶数などがあります
このような条件が隠れてないか探すことも整数問題においては
ごくごく自然なものです
そうしてa(a-1)という式をみると、隣り合った2数の積なので
各々が互いに素となります
これをもとに10000を素因数分解してa、a-1がどのような素因数
を持つか調べ解いて行くことができます
しかしやはり隣り合った2数が互いに素というのに気づくのは
初見だと少々難しいかもしれませんね
この問題を通してその事実は覚えて置いてください

また、合同式での解法はこの場合うまくいかないでしょう
そもそも合同式の解法といいますが、合同式はあくまで
解答をスッキリ書くためのコツですので、なんら
特別な解法というわけでもありません
つまり合同式を用いないと解けない問題は一つも存在しません

参考になれば幸いです

お礼

私の要求していた答えでした！！！！

数学の先見性を磨く上で参考になる答えでした！

ありがとうございました！

回答No.4

WiredLogic

＞a^2-a=a（a-1）と分解しaと（a-1）が互いに素である・・・(1)という証明から
＞はじまります。
＞(1)を求めようと考える必然性はありますか？

証明までせんといかんか？とは思いますが、
「必然性」というより、そこに目がいかないと、
実際、aを絞り込むことは(a=2m+1などとおいて、
mを絞り込むことも)難しいので、結局行き詰るかと。

で、合同式を使う、その後のやり方を書こうかと思ってましたが、
ちょっと思い出して、東進の大学入試問題過去問データベースを見たら、
その解答例が、ちょうどご希望に叶いそうな奴でした。
(ここは、証明はせず、ほとんど自明のような書き方を
していました。赤本と言うのが、文字通りの教学社の奴だと、
数学の解答例がややおおげさな傾向があったりします)

ここは、会員登録しないと、中身は見られませんが、
無量で、会員資格なども特にうるさいことはないので、
よかったら、登録してご覧になるといいかも。
URLは、http://www.nyushimondai.com/です。

お礼

thank you!

回答No.3

DJ-Potato

a^2-aが10000で割り切れる、ということは、a^2-aを素因数分解した時に、５と２が最低でも４つずつ出て来るということです。
aと(a-1)は、２以上の連続する２整数なので、必然的に互いに素なのですが、定義よりaは奇数、つまり(a-1)は偶数です。
となれば、４つの５はaから　４つの２は(a-1)から出て来る、ということになります。

つまりaの候補は、5^4=625の奇数倍、3～9999であれば高々８個です。
解き方が美しいとは思いませんが、８個なら列挙しても許される数ですね。

ちなみに、3～9999となっているのは、
aが10000を超えると、aが5^4の倍数でなく、(a-1)が10000の倍数である場合
つまりa=10001, 20001・・・などの可能性が出て来るためではないでしょうか。

お礼

best answerにしようと思ったぐらい論理的です。

私の要求していたことを汲んでいただきありがとうございます！

回答No.2

alice_44

その赤本のやり方は、計算量も答案の文章も
コンバクトに済ませられて、気のきいた解法
だと思います。しかし、どんな解法にせよ、
必然ということはないでしょう。
常に、別解はありえるのだから。

貴方の「合同式を用いた方法」ですが、
a を勝手に奇数と決めてしまっているのは
a が偶数の場合は後で出てくるのだとしても、
≡10000 の部分はイタダケナイ。
それは、単なるデタラメでしょう。
その式を立てた根拠は、何ですか？

合同式を使うとすれば、aa-a=10000n から
何か 10000 の約数を法として aa-a≡0 となり、
これを使って a の剰余を絞り込んでゆく
ことになるかと思いますが、その際、
10000 が 2 や 5 で何回も割りきれることが
難点となり、あまりスバッとはいきません。
10000 でなくて、素数の積のような数なら
上手くゆくんですがね。

お礼

合同式は便利なものという
曖昧な知識で用いてしまいました。

alice 44サンの
・・・合同式を使うとすれば、aa-a=10000n から
何か 10000 の約数を法として aa-a≡0 となり、
これを使って a の剰余を絞り込んでゆく
ことになるかと思いますが、その際、
10000 が 2 や 5 で何回も割りきれることが
難点となり、あまりスバッとはいきません。
10000 でなくて、素数の積のような数なら・・・

が参考になりました！！