模运算的误解

这是系列的一部分常见的误解．

这是真的还是假的?

如果 $n .相等的$而且 $A \equiv b \pmod n$然后 $一个\枚b \ pmod {mn}。$

为什么有人说这是真的:这是一部分中国剩余定理．

为什么有人说它是假的:你可以乘 $一个$而且 $b,$但是你不能乘以模。

该声明是 $颜色\ {# D61F06} {\ textbf{假}}$．

证明:

事实上，这种说法只适用于互质整数 $米$而且 $n;$这是中国剩余定理“唯一性”部分的结果。直接看到它是真的如果 $米$而且 $n$都是相对质数的，注意到了吗 $m | (a - b)$而且 $n | (a - b),$所以 ${lcm} \文本(m, n) | (a - b)。$如果 $米$而且 $n$相对', ${lcm} \文本(m, n) =锰、$所以 $mn | (a - b),$所以 $一个\枚b \ pmod {mn}。$

这个证明使一般的结果很清楚:如果 $n .相等的$而且 $A \equiv b \pmod n$然后 $\枚b \ pmod{\文本模块}{{\小(m, n)}}。$(反之亦然。)

例如,如果 $= 13, b = 1, m = 4, n = 6,$然后 $13\equiv 1 \pmod 4$而且 $13\equiv 1 \pmod 6;$但 $13不\ \ 1枚\ pmod{24}。$这是对原命题的反例。 $\大($请注意, $13 \枚1 \ pmod {12}$而且 $12 = {lcm} \文本(4、6)。\大)$ $_ \广场$

反驳:如果 $米$而且 $n$的因素 $a - b,$然后它们都出现在因式分解中 $a - b,$所以它们的乘积也出现了。所以 $mn | (a - b)。$
回复只有当 $米$而且 $n$相对'。在上面的例子中， $13-1 = 12 = {\bf 4} \cdot 3 = {\bf 6} \cdot 2，$但 $4$而且 $6$不会出现在相同的因式分解中 $a - b。$

---

反驳这个结果在很多情况下都是正确的。例如,如果 $米$而且 $n$是不同的质数，结果为真。
回复这是正确的，但这种说法仍然是错误的，因为它并不适用于所有人 $m, n。$

这是真的还是假的?

如果 $A \equiv b \pmod m$然后 $A = b + m。$

为什么有人说这是真的:如果 $a = b + m,$然后 $\ \ pmod枚b m。$

为什么有人说它是假的:有两个以上的数相等 $b \ pmod m。$

该声明是 $颜色\ {# D61F06} {\ textbf{假}}$．

证明:

反过来是正确的，但这个陈述是错误的:如果 $n .相等的$而且 $b$是固定的，有无限多的选择 $一个。$例如,如果 $b = 1$而且 $m = 3,$然后 $一个$可能是 $b + m = 1 + 3 = 4,$但也有可能是这样 $7,$或 $1，$或 $-998年。$表格中的任何数字 $1 + 3 k,$ $k$整数也可以。 $_ \广场$

反驳下面是一个例子:如果 $= 7, b = 3 m = 4,$然后 $\ \ pmod枚b m$而且 $a = b + m。$

回复的某些值，结论成立 $a、b、m,$但并不是所有的。所以这个表述是假的。

这是真的还是假的?

如果 $A \equiv b \pmod m$然后 $Na \equiv nb \pmod{nm}。$

为什么有人说这是真的:一切都乘以 $n。$

为什么有人说它是假的:方程两边同时乘以是有意义的 $n,$但是改变模量也是不同的。

该声明是 $颜色\ {# 3 d99f6} {\ textbf{真}}$．

证明:

转换成关于可除性的表述。开始 $A \equiv b \pmod m;$这意味着 $m | (a - b)。$所以 $可= a - b$对于一些整数 $k。$现在两边同时乘以 $护士:$ $MNK = n(a-b) = na-nb，$所以 $Mn |(na-nb) \隐含na \equiv nb \pmod{Mn}。\ _ \广场$

反驳:这只是真正的mod $米,$不是国防部 $nm。$

回复这也是真的 $米,$但这个说法更有力。证明也是不同的:而不是工作mod $米,$有必要将其转换为关于整数的语句。

这是真的还是假的?

如果 $n .相等的$而且 $n \ 0,$然后 $n .相等的;$

为什么有人说这是真的:它对整数成立，所以它对整数mod也成立 $m。$

为什么有人说它是假的:除以 $n$可能不允许mod $m。$

该声明是 $颜色\ {# D61F06} {\ textbf{假}}$．

证明:

如果 $米$而且 $n$不都是相对质数，这句话不都是真的吗 $a、b。$转换 $n .相等的$到可除性命题 $m | n (a - b),$但最后, $m | (a - b)$要求 $米$而且 $n$相对'。

一个反例 $米$而且 $n$不都是相对素数吗 $m = 4, n = 2, a = 1, b = 3。$然后 $2\cdot 1 \equiv 2\cdot 3 \pmod 4，$但 $1 \not\equiv 3 \pmod$ $_ \广场$

反驳只要两边同时乘以 $\ frac1 {n}。$

回复:乘法逆 $\ frac1 {n}$不存在mod $米$除非 $米$而且 $n$相对'。

这是真的还是假的?

如果 $Na \equiv nb \pmod {nm}，$而且 $n \ 0,$然后 $n .相等的;$

为什么有人说这是真的:一切都除以 $n。$

为什么有人说它是假的:除以 $n$不允许mod $nm。$

该声明是 $颜色\ {# 3 d99f6} {\ textbf{真}}$．

证明:

将第一个同余转换为可分割语句: $纳米| (na-nb),$或 $纳米| n (a - b)。$这是一个整数 $k$这样 $nmk = n (a - b)。$自 $n \ 0,$我们可以取消 $n$从两方面来看，所以 $可= a - b,$所以 $m | (a - b),$所以 $n .相等的;$ $_ \广场$

反驳你不能取消 $n$除非它相对于模量是素数。

回复:一般来说这是对的，但是这里我们在消去后改变了模量。通过将其转换为一个关于整数的语句，该语句仍然是可证明的，其中允许取消任何非零整数。

另请参阅

• 常见的误解列表