中国剩余定理详解

引入

我国古代数学著作《孙子算经》中有一道题目,它的描述是这样的

今有物不知其数,三三数之余二;五五数之余三;七七数之余二。问物几何?

这道题用现代数学理论来看,无非就是解一个方程

\begin{cases}x\equiv 2\left( mod\ 3\right) \\ x\equiv 3\left( mod\ 5\right) \\ x\equiv 2\left( mod\ 7\right) \end{cases}

那么这个方程怎么解呢?

这需要用到我们祖先的伟大创造——中国剩余定理

中国剩余定理

在很久以前,数学领域还没有像扩展欧几里得这种东西。对于这个问题,我们祖先采用了构造的方法

构造过程如下

首先考虑三个特殊方程

\begin{cases}x\equiv 1\left( mod\ 3\right) \\ x\equiv 0\left( mod\ 5\right) \\ x\equiv 0\left( mod\ 7\right) \end{cases}

\begin{cases}x\equiv 0\left( mod\ 3\right) \\ x\equiv 1\left( mod\ 5\right) \\ x\equiv 0\left( mod\ 7\right) \end{cases}

\begin{cases}x\equiv 0\left( mod\ 3\right) \\ x\equiv 0\left( mod\ 5\right) \\ x\equiv 1\left( mod\ 7\right) \end{cases}

他们的特殊解

那第一个方程来说,它实际上等同于解一个同余式

 35y\equiv 1\left( mod\ 3\right)

因为x一定是5*7=35的倍数

化简一下当面的式子

2y\equiv 1\left( mod\ 3\right)

我们不难得出解y=2,此时x=70

同理,对于第二第三个式子我们可以运用相同的方法求解

\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}=70\begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}=21\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}=15

那么最终的答案为

\begin{pmatrix} 2 \\ 3 \\ 2 \end{pmatrix}=2\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}+3\begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}+2\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}

=2\times 70+3\times 21+2\times 15\equiv 23\left( mod\ 105\right)

我们这样就可以求出解了。

但是这仅仅是三个式子的情况,如果推广到$r$个呢?

其实是一样的,都是利用构造的手段。

下面我们来推广一下。

设有r个同余式,其中m_i两两互素,注意m必须两两互素,否则答案错误。其实不互素也可以搞不过要用更神奇的东西

N=\prod ^{r}_{i=1}m_{i}

对于同余方程组

\begin{cases}x\equiv b_{1}\left( mod\ m_{1}\right) \\ x\equiv b_{2}\left( mod\ m_{2}\right) \\ \ldots \\ x\equiv br\left( mod\ m_r\right) \end{cases}

在模$N$同余的意义下有唯一解

这个方程怎么解呢?

我们仍然像前面一样,考虑构造

\begin{cases}x\equiv 0\left( mod\ m_{1}\right) \\ \ldots \\ x\equiv 0\left( mod\ m_{i-1}\right) \\ \ldots \\ x\equiv 1\left( mod\ m_{i}\right) \\ \ldots \\ x\equiv 0\left( mod\ m_{i+1}\right) \\ \ldots \\ x\equiv0\left( mod\ M_{r}\right) \end{cases}

像上面那样,我们令$x=(N/m_i)*y$

那么我们现在需要解出

\left( N/m_{i}\right) y\equiv 1\left( mod\ m_{i}\right)

这个东西怎么搞呢?

聪明的你肯定已经知道啦,这不就是个逆元嘛,想怎么搞就怎么搞

如果你不知道怎么搞的话可以看这里

那么方程的解为x_{0}=b_{1}x_{1}+b_{2}x_{2}+\ldots +b_{r}x_{r}\left( mod\ N\right)

怎么样?似不似很简单?

例题

有了上面的知识代码应该不难写

放一道水题

http://poj.org/problem?id=1006

题解(很久之前做的)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏海天一树

Python从0实现朴素贝叶斯分类器

朴素贝叶斯算法是一个直观的方法,使用每个属性归属于某个类的概率来做预测。你可以使用这种监督性学习方法,对一个预测性建模问题进行概率建模。 给定一个类,朴素贝叶斯...

73120
来自专栏Pytorch实践

简单的搜索引擎搭建

24670
来自专栏媒矿工厂

HDR关键技术:HEVC/H.265编码方案

前文我们对HEVC的HDR编码优化技术做了介绍,侧重编码性能的提升。本章主要阐述HEVC中HDR/WCG相关的整体编码方案,包括不同应用场景下的HEVC扩展编码...

67900
来自专栏Petrichor的专栏

论文阅读: YOLOv2

本文获得了CVPR 2017 Best Paper Honorable Mention:

32640
来自专栏鸿的学习笔记

八个方法干掉不平衡集

I have a binary classification problem and one class ispresent with 60:1 ratio i...

12120
来自专栏杨熹的专栏

机器学习&人工智能博文链接汇总

? 争取每天更新 ? 126 ? ---- 蜗牛的历程: [入门问题] [机器学习] [聊天机器人] [好玩儿的人工智能应用实例] [Tensor...

37360
来自专栏机器之心

资源 | 用Python和NumPy学习《深度学习》中的线性代数基础

23830
来自专栏目标检测和深度学习

资源 | 用Python和NumPy学习《深度学习》中的线性代数基础

11320
来自专栏本立2道生

伪随机数生成算法

伪随机数生成算法在计算机科学领域应用广泛,比如枪击游戏里子弹命中扰动、数据科学里对样本进行随机采样、密码设计、仿真领域等等,背后都会用到伪随机数生成算法。

38520
来自专栏IT派

六行代码!完成你的第一个机器学习算法

Google出了一个面向新手的机器学习教程,每集六七分钟,言简意赅,只掌握最基础的Python语法知识,便可以实现一些基本的机器学习算法。接下来我准备分几次...

39660

扫码关注云+社区

领取腾讯云代金券