模係數記數法

模係數記數法(modular coefficient notation)是與剩餘表示有關的概念，若以兩兩互素的k個正整數m₁，m₂，…，m_k分別為模，則整數x(0≤x<M，M=m₁m₂…m_k)的剩餘表示(〈x〉_m1，〈x〉_m2，…，〈x〉_mk)稱為x的模係數記數法。

基本介紹

• 中文名：模係數記數法
• 外文名：modular coefficient notation
• 所屬學科：數學
• 所屬問題：初等數論(同餘式)
• 簡介：與剩餘表示有關的概念

基本介紹

若以兩兩互素的k個正整數m₁，m₂，…，m_k分別為模，則整數x(0≤x<M，M=m₁m₂…m_k)的剩餘表示(〈x〉_m1，〈x〉_m2，…，〈x〉_mk)稱為x的模係數記數法。由於限定0≤x<M=m₁m₂…m_k，不同的整數x對於模m₁，m₂，…，m_k的剩餘表示也是不同的。若知道了整數x的模係數記數法(〈x〉_m1，〈x〉_m2，…，〈x〉_mk)，用孫子定理即可惟一地定出x。

相關性質定理

定理1 設Z表整數集，Z_l={0，1，…，l-1}表示l的最小非負剩餘組成的集合，且m₁>0，…，m_k>0，(m_i，m_j)=1，0<i<j≤k，0≤x<m₁m₂…m_k，則集合S={x|0≤x<m₁m₂…m_k}與集合S₁={(a₁，a₂，…，a_k)|a_j∈Z_mj，j=1，2，…，k}之間存在一一對應。

定理2 設0≤x<M，0≤y<M，則x的模係數記數法有下列性質：

1.〈x±y〉_M的模係數記數法為(〈〈x〉_m1±〈y〉_m1〉_m1，〈〈x〉_m2±〈y〉_m2〉_m2，…，〈〈x〉_mk±〈y〉_mk〉_mk)。

2.〈x·y〉_M的模係數記數法為(〈〈x〉_m1〈y〉_m1〉_m1，〈〈x〉_m2〈y〉_m2〉_m2，…，〈〈x〉_mk〈y〉_mk〉_mk)。

推論 如果0≤x<M，0≤y<M，0≤xy<M，0≤x+y<M，則在定理2中把整數的剩餘表示換成整數的模數係數記數法，則結論仍然成立。

舉例說明

下面舉例說明使用模係數記數法進行加法和乘法運算帶來的方便。例如，對模3，4，5，11.x=209↔(2，1，4，0)，y=135↔(0，3，0，3)。

1) 進行加法運算：

2) 進行乘法運算：

從上例中看出，這裡乘法和加法無須進位，特別是乘法無需進位，這對計算機的製造和使用將帶來很多的方便。用模係數記數法，Z_M中的數對模M的運算，可以分別通過Z_mj中的數對模M_j(j=1，2，…，k)的運算來完成。