備忘録：64x-27y=-1の整数解

数学

64x-27y=-1 の整数解について
mod 9 で x\equiv -1 だから x=9a-1 とおくと 9\cdot 64a-27y=63 だから，64a-3y=7
mod 3 で a\equiv 1 だから x=3b+1 とおくと 3\cdot 64b-3y=-57 だから，64b-y=-19
となり，(b,y)=(0,19) だから (x,y)=(8,19) となる，という解き方をする人はあまりいないだろうなぁ。

を学んでおくと良い．ユークリッドの互除法はユニモジュラー行列で記述できるので，行列式を考えるのは当然のこと．

mod n で k と n が互いに素ならば ka\equiv kb\Longleftrightarrow a\equiv b を押さえておくと最速の

mod 27 で 10x\equiv -1 \equiv 80 で，27 と 10 は互いに素だから x\equiv 8
このとき 64\times 8-27 y=-1 より y=\dfrac{513}{27}=19 となる．

が得られる．ユニモジュラー行列を用いる方法は機械的で安全だけど最初に紹介した割り割り法も言うほど遅くはない。