【整数】x^2+y^2=2009^nを満たす自然数x、yが存在することを示せ（2009・横浜国立大）【難問】

nを自然数とする。$x^2+y^2=2009^n$ を満たす自然数x、yが存在することを示せ。

（2009・横浜国立大学）

$$x^2+y^2=2009^n$$

$$x^2+y^2=(7^2\times41)^n$$

$$x^2+y^2=(7^n)^2\times41^n$$

$41^n=a^2+b^2$ を満たす自然数$a,b (a≤b)$が存在すればよい

数学的帰納法でこれを示す

(i) $n=1$ のとき

$$41=16+25=4^2+5^2$$

したがって成立する

(ii) $n=k$ のとき成立すると仮定する

$41^k=a^2+b^2$を満たす自然数$a,b (a≤b)$ が存在する

$n=k+1$ のとき

$$41^{k+1}$$

$$=41\times41^k$$

$$=41(a^2+b^2)$$

$$=(4^2+5^2)(a^2+b^2)$$

$$=4^2a^2+4^2b^2+5^2a^2+5^2b^2$$

$$=(5b-4a)^2+(4b+5a)^2$$

（※補足）

したがって成立する

(i)(ii)より

$41^n=a^2+b^2$ を満たす自然数$a,b (a≤b)$が存在する

$$x^2+y^2=(7^n)^2\times(a^2+b^2)$$

$$x^2+y^2=(7^n\times a)^2+(7^n\times b)^2$$

よって$x^2+y^2=2009^n$を満たす自然数x,yが存在する