大学入試 整数問題の解法

質問

数学で、以下の問題の解法が分かりません。
ご存じの方いらっしゃいましたら、教えていただきたいです。
途中までは考えたのですが、そこから上手くいきません。違うやり方でスマートな方法があるのでしょうか。
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
『３以上9999以下の奇数aで、a^2-aが10000で割り切れるものをすべて求めよ』
（答えはa=625のみだそうです）
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
途中まで考えた部分を載せておきます。
(1)まず10000を素因数分解して2^4・5^4と表し、a^2-aはa(a-1)と表せてaが奇数であるからa-1=k・2^4としました。(kは自然数)
a(a-1)=2^4・5^4・p (pは自然数)として、先ほど考えたa-1を代入するとa=5^4・(p/k)となりますが、ここで(p/k)が整数ではないため、どうやって求めていけばいいのか…
(2)他の考え方として、最初にa(a-1)=2^4・5^4・pとaの偶奇からa=5^4・sとa-1=2^4・tと置くことも考えたのですが、偶数部分であるa-1が5の累乗を因数にもたないとは限らないため、sは整数とは限らない…(結局(1)の論理と同じことになりますが)

長文となってしまい申し訳ございません。
どなたか分かる方、説明していただける方がいらっしゃいましたら、よろしくお願いいたします。

回答No.2

tmpname · ベストアンサー

ああ、東大の2005年の問題ですね。
検索すればいっぱいヒットするいい練習問題ですが、それはさておき

> 偶数部分であるa-1が5の累乗を因数にもたないとは限らないため
要は、ここで「持たないことは明らか」と気付かないと、解答が遅くなるのです（気付かなくても実際は何とかなりますが）。

というのは、aとa-1とは明らかに「互いに素」（何故なら差が1しかないから。2つとも共にある数dの倍すうなら、両者の差はdの整数倍ですね）なので、aとa-1とは共通の素因数を持たず、結局a-1は2^4の倍数ではあるけど5の倍数ではないのです。

そこまで気付けば、あとは実は5^4 = 625を2^4 16で試しに割ってみると625 = 16 * 39 + 1なので、625が一つの解であることがわかります。後は解が10000を法として一つしかない（10000で割った余りが同じになる）ことを言えば良い。

#No1さん
> ここでk=625qと仮定するとa=16k+1=10000q+1となって題意に適しません。
> したがって16k+1=625r
ポイントは、625は素数ではないので、この段階ではk=125r, 16k + 1 = 5sみたいな可能性が（直ちには）否定できないことにあります（直に否定されますが）。

お礼

なるほど！隣り合う二つの数が互いに素であるという事実に気づけば簡単だったんですね。
回答ありがとうございました。

回答No.1

f272

(1)の考えにのっとっていきます。出てくる文字はすべて非負整数です。
a-1=16k
a(a-1)=16*625*p
(16k+1)*k=625p
ここでk=625qと仮定するとa=16k+1=10000q+1となって題意に適しません。
したがって
16k+1=625r
両辺を5で割って余りに矛盾がないようにするにはk=5l+4です。
16(5l+4)+1=625r
80l+65=625r
16l+13=125r
両辺を5で割って余りに矛盾がないようにするにはl=5m+2です。
16(5m+2)+13=125r
80m+45=125r
16m+9=25r
両辺を5で割って余りに矛盾がないようにするにはm=5n+1です。
16(5n+1)+9=25r
80n+25=25r
16n+5=5r
両辺を5で割って余りに矛盾がないようにするにはn=0です。
したがってm=1，l=7，k=39，a=16k+1=625となります。

お礼

順序立てて説明してくださって、どうもありがとうございました！