整数論を勉強するためのスレッド

整数論を勉強するため ..

110:１３２人目の素数さん
19/12/11 09:46:09.84 VLSxIs0+.net
>>104
>>108
mは素数とする。
x_i をmで割ったときの剰余に注目して、昇順に並べる。
　0 ≦ x_1 ≦ x_2 ≦ ････ ≦ x_(2m-1) < m,
・同じ剰余がm個以上あるとき、そのm個を取り出す。
・どの剰余も(m-1)個以下のとき、
　0 < x_(m+i) - x_i < p,　　(1≦i<m)　････(1)
ここで、
S_0 = {0}
S_1 = {0, x_(m+1)-x_1}
S_t = { [Σ[i=1,t] f_i･(x_(m+i) - x_i)] mod m | f_i = 0または1 }
とおく。
補題
　#S_t ≧ t+1,　　(0≦t≦m-1)
(略証)
tについての帰納法による。
#S_0 = 1,
#S_1 = 2,
S_(t+1) = S_t Ｕ { [s+x_(m+t+1)-x_(t+1)] mod m | s∈S_t }
右辺の２つの集合は、元の数は等しい。( #S_t )
しかし元の和は (x_(m+t+1) - x_(t+1)) #S_t だけずれている。(mod m)
#S_t < m のとき、(1) より、mで割り切れない。
∴ 後者の集合は S_t にはない元を含む。
∴ #S_(t+1) ≧ #S_t + 1,　　　(終)
#S_(m-1) = m だから 0,1,････,m-1 をすべて含む。
　s ≡ - (x_1+x_2+････+x_m)　　(mod m)
となる元 s ∈ S_(m-1) を取り出せば、
　Σ[f_i=0] x_i + Σ[f_i=1] x_(m+i) ≡ 0　　(mod m)

次ページ

続きを表示

1を表示