rを平方部分とそうでない部分に分けます。例えば、24なら22と6です。一般に
r = s2t（tは平方成分を含まない）
と書けます。そうすると、q, dは、
q = sut
d = u2t
元の式は、
n = m2 = qd + r = st(tu3 + s)
ここからtはsで割り切れることを示します。
tは平方を含まないから、
t = p1…pl（pkは素数 l ≥ 0）
と書けます。sがpkで割り切れないならtu3 + sもpkも割り切れないので、右辺はpkを一つしか持たないことになり平方数になりません。よってsはpkで割り切れます。全ての素因数についてこれが成り立つので、sはtで割り切れることになります。
とりあえず、3秒になりました。
