工繊大の塚本です.

In article <b3a67771-640c-412b-9f85-fed5d73d802d@n26g2000yqh.googlegroups.com>
KyokoYoshida <kyokoyoshida123@gmail.com> writes:
> ちょっと混乱しております。
> 
> In article <100927172650.M0206377@ras2.kit.ac.jp>
> Tsukamoto Chiaki <chiaki@kit.ac.jp> writes:
> > ですから, x^2 ≡ -1  (mod 5^k) を満たす x = b_k を
> > b_k = x_0 + 5 x_1 + … + 5^{k-1} x_{k-1}  (0 ≦ x_i ≦ 4) の形で
> 
> どうしてこの形と分かるのでしょうか?

自然数の 5 進表記を考えれば明らかでしょう.
10進表記で, 例えば 2010 = 0 + 10 * 1 + 10^2 * 0 + 10^3 * 2 と,
任意の自然数が一意に書き表せるように,
同じ自然数は, 例えば
 2010 = 0 + 5 * 2 + 5^2 * 0 + 5^3 * 1 + 5^4 * 3, つまり
 (2010)_{10} = (31020)_{5} と, 一意的に 5 進表記が出来ます.

 2010/5 = 402 余り 0,
  402/5 = 80  余り 2,
   80/5 = 16  余り 0,
   16/5 = 3   余り 1,
    3/5 = 0   余り 3.

特に, 5^k での合同類の代表元となる自然数であれば,
 5 進 k 桁で表わすことが出来ます.

> >  k = 2 の時は, (b_2)^2 ≡ -1  (mod 5^2) となる b_2 を
> >  b_2 = 2 + 5 x_1  (0 ≦ x_1 ≦ 4) の形で求めることになります.
> 
> ここもどうしてb_2 = 2 + 5 x_1 の形と分かるのでしょうか?

 5^2 を法として二乗して -1 になる数は,
 5 を法としても二乗して -1 になる数ですから,
一桁目の x_0 は 5 を法として二乗して -1 になる数です.
二通りの取り方がありますが, 今は 2 の方を取ることに
決めました. 5 進 2 桁の数ですから, 上の形です.

実際それで b_2 が見つかるのですから,
それで良いではありませんか.
もし見つからないなら, 全ての取り方を考えて,
本当に見つかるか, どうしても見つからないかの
結論を出さないといけませんが,
見つかったのだから,
別に全ての場合を考える必要はないのです.

# 何通り解があるか, は別の問題です.
-- 
塚本千秋@数理・自然部門.基盤科学系.京都工芸繊維大学
Tsukamoto, C. : chiaki@kit.ac.jp