求“韩信点兵”的同余解法 同余式组的求解定理是什么啊？
\u53e4\u7b97\u4e2d\u7684\u201c\u97e9\u4fe1\u70b9\u5175\u201d\u5c31\u662f\u73b0\u4ee3\u6570\u5b66\u4e2d\u7684\u4e00\u6b21\u540c\u4f59\u5f0f\u7ec4\u89e3\u6cd5\u53e4\u7b97\u4e2d\u7684\u201c\u97e9\u4fe1\u70b9\u5175\u201d\u5c31\u662f\u73b0\u4ee3\u6570\u5b66\u4e2d,\u6570\u8bba\u4e2d\u7684\u4e0d\u5b9a\u65b9\u7a0b\uff01
\u8fd9\u79cd\u5de7\u5999\u7b97\u6cd5\uff0c\u4eba\u4eec\u79f0\u4e3a\u9b3c\u8c37\u7b97\uff0c\u4e5f\u53eb\u9694\u5899\u7b97\uff0c\u6216\u79f0\u4e3a\u97e9\u4fe1\u70b9\u5175\uff0c\u5916\u56fd\u4eba\u8fd8\u79f0\u5b83\u4e3a\u201c\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\u201d\u3002\u5728\u6570\u8bba\u4e2d\u79f0"\u5b59\u5b50\u5b9a\u7406".
\u5230\u4e86\u660e\u4ee3(1593\u5e74)\uff0c\u6570\u5b66\u5bb6\u7a0b\u5927\u4f4d\u7528\u8bd7\u6b4c\u6982\u62ec\u4e86\u8fd9\u4e00\u7b97\u6cd5\uff0c\u4ed6\u5199\u9053\uff1a
\u4e09\u4eba\u540c\u884c\u4e03\u5341\u7a00\uff0c\u4e94\u6811\u6885\u82b1\u5eff\u4e00\u679d\uff0c
\u4e03\u5b50\u56e2\u5706\u6708\u6b63\u534a\uff0c\u9664\u767e\u96f6\u4e94\u4fbf\u5f97\u77e5\u3002
\u5728\u4e2d\u56fd\u6570\u5b66\u53f2\u4e0a\uff0c\u5e7f\u6cdb\u6d41\u4f20\u7740\u4e00\u4e2a\u201c\u97e9\u4fe1\u70b9\u5175\u201d\u7684\u6545\u4e8b\uff1a
\u97e9\u4fe1\u662f\u6c49\u9ad8\u7956\u5218\u90a6\u624b\u4e0b\u7684\u5927\u5c06\uff0c\u4ed6\u82f1\u52c7\u5584\u6218\uff0c\u667a\u8c0b\u8d85\u7fa4\uff0c\u4e3a\u6c49\u671d\u7684\u5efa\u7acb\u4e86\u5353\u7edd\u7684\u529f\u52b3\u3002\u636e\u8bf4\u97e9\u4fe1\u7684\u6570\u5b66\u6c34\u5e73\u4e5f\u975e\u5e38\u9ad8\u8d85\uff0c\u4ed6\u5728\u70b9\u5175\u7684\u65f6\u5019\uff0c\u4e3a\u4e86\u4fdd\u4f4f\u519b\u4e8b\u673a\u5bc6\uff0c\u4e0d\u8ba9\u654c\u4eba\u77e5\u9053\u81ea\u5df1\u90e8\u961f\u7684\u5b9e\u529b\uff0c\u5148\u4ee4\u58eb\u5175\u4ece1\u81f33\u62a5\u6570\uff0c\u7136\u540e\u8bb0\u4e0b\u6700\u540e\u4e00\u4e2a\u58eb\u5175\u6240\u62a5\u4e4b\u6570\uff1b\u518d\u4ee4\u58eb\u5175\u4ece1\u81f35\u62a5\u6570\uff0c\u4e5f\u8bb0\u4e0b\u6700\u540e\u4e00\u4e2a\u58eb\u5175\u6240\u62a5\u4e4b\u6570\uff1b\u6700\u540e\u4ee4\u58eb\u5175\u4ece1\u81f37\u62a5\u6570\uff0c\u53c8\u8bb0\u4e0b\u6700\u540e\u4e00\u4e2a\u58eb\u5175\u6240\u62a5\u4e4b\u6570\uff1b\u8fd9\u6837\uff0c\u4ed6\u5f88\u5feb\u5c31\u7b97\u51fa\u4e86\u81ea\u5df1\u90e8\u961f\u58eb\u5175\u7684\u603b\u4eba\u6570\uff0c\u800c\u654c\u4eba\u5219\u59cb\u7ec8\u65e0\u6cd5\u5f04\u6e05\u4ed6\u7684\u90e8\u961f\u7a76\u7adf\u6709\u591a\u5c11\u540d\u58eb\u5175\u3002
\u8fd9\u4e2a\u6545\u4e8b\u4e2d\u6240\u8bf4\u7684\u97e9\u4fe1\u70b9\u5175\u7684\u8ba1\u7b97\u65b9\u6cd5\uff0c\u5c31\u662f\u73b0\u5728\u88ab\u79f0\u4e3a\u201c\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\u201d\u7684\u4e00\u6b21\u540c\u4f59\u5f0f\u89e3\u6cd5\u3002\u5b83\u662f\u4e2d\u56fd\u53e4\u4ee3\u6570\u5b66\u5bb6\u7684\u4e00\u9879\u91cd\u5927\u521b\u9020\uff0c\u5728\u4e16\u754c\u6570\u5b66\u53f2\u4e0a\u5177\u6709\u91cd\u8981\u7684\u5730\u4f4d\u3002
\u6700\u65e9\u63d0\u51fa\u5e76\u8bb0\u53d9\u8fd9\u4e2a\u6570\u5b66\u95ee\u9898\u7684\uff0c\u662f\u5357\u5317\u671d\u65f6\u671f\u7684\u6570\u5b66\u8457\u4f5c\u300a\u5b59\u5b50\u7b97\u7ecf\u300b\u4e2d\u7684\u201c\u7269\u4e0d\u77e5\u6570\u201d\u9898\u76ee\u3002\u8fd9\u9053\u201c\u7269\u4e0d\u77e5\u6570\u201d\u7684\u9898\u76ee\u662f\u8fd9\u6837\u7684\uff1a
\u201c\u4eca\u6709\u4e00\u4e9b\u7269\u4e0d\u77e5\u5176\u6570\u91cf\u3002\u5982\u679c\u4e09\u4e2a\u4e09\u4e2a\u5730\u53bb\u6570\u5b83\uff0c\u5219\u6700\u540e\u8fd8\u5269\u4e8c\u4e2a\uff1b\u5982\u679c\u4e94\u4e2a\u4e94\u4e2a\u5730\u53bb\u6570\u5b83\uff0c\u5219\u6700\u540e\u8fd8\u5269\u4e09\u4e2a\uff1b\u5982\u679c\u4e03\u4e2a\u4e03\u4e2a\u5730\u53bb\u6570\u5b83\uff0c\u5219\u6700\u540e\u4e5f\u5269\u4e8c\u4e2a\u3002\u95ee\uff1a\u8fd9\u4e9b\u7269\u4e00\u5171\u6709\u591a\u5c11\uff1f\u201d
\u7528\u7b80\u7ec3\u7684\u6570\u5b66\u8bed\u8a00\u6765\u8868\u8ff0\u5c31\u662f\uff1a\u6c42\u8fd9\u6837\u4e00\u4e2a\u6570\uff0c\u4f7f\u5b83\u88ab3\u9664\u4f592\uff0c\u88ab5\u9664\u4f593\uff0c\u88ab7\u9664\u4f592\u3002\u300a\u5b59\u5b50\u7b97\u7ecf\u300b\u7ed9\u51fa\u4e86\u8fd9\u9053\u9898\u76ee\u7684\u89e3\u6cd5\u548c\u7b54\u6848\uff0c\u7528\u7b97\u5f0f\u8868\u793a\u5373\u4e3a\uff1a
\u7528\u73b0\u4ee3\u7684\u6570\u5b66\u672f\u8bed\u6765\u8bf4\uff0c\u8fd9\u5e45\u201c\u5f00\u65b9\u4f5c\u6cd5\u672c\u6e90\u56fe\u201d\u5b9e\u9645\u4e0a\u662f\u4e00\u4e2a\u6307\u6570\u4e3a\u6b63\u6574\u6570\u7684\u4e8c\u9879\u5f0f\u5b9a\u7406\u7cfb\u6570\u8868\u3002\u7a0d\u61c2\u4ee3\u6570\u7684\u8bfb\u8005\u90fd\u77e5\u9053\uff1a
\u300a\u5b59\u5b50\u7b97\u7ecf\u300b\u5b9e\u9645\u4e0a\u662f\u7ed9\u51fa\u4e86\u8fd9\u7c7b\u4e00\u6b21\u540c\u4f59\u5f0f\u7ec4
\u7684\u4e00\u822c\u89e3\uff1a
\u5176\u4e2d70\u300121\u300115\u548c105\u8fd9\u56db\u4e2a\u6570\u662f\u5173\u952e\uff0c\u6240\u4ee5\u540e\u6765\u7684\u6570\u5b66\u5bb6\u628a\u8fd9\u79cd\u89e3\u6cd5\u7f16\u6210\u4e86\u5982\u4e0b\u7684\u4e00\u9996\u8bd7\u6b4c\u4ee5\u4fbf\u4e8e\u8bb0\u8bf5\uff1a
\u201c\u4e09\u4eba\u540c\u884c\u4e03\u5341\uff0870\uff09\u7a00\uff0c
\u4e94\u6811\u6885\u82b1\u4e8c\u4e00\uff0821\uff09\u679d\u3002
\u4e03\u5b50\u56e2\u5706\u6b63\u534a\u6708\uff0815\uff09\uff0c
\u9664\u767e\u96f6\u4e94\uff08105\uff09\u4fbf\u5f97\u77e5\u3002\u201d
\u300a\u5b59\u5b50\u7b97\u7ecf\u300b\u7684\u201c\u7269\u4e0d\u77e5\u6570\u201d\u9898\u867d\u7136\u5f00\u521b\u4e86\u4e00\u6b21\u540c\u4f59\u5f0f\u7814\u7a76\u7684\u5148\u6cb3\uff0c\u4f46\u7531\u4e8e\u9898\u76ee\u6bd4\u8f83\u7b80\u5355\uff0c\u751a\u81f3\u7528\u8bd5\u731c\u7684\u65b9\u6cd5\u4e5f\u80fd\u6c42\u5f97\uff0c\u6240\u4ee5\u5c1a\u6ca1\u6709\u4e0a\u5347\u5230\u4e00\u5957\u5b8c\u6574\u7684\u8ba1\u7b97\u7a0b\u5e8f\u548c\u7406\u8bba\u7684\u9ad8\u5ea6\u3002\u771f\u6b63\u4ece\u5b8c\u6574\u7684\u8ba1\u7b97\u7a0b\u5e8f\u548c\u7406\u8bba\u4e0a\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u7684\uff0c\u662f\u5357\u5b8b\u65f6\u671f\u7684\u6570\u5b66\u5bb6\u79e6\u4e5d\u97f6\u3002\u79e6
\u4e5d\u97f6\u5728\u4ed6\u7684\u300a\u6570\u4e66\u4e5d\u7ae0\u300b\uff08\u89c1\u56fe1\u4e007\u4e001\uff09\u4e2d\u63d0\u51fa\u4e86\u4e00\u4e2a\u6570\u5b66\u65b9\u6cd5\u201c\u5927\u884d\u6c42\u4e00\u672f\u201d\uff0c\u7cfb\u7edf\u5730\u8bba\u8ff0\u4e86\u4e00\u6b21\u540c\u4f59\u5f0f\u7ec4\u89e3\u6cd5\u7684\u57fa\u672c\u539f\u7406\u548c\u4e00\u822c\u7a0b\u5e8f\u3002
\u79e6\u4e5d\u97f6\u4e3a\u4ec0\u4e48\u8981\u628a\u4ed6\u7684\u8fd9\u4e00\u5957\u8ba1\u7b97\u7a0b\u5e8f\u548c\u57fa\u672c\u539f\u7406\u79f0\u4e3a\u201c\u5927\u884d\u6c42\u4e00\u672f\u201d\u5462\uff1f\u8fd9\u662f\u56e0\u4e3a\u5176\u8ba1\u7b97\u7a0b\u5e8f\u7684\u6838\u5fc3\u95ee\u9898\u662f\u8981\u201c\u6c42\u4e00\u201d\u3002\u6240\u8c13\u201c\u6c42\u4e00\u201d\uff0c\u901a\u4fd7\u4ed6\u8bf4\uff0c\u5c31\u662f\u6c42\u201c\u4e00\u4e2a\u6570\u7684\u591a\u5c11\u500d\u9664\u4ee5\u53e6\u4e00\u4e2a\u6570\uff0c\u6240\u5f97\u7684\u4f59\u6570\u4e3a\u4e00\u201d\u3002\u90a3\u4e48\u4e3a\u4ec0\u4e48\u8981\u201c\u6c42\u4e00\u201d\u5462\uff1f\u6211\u4eec\u53ef\u4ee5\u4ece\u201c\u7269\u4e0d\u77e5\u6570\u201d\u9898\u7684\u51e0\u4e2a\u5173\u952e\u6570\u5b5770\u300121\u300115\u4e2d\u627e\u5230\u5982\u4e0b\u7684\u89c4\u5f8b\uff1a
\u56fe1-7-1 \u6587\u6f9c\u9601\u56db\u5e93\u5168\u4e66\u672c\u300a\u6570\u4e66\u4e5d\u7ae0\u300b\u4e66\u5f71
\u5176\u4e2d70\u662f5\u548c7\u7684\u500d\u6570\uff0c\u4f46\u88ab3\u9664\u4f591\uff1b21\u662f3\u548c7\u7684\u500d\u6570\uff0c\u4f46\u88ab5\u9664\u4f591\uff1b15\u662f3\u548c5\u7684\u500d\u6570\uff0c\u4f46\u88ab7\u9664\u4f591\uff0c\u4efb\u4f55\u4e00\u4e2a\u4e00\u6b21\u540c\u4f59\u5f0f\u7ec4\uff0c\u53ea\u8981\u6839\u636e\u8fd9\u4e2a\u89c4\u5f8b\u6c42\u51fa\u90a3\u51e0\u4e2a\u5173\u952e\u6570\u5b57\uff0c\u90a3\u4e48\u8fd9\u4e2a\u4e00\u6b21\u540c\u4f59\u5f0f\u7ec4\u5c31\u4e0d\u96be\u89e3\u51fa\u4e86\u3002\u4e3a\u6b64\uff0c\u79e6\u4e5d\u97f6\u63d0\u51fa\u4e86\u4e58\u7387\u3001\u5b9a\u6570\u3001\u884d\u6bcd\u3001\u884d\u6570\u7b49\u4e00\u7cfb\u5217\u6570\u5b66\u6982\u5ff5\uff0c\u5e76\u8be6\u7ec6\u53d9\u8ff0\u4e86\u201c\u5927\u884d\u6c42\u4e00\u672f\u201d\u7684\u5b8c\u6574\u8fc7\u7a0b\u3002\uff08\u7531\u4e8e\u89e3\u6cd5\u8fc7\u4e8e\u7e41\u7ec6\uff0c\u6211\u4eec\u5728\u8fd9\u91cc\u5c31\u4e0d\u5c55\u5f00\u53d9\u8ff0\u4e86\uff0c\u6709\u5174\u8da3\u7684\u8bfb\u8005\u53ef\u8fdb\u4e00\u6b65\u53c2\u9605\u6709\u5173\u4e66\u7c4d\u3002\uff09\u76f4\u5230\u6b64\u65f6\uff0c\u7531\u300a\u5b59\u5b50\u7b97\u7ecf\u300b\u201c\u7269\u4e0d\u77e5\u6570\u201d\u9898\u5f00\u521b\u7684\u4e00\u6b21\u540c\u4f59\u5f0f\u95ee\u9898\uff0c\u624d\u771f\u6b63\u5f97\u5230\u4e86\u4e00\u4e2a\u666e\u904d\u7684\u89e3\u6cd5\uff0c\u624d\u771f\u6b63\u4e0a\u5347\u5230\u4e86
\u201c\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\u201d\u7684\u9ad8\u5ea6\u3002
\u4ece\u300a\u5b59\u5b50\u7b97\u7ecf\u300b\u5230\u79e6\u4e5d\u97f6\u300a\u6570\u4e66\u4e5d\u7ae0\u300b\u5bf9\u4e00\u6b21\u540c\u4f59\u5f0f\u95ee\u9898\u7684\u7814\u7a76\u6210\u679c\uff0c\u572819\u4e16\u7eaa\u4e2d\u671f\u5f00\u59cb\u53d7\u5230\u897f\u65b9\u6570\u5b66\u754c\u7684\u91cd\u89c6\u30021852\u5e74\uff0c\u82f1\u56fd\u4f20\u6559\u58eb\u4f1f\u70c8\u4e9a\u529b\u5411\u6b27\u6d32\u4ecb\u7ecd\u4e86\u300a\u5b59\u5b50\u7b97\u7ecf\u300b\u7684\u201c\u7269\u4e0d\u77e5\u6570\u201d\u9898\u548c\u79e6\u4e5d\u97f6\u7684\u201c\u5927\u884d\u6c42\u4e00\u672f\u201d\uff1b1876\u5e74\uff0c\u5fb7\u56fd\u4eba\u9a6c\u8482\u751f\u6307\u51fa\uff0c\u4e2d\u56fd\u7684\u8fd9\u4e00\u89e3\u6cd5\u4e0e\u897f\u65b919\u4e16\u7eaa\u9ad8\u65af\u300a\u7b97\u672f\u63a2\u7a76\u300b\u4e2d\u5173\u4e8e\u4e00\u6b21\u540c\u4f59\u5f0f\u7ec4\u7684\u89e3\u6cd5\u5b8c\u5168\u4e00\u81f4\u3002\u4ece\u6b64\uff0c\u4e2d\u56fd\u53e4\u4ee3\u6570\u5b66\u7684\u8fd9\u4e00\u521b\u9020\u9010\u6e10\u53d7\u5230\u4e16\u754c\u5b66\u8005\u7684\u77a9\u76ee\uff0c\u5e76\u5728\u897f\u65b9\u6570\u5b66\u53f2\u8457\u4f5c\u4e2d\u6b63\u5f0f\u88ab\u79f0\u4e3a\u201c\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\u201d\u3002
这个问题的一般解法就是构造性的.
解法的关键步骤是找到几个数: 910, 546, 1170, 105.
这几个数的特点是: 910是5, 7, 13的公倍数, 且mod 3余1; 546是3, 7, 13的公倍数, 且mod 5余1;
1170是3, 5, 13的公倍数, 且mod 7余1; 105是3, 5, 7的公倍数, 且mod 13余1.
如果取r = 910a+546b+1170c+105d, 则有r ≡ a (mod3), r ≡ b (mod5), r ≡ c (mod7), r ≡ d (mod13).
即r是同余方程组x ≡ a (mod3), x ≡ b (mod5), x ≡ c (mod7), x ≡ d (mod13)的一个解.
若s是该方程组的另一个解, 相减得r-s ≡ 0 (mod3), r-s ≡ 0 (mod5), r-s ≡ 0 (mod7), r-s ≡ 0 (mod13).
于是r-s被3, 5, 7, 13整除, 即被1365 = 3·5·7·13整除.
因此方程组的通解为x = r+1365k, k为任意整数.
本题将a = 1, b = 2, c = 4, d = 6代入, 得r = 7312.
当k = -5时r+1365k = 487取得最小正整数解.
下面解释一下那几个数是怎么找的.
首先这几个数存在的依据是3, 5, 7, 13两两互质.
数论里有个定理: 若m, n互质, 则存在整数u, v使得um+vn = 1.
可以看到um = 1-vn, 是m的倍数且mod n余1.
至于如何计算, 因为这道题的数还算比较小, 所以逐个验算也不困难.
还可以借助同余式稍微简化一点, 例如由3·5·13 ≡ 6 (mod 7), 只需找6的倍数使其mod 7余1.
由6·6 ≡ 1 (mod 7), 可取1170 = 6·3·5·13 ≡ 6·6 ≡ 1 (mod 7).
如果不是mod 7, 而是mod 97这样更大的数, 计算的效率还是比较低.
相对有效的办法是用辗转相除, 这里先不介绍了.
另外对于一组给定的模数, 相应的数只要计算一次, 结果能适用于不同余数的情况.
个人认为这个题一次解2个比一下解4个方程有效.
先解x ≡ 1 (mod3), x ≡ 2 (mod5). 取两个数-5和6, 得x ≡ -5·1+6·2 = 7 (mod 3·5).
再解x ≡ 7 (mod 3·5), x ≡ 4 (mod 7). 取两个数-14和15, 得x ≡ 67 (mod 3·5·7).
最后解x ≡ 67 (mod 3·5·7), x ≡ 6 (mod 13). 取两个数-104和105, 得x ≡ 487 (mod 3·5·7·13).
这里再说明一下.
由2·3-1·5 = 1, 6 = 2·3是3的倍数并mod 5余1. 由同样的等式, -5 = -1·5是5的倍数并mod 3余1.
引入负数使我们能由一个等式得到所需要的两个数. 同样的考虑在3·5·7和13时作用最明显.
由3·5·7-8·13 = 1, 105是3·5·7的倍数并mod 13余1, 而-104是13的倍数并mod 3·5·7余1.
如果非要取正整数, 那最小就是1365-104 = 1261, 计算量要大一些.
一个数的2倍，除以3余2，除以5余4，除以13余12，这个数正好是除以3余1，除以5余2，除以13余6
所以，（3*5*13-1）/2=97正好是除以3余1，除以5余2，除以13余6
所以，
97+3*5*13*n=97+195*n n=0,1,2,3……都是正好除以3余1，除以5余2，除以13余6
97除以7余6
195除以7余6
97+195*2除以7的余数，与6+6*2=18除以7的余数相同，18除以7余4
所以，
97+195*2=487正好是除以3余1，除以5余2，除以7余4，除以13余6
487+3*5*7*13*n=487+1365*n n=0,1,2,3……都是正好除以3余1，除以5余2，除以7余4，除以13余6
487是最小的
先计算“每3人一列余1人、5人一列余2人、7人一列余4人”
按数学家程大位诗歌算法：
三人同行七十稀，五树梅花廿一枝，
七子团圆月正半，除百零五便得知。
其值为
70×1+21×2+15×4=172=105+67
67是最小数
那么所有105乘以正数+67都符合要求
可知105÷13得8余1,67÷13得5余2
那么105每增加一倍，即增加余数1，显然增加4倍，余数即是6
那么这个数应该是105×4+67=487
不知道是不是这样
x≡
1（mod3)
2（mod5)
4（mod7)
6（mod13)
解:以下用==表示同余号≡.
并以向量形式描述上题,即
x==(1,2,4,6) mod (3,5,7,13)
先求得
x1==(1,0,0,0) mod (3,5,7,13)
x2==(0,1,0,0) mod (3,5,7,13)
x3==(0,0,1,0) mod (3,5,7,13)
x4==(0,0,0,1) mod (3,5,7,13)
再进行线性叠加,即得解:
x=x1+2x2+4x3+6x4. mod lcm(3,5,7,13)
此处lcm表示最小公倍数,也用中括号代替,记成[3,5,7,13]
对于两两互质的数,其lcm就是它们的积.
注:
1:我们可以看到,完全可以用矩阵论\线性代数理论来处理同余问题;
2:x1,x2,x3,x4并列,构成单位矩阵;
3:x可以表示成两个向量的内积(点积,标积,数量积), 即x=(1,2,4,6)·(x1,x2,x3,x4)
4: 以上就是中国剩余定理的本质性描述.插值法中的拉格朗日插值,也是这样的原理.
5:这种方案,x1,x2,x3,x4的计算是同步并行的.
6:类以牛顿插值,还可以使用以下过程:
x1=(1,1,1,1) mod (3,5,7,13)
x2=(0,1,1,1) mod (3,5,7,13)
x3=(0,0,2,2) mod (3,5,7,13)
x4=(0,0,0,2) mod (3,5,7,13)
再取x=x1+x2+x3+x4.
也就是:
x1=1
x2=(0,1) mod (3, (5,7,13))
x3=(0,2) mod ((3,5), {7,13))
x4==(0,2) mod ((3,5,7), 13)
其矩阵形式是一个上三角矩阵.
7: 中国剩余定理使用了单位向量.事实上,为便于计算,可以不必使用单位向量.
过程如下:
x1==(1,0,0,0) mod (3,5,7,13)
x2==(0,2,0,0) mod (3,5,7,13)
x3==(0,0,4,0) mod (3,5,7,13)
x4==(0,0,0,6) mod (3,5,7,13)
再取x=x1+x2+x3+x4.
在下面的过程中,会看到此种方式对计算的简化.因此,这是对中国剩余定理的计算过程的一种简单的改进,也有助于我们打破对中国剩余定理的迷信,进一步认识到其本质.
8:洪伯阳同余表示:
ax==b mod m, 记成 x=b/a mod m
并且,可以将 b/a作为带分数处理; 可以将b/a 同时乘除一个与m 互质的数而保持同解; 可以将b,a替换为它关于模m的同余类中的任一个等价元.即b'==b mod m, 可以用b'取代b而同余式保持同解.
可以在上式用使用比例的性质.
9: 为直观,我常用|||取代同余号mod.
x==
1 ||| 3
2 ||| 5
4 ||| 7
6 ||| 13
基于注释7和8, 同余式的解可以如下表示,
==
{$$$
(5*7*13) * [1/(5*7*13) mod 3]+
(3*7*13) * [ 2/(3*7*13) mod 5]+
(3*5*13) * [4/(3*5*13) mod 7]+
(3*5*7) * [ 6/(3*5*7) mod 13]
$$$}
==进而,对上面的过程,我有以下的简化改进记法,称为模积表示法,用以解同余式.
1/(5*7*13) @ 3
2/(3*7*13) @ 5
4/(3*5*13) @ 7
6/(3*5*7) @ 13
==(开始使用洪伯阳表示的性质,并将乘号改动为逗号简化书写,改为逗号不是必须的,我在草稿纸常这样写 )
1/(-1,1,1) @ 3
2/(21==1,-2) @5
4/(15==1,13==-1)@7
6/(105==1) @13
==
-1 @ 3
-1 @5
-4 @7
6 @ 13
==
[注意体会模积表示; 注意上面各式是对称的,位置与计算次序可以任意;注意任一行,@符号前的内容可以关于@后的模取代为同余类的任意等价元]
-8==
7 @15
-4 @ 7
6 @ 13
==
49-60 @ 15*7==
-11 @ 105
6 @ 13
==630-143 MOD 13*105
== 487 mod 1365
以上过程,在了解了中国剩余定理的本质和改进方案.熟悉了洪伯阳表示及何冬州模积表示之后,
能结合心算或简化中间过程,快速计算出同余式组的解.
注意到各式的对称性,即无先后之分,用多种过程来计算与验证,曾经是我在2005年初发现这种方法时的一种乐趣.
利用洪伯阳表示的性质,进行笔算求幂余和解大模的同余式,也很方便.
这种过程我曾考虑过自动编程方案,仍在思考之中.
外一则:
对于同余号 mod m, 可以认为它与一个可平移到等式两端任意同阶的项上的一个代数和项: ±mk.
以此破除对同余概念的迷惑.同余式与不定方程式是完全等效的.
相关内容, 请搜索:
wsktuuytyh 同余新概念
关于一次不定方程的简化解法,请搜索
不定方程解法 wsktuuytyh
绛旓細棣栧厛鎴戝厛姹5銆9銆13銆17鍏嶆暟9945(娉:5銆9銆13銆17涓や袱浜掕川鏁存暟鏁呭叾鍏嶆暟浜涙暟绉)鍚庡啀鍔39948()鍗冨墠銆婂瓩绠楃粡銆嬮亾绠楁湳棰:浠婄墿鐭ュ叾鏁颁笁涓夋暟鍓╀簩浜斾簲鏁板墿涓変竷涓冩暟鍓╀簩闂墿鍑犱綍鎸夌収浠婅:鏁伴櫎3浣2闄5浣3闄7浣2姹傛暟闂绉闊╀俊鐐瑰叺.褰㈢被闂鍒濈瓑鏁拌瑙鍚屼綑寮 鈶 鏁伴櫎3浣2闄4浣1闂暟闄...
绛旓細杩欎釜绠楁硶鍦ㄦ垜鍥芥湁璁稿鍚嶇О锛屽鈥闊╀俊鐐瑰叺鈥濓紝鈥滈璋风畻鈥濓紝鈥滈殧澧欑畻鈥濓紝鈥滃壀绠℃湳鈥濓紝鈥滅濂囧绠椻濈瓑绛夛紝棰樼洰涓瑙ｆ硶閮借浇浜庢垜鍥藉彜浠ｉ噸瑕佺殑鏁板钁椾綔銆婂瓩瀛愮畻缁忋嬩腑銆備竴鑸涓鸿繖鏄笁鍥芥垨鏅嬫椂鐨勮憲浣滐紝姣斿垬閭︾敓娲荤殑骞翠唬瑕佹櫄杩戜簲鐧惧勾锛岀畻娉曞彛璇璇楀垯杞戒簬鏄庢湞绋嬪ぇ浣嶇殑銆婄畻娉曠粺瀹椼嬶紝璇椾腑鏁板瓧闅愬惈鐨勫彛璇鍓嶉潰宸茬粡...
绛旓細鈥滀粖鏈夌墿涓嶇煡鍏舵暟锛屼笁涓夋暟涔嬪墿浜岋紝浜斾簲鏁颁箣鍓╀笁锛屼竷涓冩暟涔嬪墿浜岋紝闂墿鍑犱綍锛熲濇寜鐓т粖澶╃殑璇濇潵璇达細涓涓暟闄や互3浣2锛岄櫎浠5浣3锛岄櫎浠7浣2锛姹傝繖涓鏁.杩欐牱鐨勯棶棰橈紝涔熸湁浜虹О涓衡闊╀俊鐐瑰叺鈥.瀹冨舰鎴愪簡涓绫婚棶棰橈紝涔熷氨鏄垵绛夋暟璁轰腑瑙鍚屼綑寮.杩欑被闂鐨勬湁瑙ｆ潯浠跺拰瑙ｇ殑鏂规硶琚О涓衡滀腑鍥藉墿浣欏畾鐞嗏濓紝杩欐槸...
绛旓細鍦ㄨ崏绋跨焊涓婏紝鍙互鍐欏緱寰堢畝娲侊紱鍙互鐪佸幓*1锛涘彲浠ラ厤鍚堝績绠楋紝寰堝揩鐨勬眰瑙ｅ拰璁＄畻鍚屼綑寮忋傜被浼肩殑涔犻瑙ｇ瓟锛屽強鏈緥鐨勫叾瀹瑙ｆ硶锛屽強鍒╃敤娲集闃鐨勫悓浣寮忚娉曚綔鏇寸畝娲佺殑涓绔欏紡鍚屼綑寮忚В娉曟弿杩帮紝鎴戝啓鍒颁簡鎴戠殑鏈鏂板崥鏂囥闊╀俊鐐瑰叺鍏紡-鍐嶆璇﹁涓浗鍓╀綑瀹氱悊銆嬩腑锛屼緵鍙傝冦傝繖閲屽彧璇翠簡妯′负3,5,7鐨勬儏鍐碉紱鍏跺疄锛屽浜庝换鎰...
绛旓細涔熷彨涓浗鍓╀綑瀹氱悊銆傘婂瓩瀛愮畻缁忋嬩腑鈥滅墿涓嶇煡鏁扳濋棶棰樿锛氣滀粖鏈夌墿锛屼笉鐭ュ叾鏁帮紝涓変笁鏁颁箣鍓╀簩锛屼簲浜旀暟涔嬪墿涓夛紝涓冧竷鏁颁箣鍓╀簩锛岄棶鐗╁嚑浣曪紵鈥濆嵆琚笁闄や綑浜岋紝琚簲闄や綑涓夛紝琚竷闄や綑浜岀殑鏈灏忔暣鏁般傝繖涓棶棰樼О浣滃瓩瀛愰棶棰橈紝淇楃О闊╀俊鐐瑰叺銆傚叾姝ｇ‘瑙ｆ硶鍙仛瀛欏瓙鍓╀綑瀹氱悊銆備腑鍥芥妸瑙ｆ硶缂栨垚鍥涘彞姝岃瘈锛氣滀笁浜哄悓鎬...
绛旓細闊╀俊鐐瑰叺锛屽澶氱泭鍠勬垜鍥芥眽浠ｆ湁浣嶅ぇ灏,鍚嶅彨闊╀俊.浠栨瘡娆￠泦鍚堥儴闃,鍙姹傞儴涓嬪厛鍚庢寜l锝3銆1锝5銆1锝7鎶ユ暟,鐒跺悗鍐嶆姤鍛婁竴涓嬪悇闃熸瘡娆℃姤鏁扮殑浣欐暟,浠栧氨鐭ラ亾鍒颁簡澶氬皯浜恒1銆佷粬鐨勮繖绉嶅阀濡欑畻娉,浜轰滑绉颁负楝艰胺绠,涔熷彨闅斿绠,鎴栫О涓洪煩淇＄偣鍏,澶栧浗浜鸿繕绉板畠涓衡滀腑鍥藉墿浣欏畾鐞嗏濄2銆佸埌浜嗘槑浠,鏁板瀹剁▼澶т綅鐢ㄨ瘲姝...
绛旓細棣栧厛锛岃鐭ラ亾锛屼笉鏄换浣曠殑A锛孊锛孋閮藉彲浠ユ眰鍑篨鐨勩侫锛孊锛孋蹇呴』浜掕川锛屼篃鍙簰绱犮傜劧鍚庢眰鍑轰笁鑰呯殑鏈灏忓叕鍊嶆暟X0锛屽啀姹傚嚭涓や袱鐨勫叕鍊嶆暟锛屼笖闄や互绗笁鏁拌浣欎竴锛屽緱X1锛孹2锛孹3銆俋锛漀*X1+M*X2+L*X3-nX0 涓句緥锛屽師濮嬬殑闊╀俊鐐瑰叺鏄疉锛3锛孊锛5锛孋锛7锛屼簰璐 鏈灏忓叕鍊嶆暟鏄疿0锛3*5*7锛105锛...
绛旓細绉︾帇鏆鐐瑰叺闂鍜闊╀俊涔辩偣鍏甸棶棰橈紝閮芥槸鍚庝汉瀵圭墿涓嶇煡鍏舵暟闂鐨勪竴绉嶆晠浜嬪寲銆傜墿涓嶇煡鍏舵暟闂鍑鸿嚜涓鍗冨叚鐧惧勾鍓嶆垜鍥藉彜浠ｆ暟瀛﹀悕钁椼婂瓩瀛愮畻缁忋嬨傚師棰樹负锛"浠婃湁鐗╀笉鐭ュ叾鏁帮紝涓変笁鏁颁箣浜岋紝浜斾簲鏁颁箣涓夛紝涓冧竷鏁颁箣浜岋紝闂墿鍑犱綍锛"杩欓亾棰樼殑鎰忔濇槸锛氭湁涓鎵圭墿鍝侊紝涓嶇煡閬撴湁鍑犱欢銆傚鏋滀笁浠朵笁浠跺湴鏁帮紝灏变細鍓╀笅涓...
绛旓細2锛岄煩淇＄偣鍏靛彧鏄滀笁涓夋暟涔嬩綑浜岋紝浜斾簲鏁颁箣浣欎笁锛屼竷涓冩暟涔嬩綑浜屸濓紝杩欑姣旇緝灏忕殑鏁板硷紝濡傛灉鍙樻垚姣旇緝澶х殑鏁帮紝灏遍渶瑕鍚屼綑鐞嗚鏉ヨ绠椾簡銆傞棶棰樹簩锛氶煩淇＄偣鍏靛澶氱泭鍠勭殑瀵撴剰鏄粈涔堬紵鏉ュ舰瀹逛粈涔堬紵 闊╀俊鐐瑰叺鐨鎴愯鏉ユ簮娣畨姘戦棿浼犺銆傚父涓庡澶氱泭鍠勬惌閰嶏紒瀵撴剰瓒婂瓒婂ソ锛佸垬閭﹂棶浠栵細鈥滀綘瑙夊緱鎴戝彲浠ュ甫鍏靛灏戯紵鈥濋煩淇★細...
绛旓細涓浗鍓╀綑瀹氱悊锛屽張鍙腑鍥戒綑鏁板畾鐞嗭紝鏄暟璁轰腑鐨勪竴涓叧浜庝竴鍏冪嚎鎬鍚屼綑鏂圭▼缁勭殑瀹氱悊锛岃鏄庝簡涓鍏冪嚎鎬у悓浣欐柟绋嬬粍鏈夎В鐨勫噯鍒欎互鍙婃眰瑙ｇ殑鏂规硶銆備篃绉颁负瀛欏瓙瀹氱悊锛屽彜鏈"闊╀俊鐐瑰叺"锛"瀛欏瓙瀹氱悊"锛"姹備竴鏈"(瀹嬫矆鎷)锛"楝艰胺绠"锛"闅斿绠"锛"鍓鏈"(瀹嬫潹杈)锛"绉︾帇鏆楃偣鍏"涔嬪悕銆傚師鏂囧涓嬶細鏈夌墿涓嶇煡鍏舵暟锛屼笁涓夋暟...
