以下のような問題を考えます
【問題】$x^2+y^2=1105$を満たす自然数$(x,y)$の組をすべて求めよ
フェルマーの二平方和定理
\begin{align}
奇素数pが \; p&=x^{2}+y^{2} (x,y \in \mathbb{Z})と表せる \\ \Leftrightarrow p&\equiv 1\pmod {4} \dots (1) \\
\end{align}
ブラーマグプタ-フィボナッチ恒等式（BF恒等式）
以下の式が成り立つので$x^2+y^2$で表される2つの数$m,n$があるとき、その積$m \times n$も$x^2+y^2$で表される。
しかもその$(x,y)$のペアの数は2倍になる。
\begin{align}
&(a^2 +b^2)(c^2+d^2) \\
&=(ac−bd)^2+(ad+bc)^2 \\
&=(ac+bd)^2+(ad−bc)^2 \dots (2) \\
\end{align}
右辺の素因数分解
【問題】ですが、右辺$1105$の素因数分解をすると、3つの素数の積になり、しかも3つとも4で割った余りが１となっていることが分かります。
1105 = 5 \times 13 \times 17
従って各々は$x^2+y^2$で表すことが出来ます。
\begin{align}
1^2+2^2 &= 5 \\
2^2+3^2 &= 13 \\
1^2+4^2 &= 17 \\
\end{align}
BF恒等式のコード
(2)のBF恒等式を使うと例えば$5 \times 13 = 65$に対して$(x,y)=(1,8),(7,4)$の2通りの解が求まります。
def bf(a,b,c,d):
return ((abs(a*c-b*d),abs(a*d+b*c)), (abs(a*c+b*d),abs(a*d-b*c)))
print(bf(1,2,2,3))
# ((1, 8), (7, 4))
最終的な$1105$はこれらの解それぞれに$7$の$(1,4)$をbfで掛ければ良いので。
print(bf(1,8,1,4))
print(bf(7,4,1,4))
# ((31, 12), (33, 4))
# ((9, 32), (23, 24))
一応検算してみると正しい結果になりました。
for x,y in [(31, 12), (33, 4), (9, 32), (23, 24)]:
print(f"{x}^2+{y}^2 = {x**2+y**2}")
\begin{align}
31^2+12^2 &= 1105 \\
33^2+4^2 &= 1105 \\
9^2+32^2 &= 1105 \\
23^2+24^2 &= 1105 \\
\end{align}
解答
- $(x,y) = (31, 12),(33, 4),(9, 32),(23, 24)$
この考え方はEuler Project: Problem 273を解くのに役に立ちます。
（開発環境：Google Colab）