すこし難しくなるかな。

合同の知識は、暗号の理論等にも良く使われてて、コンピュータについてさらに詳しく知りたい人には基本知識の1つ。難しく感じたら、初等整数論の教科書等を見るといいだろう。

一次合同式を解くとは、a、b を自然数とするとき、a x ≡ b (mod m) となる x を求めることをいう。

例えば、3x ≡ 2 (mod 7) の解は、 x ≡ 3 (mod 7) で与えられる。

一次合同式が解を持たないこともある。例えば、 3x ≡ 1 (mod 6) は解を持たない。

<関数名>
  congruence —- 一次合同式 a x≡b (mod m) を満たす x を求める

<形式>
  int congruence(int a, int b, int m);

<引数>
  a、b、m ともに自然数

<関数値>
  合同式の解 x の値 (0≦x<m)。解がない時に、関数値は -1 となる。

用例

<関数本体>
  congruence.c

<説明>
  合同式 a x≡b (mod m) を解くには、もう一つ自明な合同式 m x≡0 (mod m) を利用して、同値な変形を繰り返せばよい。すなわち、x の係数 a と m に対して ユークリッド互除法 を用いて、 x の係数を小さく変形していく。

Comments are closed.

Post Navigation