岩大学習支援デスク

学習支援デスク@2015.6.2

質問 {2x \equiv 1 \  (\rm{mod} \ {11})} となる  {x} を求めよ.

これは,不定方程式 {2x + 11y = 1} の整数解 {(x, y)}を求める問題である。

解の存在

2 と 11 は互いに素なので,最大公約数は 1 になり,

ユークリッドの定理より,{2x+11y=1} となる {x}{y} が存在する。

 0<x<11 の特殊解は,ユークリッドの互除法により求めることができる。

一般解を求める

式の変形で,{2x+11y=1} の解を求める。

解は無数にあるので,パラメータ{u} による表示 { x = x(u), \  y = y(u), \ u=0,\pm{1}, \cdots} を求めることになる。

 11y の中の2の倍数部分をまとめ,

  •  {2(x+5y)+y=1},

{x+5y = u}と置いて,

  • {2u+y=1}

これはすぐ解けて, uを任意の整数として,

  •  y = 1-2u となる。

u = x+5y なので,

  • x = u - 5y = u - 5(1-2u) = 11u-5 となる。

したがって,

  •  (x,y) = (11u-5, 1-2u), u=0, \pm{1}, \cdots となる。

 u=0 の時は,(x,y) = (6, 1) となる。