分數模值計算公式

下面是“分數”模運算的定義：

b， m互質

k = a/b (mod m) <=> kb = a (mod m)

這裏求 x = 1/17 (mod 2668)

<=>

17x = 1 (mod 2668)

<=>

17x = 2668k + 1 （k∈整數）

取合適的k使得17|(2668k+1)

這裏剛好17 | (2668 + 1)

所以k = 1， x = (2668+1)/17 = 157

當然，當k = 1 + 17n 時

x = (2668 + 17·n·2668 + 1)/17 = 157 + 2668n

也符合條件（n任意整數）

但如果限定 2668 > x > 0，x是唯一的。