2004-07-11 (日)
-
天気:晴れ
*暑い…
今日は久しぶりに頭の中は数学モード．中３の時に考えていた問題の続きを考える．
aとbが互いに素であるとき，y≡{a*x mod b | x∈Z,0≦x＜b}というyを定義すると，yは0〜bの全ての整数を埋め尽くす．つまり，{a*x mod b | x∈Z,0≦x＜b}≡{y|y∈Z,0≦y＜b}．
これは，グラフィックのワイプ処理をしようとして，平面を埋め尽くす数列を色々考えていたときに思いついた仮定．今だったらα合成してしまうけど，当時はCPUが遅かったしメモリも節約したかったので，テーブルを作らずにしかも，見た目はランダムに点で画面を埋め尽くす必要があった．こんな妙な仮定を用いたアルゴリズムは見たことが無いのだけど，どこかに穴があるのだろうか…．
思いついたときは，これは絶対成り立つと思ったのですが，根拠があったのかなぁ．で，５年以上経って証明を試みるが，なんか，アレにそっくりです．拡張ユークリッドの互除法を導くときに使った定理が色々使えそうです．つまり，ax - by = i のとき，iに対するxとyが一意に定まれば良いわけか．なんか，嫌な感じがしてきました．符号と暗号の授業で出てきた定理にたしか，d=gcd(a,b)のとき，ax + by = d を満たす，xとyが存在してどうこうというのがあったはず．ということは，両辺に整数を掛けても成り立つので，a,bが互いに素ならgcd(a,b)=1なので，iについても成り立つことがいえるはず．確か，唯一の解が存在する条件の話も先生がしてたはずなので，たぶん，それも成り立ってる(覚えてないけど)．
というわけで，あの仮定は正しかった(と思う)．これで考えてたアルゴリズムが安心して使えます．それに，未解決の引き出しの中身が一つ減って気が少し晴れました．