余数（英文：remainder），是数学中的用语。在整数除法运算中，如果要让商是整数，这样的除法不是总能除尽的。如果商数与除数相乘之后不会大于被除数，那么被除数与这个乘积之差叫做余数。余数有几个常见的基本性质，如余数等于被除数减去除数与商之积；余数是小于除数的整数等。

余数的概念有着悠久的历史，早在公元前300年古希腊数学家欧几里得（Euclid）所著的《几何原本》中就已经有了辗转相除法的陈述。中国的《九章算术》大约成书于东汉初年（公元一世纪），书中把最大公约数称为“等数”，求两个数的最大公因数要“以少减多，更相减损”，这种方法与欧几里得的辗转相除法是相同的。随着对数学问题的深入研究，在余数的基础上产生了同余的概念，即多个整数被一个自然数除所得的余数相同。同余概念丰富了余数在数学上的研究内容。与余数相关的定理也随之产生，如带余除法定理、孙子定理、费马小定理、欧拉定理等。这些定理应用于整除问题的解决中，如带余除法可以求解最大公因数。

余数及其相关定理在实际问题中应用广泛，如计算机、工程学、密码学等领域。在计算机领域，进制数的转换依赖于余数的计算；在工程学领域，复合伪码测距是基于单一伪码测距原理和中国的“中国剩余定理”的深空测距技术之一。

整除的定义：设都是整数，，如果存在一个整数，它能使成立，那么说能被整除，记为

余数定义：在整数的除法中，如果商数与除数相乘之后不会大于被除数，那么被除数与这个乘积之差就叫做余数。

例如：带余除法，其中是被除数，是除数，为商，是余数。

本文谈论的余数在带余除法的定义之下，被除数、除数为负数的情况不予考虑。

公元前300年古希腊数学家欧几里得所著的《几何原本》第九章命题中有一种著名的算法——辗转相除法，它是数论和代数中求两数（或两式）的最大公约数的重要方法，它的理论基础是带余除法。

中国的《九章算术》大约成书于东汉初年（公元100年），书中把最大公因数称为“等数”，求两个数的最大公因数要“以少减多，更相减损”，这种方法与欧几里得的辗转相除法是相同的。《孙子算经》大约成书于公元400年到500年之间，书中第二十六题“今有物不知其数”是关于孙子定理求解一次同余方程组问题的最早记载。

同余的定义：一般地，若两个整数被一个大于的正整数除得的余数相同，则称和关于模同余；若余数不同，则称和关于模不同余。

用数学语言可表示为：

设，当时，，则称和关于模同余，记作，读作同余模；

否则，称和关于模不同余，记作，读作不同余模

如果是整数，且和都是正整数，若，那么叫做的公约数。公因数中的最大的那一个数叫做的最大公因数，最大公因数是其他公因数的倍数。如果是的最大公因数，记为

质数的定义：一个大于的正整数，如果只能被和它本身整除，那么这样的正整数叫做质数（素数）。

例如：都是质数。

如果一个正整数除了能被和它本身整除外，还能被另外的正整数整除，那么这样的正整数叫做复合数。

互质的定义：如果几个正整数的最大公因数等于，那么这几个正整数是互质（互素）的，即如果，则是互质的；如果中的每一个数与另外的每一个数都互质，则称两两互质。

一般地，已知两个数 是整数，是正整数，存在唯一的两个整数，使满足条件：

其中称为被除数，称为除数，称为不完全商，称为余数。

设是两两互质的正整数。

令则有同余方程组

，有唯一解

这里

设为整数，为质数，若不能被整除，则

即

定义：设都是整数，且及，是欧拉函数，它表示小于且与互质的正整数个数，则

由欧拉定理可以得出：若，则同余方程的解为

方法：设和都是正整数，且，其中和都是正整数，那么和的最大公因数等于和的最大公因数，即

已知存在自然数和，使得

①如果，则有，所以和的最大公因数就是，如果，则有，再以除，得

由得

②如果，则和的最大公因数就是, 所以。如果，有，再以除可得

③如果，则，所以

④如果，再以除，以此辗转相除。

由于和都是自然数，所以一定存在有一个正整数，使得经过次辗转相除后有 ，但，这时就是的最大公约数，即

例题 求和的最大公因数。

解：

所以

例1 在大于的自然数中，共有多少个整数被除后，商与余数相等。

解：已知被除数=余数+除数×商。

可得：所求的数=47×商+余数。因为商与余数相等，故所求的数=47×余数+余数=48×余数。

且余数是小于除数的整数，即余数＜47，而

所以余数的取值范围在到，即只能取值

答：所求的整数有，一共5个数。

例2 被自然数除时，余数都相等，那么被除，得到的余数是多少。

解：根据同余的性质，若两个整数被同一正整数除，余数相等，则这两个整数的差是除数的倍数。

由上述性质，可知与都是的倍数，而与的最大公因数是，又故。于是被除，商是，余数为

多项式的定义：设是一个数域，是一个文字，形式表达式称为系数在数域上的一元多项式，或称数域上的一元多项式，是数域中的数，式中是一个自然数，多元多项式是一元多项式的推广。

例如：是有理数域上的一元多项式。

多项式的整除性：假定与是两个多项式，若存在一个多项式，使得，则称整除，记为。这时叫做的因式，叫做的倍式。

一元多项式的整除性具有以下几个常用性质：

假如与是任意两个多项式，并且，那么一定存在多项式与，使得，其中的次数小于的次数或者，并且这样的与是唯一确定的。多项式与，分别叫做用除所得的商式与余式。

十进制数与二进制数的转换

十进制数是最常用的数的进制，基本思想为“逢十进一”，当一位数不够表示时则用二位数表示。十进制数转换为二进制数通常采用的方法是商余法，把所要转换的十进制数除以求余数，余数即为相应二进制数的最低位，然后对商继续除，求得的余数为相应二进制数的次低位，以此重复下去，直到所得到的商小于，而此时的商就是相应二进制数的最高位。

例如：十进制数的位权表示法，

复合伪码测距是能在探月中解决地月距离范围内对探测器的跟踪又可解决距离模糊的测距的深空探测技术，基于单一伪码测距原理和中国的“孙子定理”。

复合伪码是由若干个周期为的且互为质数的单一子码按设计逻辑组合并形成所要求长度的测距码。捕获测距码时，采用本地码和回波码的码相关技术，这与的码相关测距的原理是相同的。采用复合伪码测距技术，只要复合伪码的周期满足一定条件，就可实现对月球探测器的快速跟踪和无模糊测距。

密码学的作用是使得通信双方在不安全的信道中以除通信双方之外的人不能明白和理解的方式进行通信。现代的密码技术和应用涵盖了数据处理的所有方面，而在区块链技术的应用和开发中密码技术是重点，一旦区块链加密方法被破解，则区块链的不可篡改性将消失。

非对称加密算法常用的是由三位数学家共同设计完成并由三人的名字命名的算法。的加密算法为

，解密算法为，公钥，私钥。加密算法的实现原理应用了同余的概念和欧拉函数等。理论上破解算法小于256位的密钥只需要几个小时，但是破解2048位的密钥需要耗费传统电脑10亿年的时间。