Wolfram Mathematica Documentation Center
DOCUMENTATION CENTER SEARCH
New to Mathematica? Find your learning path »
虚拟全书 > 数学和算法 > 数学函数 > 整数和数论中的函数 >
MATHEMATICA 教程
相关教程 »|更多关于 »|函数 »

整数和数论中的函数

Mod[k,n]k 模 n （ k 除以 n 的余数）
Quotient[m,n]m 和 n 的商 （ 的整数部分）
QuotientRemainder[m,n]商和余数的列表
Divisible[m,n]检测 m 是否被 n 整除
CoprimeQ[n1,n2,...]检测 是否成对互质
GCD[n1,n2,...], , ... 的最大公约数
LCM[n1,n2,...], , ... 的最小公倍数
KroneckerDelta[n1,n2,...]如果所有的 都相等，那么 Kronecker delta 等于1，否则，等于 0
IntegerDigits[n,b]b 进制下 n 的位数
IntegerExponent[n,b]整除 n 的 b 次幂的最大值

一些整数函数.

17 除以 3 的余数.
In[1]:=
Click for copyable input
Out[1]=
17/3 的整数部分.
In[2]:=
Click for copyable input
Out[2]=
Mod 也可用于实数.
In[3]:=
Click for copyable input
Out[3]=
由 Mod 得到的结果，其符号与第二个自变量的符号相同.
In[4]:=
Click for copyable input
Out[4]=
对于任意整数 a 和 b，b*Quotient[a, b]+Mod[a, b] 等于 总是成立的.
Mod[k,n]结果在 0 到 之间
Mod[k,n,1]结果在 1 到 n 之间
Mod[k,n,-n/2]结果在 到 之间
Mod[k,n,d]结果在 d 到 之间

带偏心距的整数余数.

特别当使用 Mod 来获得部分对象的索引时，指定一个偏心距常常是方便的.
在对列表循环处理下，提取列表的第 18 个元素.
In[5]:=
Click for copyable input
Out[5]=
最大公约数函数 GCD 给出整除所有 的最大整数. 当输入两个整数的比时，Mathematica 使用 GCD 约去公因式，并给出最简有理数.
最小公倍数函数 LCM 给出包含每个 的所有因子的最小整数.
整除 24 和 15 的最大整数是 3.
In[6]:=
Click for copyable input
Out[6]=
Kronecker delta 函数 KroneckerDelta 当 全相等时等于1，否则等于0. 可以看作为一个全对称的张量.
这里给出一个秩为 3 的全对称张量
In[7]:=
Click for copyable input
Out[7]=
FactorInteger[n]n 的素因子和相应指数的列表
Divisors[n]整除 n 的整数列表
Prime[k]第 k 个素数
PrimePi[x]小于等于 x 的素数的个数
PrimeQ[n]如果 n 为素数时，给出 True；否则为 False
PrimeNu[n]n 中不同素数 的个数
PrimeOmega[n]计算关于 n 的重数（multiplicities） 的素因子数目.
LiouvilleLambda[n]Liouville 函数
MangoldtLambda[n]von Mandgoldt 函数
FactorInteger[n,GaussianIntegers->True]
高斯整数 n 的高斯素数因子和相应指数的列表
PrimeQ[n,GaussianIntegers->True]n 为高斯素数时得 True，否则得 False

整数因子分解和相关函数.

给出 24 的所有因子为 ，. 每个子列表的第一个元素是因子；第二个元素是其指数.
In[8]:=
Click for copyable input
Out[8]=
这是一个较大的整数的因子.
In[9]:=
Click for copyable input
Out[9]=
应该认识到，按照现代数学的观点，整数因子分解是本质上困难的计算问题. 因此，用户能容易地输入一个整数，而 Mathematica 对其分解因子可能要花费天文数字长度的时间. 只要用户给出的整数位数小于50，FactorInteger 将不会有任何困难. 然而，在一些特殊情况下，它能处理长得多的整数.
这是一个相当特殊的长整数.
In[10]:=
Click for copyable input
Out[10]=
Mathematica c能容易地分解这个特殊整数.
In[11]:=
Click for copyable input
Out[11]=
尽管 Mathematica 可能分解不了大整数，但是它常常能检测该整数是否为素数. 此外，Mathematica 有一个寻找第 个素数的快速方法.
检测一个数是否是素数常常比分解它的因子快得多.
In[12]:=
Click for copyable input
Out[12]=
这是前 100 个素数的图形.
In[13]:=
Click for copyable input
Out[13]=
这是第一百万个素数.
In[14]:=
Click for copyable input
Out[14]=
尤其，在数论中，知道素数的分布比知道它们的值常常更加重要. 函数 PrimePi[x] 给出小于或者等于 的素数个数 .
给出小于10亿的素数个数.
In[15]:=
Click for copyable input
Out[15]=
PrimeNu 给出不同素数的数目.
In[16]:=
Click for copyable input
Out[16]=
PrimeOmega 给出计算重数（multiplicities） 关于 n 的素因子数目.
In[17]:=
Click for copyable input
Out[17]=
Liouville 函数给出 ，其中 是计算重数（multiplicity）的素因子数目.
In[18]:=
Click for copyable input
Out[18]=
该曼戈尔特函数（Mangoldt function）返回以素数幂为基的对数，或者当合成的时候，返回零.
In[19]:=
Click for copyable input
Out[19]=
默认情况下，FactorInteger 只允许实整数. 但通过设置选项 GaussianIntegers->True，它也能处理高斯整数——实部和虚部均为整数的复数. 正如它能唯一地分解出实素数一样，它也能唯一地分解出高斯素数. 然而，在高斯素数的选择中有一些潜在的二义性. 在 Mathematica 中，除了初始的 和 以外，因子总是被选为正实部和非负虚部.
在高斯整数上，2能分解为 .
In[20]:=
Click for copyable input
Out[20]=
这里是一个高斯整数的所有因子.
In[21]:=
Click for copyable input
Out[21]=
PowerMod[a,b,n] 模 n
DirichletCharacter[k,j,n]狄雷克莱特征
EulerPhi[n]欧拉 totient 函数
MoebiusMu[n]莫比乌斯函数
DivisorSigma[k,n]除数函数
DivisorSum[n,form]对于所有整除 n 的 i， 的和
DivisorSum[n,form,cond]仅包含对 给出 True 的约数的和
JacobiSymbol[n,m]雅可比符号
ExtendedGCD[n1,n2,...], , ... 的扩展最大公约数
MultiplicativeOrder[k,n]k 模 n 的多重阶
MultiplicativeOrder[k,n,{r1,r2,...}]带有余数 的广义多重阶
CarmichaelLambda[n]卡米切尔函数
PrimitiveRoot[n]n 的一个原根

数论中的一些函数.

模幂函数 PowerMod 给出与 Mod 当 b>0 时的相同的结果. 但是，PowerMod 更有效，因为它避免生成 的完全形式.
用户可以使用 PowerMod 不仅能求出正模幂，也能求出模逆. 对于负数 b，PowerMod 给出，如果可能的话，一个整数 使得 . （当这样的整数存在时，它是唯一的模 n）. 如果不存在这样的整数 ，Mathematica 就使得 PowerMod 不再计算.
PowerMod 等价于先使用 Power，再使用 Mod，但是更有效率.
In[22]:=
Click for copyable input
Out[22]=
这里给出3模7的模逆.
In[23]:=
Click for copyable input
Out[23]=
3乘以该模逆7得1，与期望的相同.
In[24]:=
Click for copyable input
Out[24]=
这里寻找最小非负整数 使得 等于 3 模 11.
In[25]:=
Click for copyable input
Out[25]=
这里验证该结果.
In[26]:=
Click for copyable input
Out[26]=
这里返回所有满足关系的小于11的整数.
In[27]:=
Click for copyable input
Out[27]=
如果 d 不具有平方根模 n，PowerMod 将保持未被计算，并且 PowerModList 将返回一个空列表.
In[28]:=
Click for copyable input
Out[28]=
In[29]:=
Click for copyable input
Out[29]=
这里检查 3 不是 5 的模平方.
In[30]:=
Click for copyable input
Out[30]=
即使对于大模数，平方根的计算也可以相当快.     
In[31]:=
Click for copyable input
Out[31]=
PowerMod 对于复合的 也适用.
In[32]:=
Click for copyable input
Out[32]=
对于给定的模 k，具有 个不同的狄利克雷（Dirichlet）特征，以索引 j 作为标签. 不同的约定可以对可能的特征给出不同的排序.
DirichletCharacter 适用于很大的数.
In[33]:=
Click for copyable input
Out[33]=
当欧拉 totient 函数 给出小于 且与 互素的正整数的个数. 一个重要的关系（费马小定理）是对与 互素的所有 有 .
莫比乌斯函数 被定义为：当 为 个不同素数的积时，等于 ，当 包含素数的平方（不为1）时，等于 . 一个重要的关系是莫比乌斯逆公式，即如果 对所有 成立，那么 ，其中和式是对所有整除 的正整数 求积.
除数函数 是 的所有约数的  次幂的和. 函数 给出 的约数的总数，并常常表示为 、 和 . 函数 等于 的所有约数的和，常常表示为 .
对于素数 ，.
In[34]:=
Click for copyable input
Out[34]=
像费马小定理保证的那样，结果为1.
In[35]:=
Click for copyable input
Out[35]=
这里给出 24 的所有约数的列表.
In[36]:=
Click for copyable input
Out[36]=
给出24的不同约数的总数.
In[37]:=
Click for copyable input
Out[37]=
函数 DivisorSum 表示 的和，对于所有的除以 n 的 i. DivisorSum 仅包含对于 给出 True 的约数.
这里给出五个正整数的约数的和的列表.
In[38]:=
Click for copyable input
Out[38]=
这里强加了每个约数 i 必须小于 6 的条件.
In[39]:=
Click for copyable input
Out[39]=
雅可比符号 JacobiSymbol 当 为奇数时，归结为勒让德符号 . 勒让德符号是：当 被 整除时，其值为零；否则，当 是二次余数（模素数 ）其值为 ，若不然其值为 . 一个与 互素的整数 称为二次余数（模 ） 是指存在一个整数 使得 . 完全雅可比符号是所有满足 的素因子 的勒让德符号 的连乘.
扩展 GCD ExtendedGCD 给出一个列表 ，其中 是 的最大公约数， 是满足 的整数. 扩展 GCD 在求线性丢番图方程的整数解中是重要的.
列表中的第一个数是 105 和 196 的最大公约数.
In[40]:=
Click for copyable input
Out[40]=
第二个数对满足 .
In[41]:=
Click for copyable input
Out[41]=
多重阶函数 MultiplicativeOrder 给出使 的最小整数 . 那么 被称为 模 的指标. 表示法 偶尔被使用.
广义多重阶函数 MultiplicativeOrder 给出使 对某个 成立的最小整数 . MultiplicativeOrder 有时称作 模 的次阶函数，记为 . MultiplicativeOrder 有时被称为关于基 模 的 的离散对数.
卡米切尔函数或最小通用指数 给出使 对所有的与 互素的整数 都成立的最小整数 .
ContinuedFraction[x,n]生成 x 的连续分式表示的前 n 项
FromContinuedFraction[list]从其连续分式表示重构一个数
Rationalize[x,dx]寻找 x 的有理近似，容差为 dx

连续分式.

这里生成 的连续分式表示的前10项.
In[42]:=
Click for copyable input
Out[42]=
重构由连续分式项的列表代表的数.
In[43]:=
Click for copyable input
Out[43]=
结果接近 .
In[44]:=
Click for copyable input
Out[44]=
这里直接给出 的有理近似.
In[45]:=
Click for copyable input
Out[45]=
连续分式 出现在许多数论的设置中，有理数有最终连续的分式表示. 二次的无理数有重复的连续分式表示.
ContinuedFraction[x]有理数或者二次无理数的完全连续分式表示
QuadraticIrrationalQ[x]检测 x 是否为二次无理数
RealDigits[x]有理数的完全数字序列
RealDigits[x,b]b 进制下的完全数字序列

数的完全表示.

的连续分式表示从第八项开始，然后涉及永远重复的项的序列.
In[46]:=
Click for copyable input
Out[46]=
这里从其连续分式表示中重构 .
In[47]:=
Click for copyable input
Out[47]=
这是一个二次无理数.
In[48]:=
Click for copyable input
Out[48]=
这里显示 3/7 的十进制位的循环序列.
In[49]:=
Click for copyable input
Out[49]=
FromDigits 重构原来的数.
In[50]:=
Click for copyable input
Out[50]=
收敛连分数 经常用来使用有理数逼近无理数. 这些近似数从上方和下方交替，并且在项数上呈指数收敛. 此外，一个简单的连分数的收敛 比任何其它具有小于或者等于 的分母的有理数逼近更好.
Convergents[x]给出 x 的有理近似的列表
Convergents[x,n]仅给出前 n 个近似

收敛连分数.

这里给出 101/9801 的有理数逼近列表，从它的连分式展开式导出.
In[51]:=
Click for copyable input
Out[51]=
这里只列出前 10 个收敛.
In[52]:=
Click for copyable input
Out[52]=
这里列出 的连续有理逼近，直到用尽数值精度.
In[53]:=
Click for copyable input
Out[53]=
对于一个确切的无理数，用户必须明确要求项的数目.
In[54]:=
Click for copyable input
Out[54]=
LatticeReduce[{v1v2,...}]整数向量 的集合的规约格基
HermiteDecomposition[{v1,v2,...}]整数向量 的集合的梯阵式

整数格的函数.

格简化函数 LatticeReduce 被使用在多种现代算术中. 基本思想是把整数向量 看作定义一个数学上的格. 表示格中一个点的任意向量可以被写为形如 的线性组合，其中 是整数. 对于一个特定的格，存在对"基向量" 的许多可能的选择. LatticeReduce 所做的是找出对于该格的具有某种特殊性质的化简的基向量 的集合.
沿着三个坐标轴的三个单位向量已经构成简化的基.
In[55]:=
Click for copyable input
Out[55]=
这里给出在由三个向量指定的四维空间中的一个格的简化基.
In[56]:=
Click for copyable input
Out[56]=
注意，在上一个例子中，LatticeReduce 把几乎平行的向量用更正交的向量取代. 在这个过程中，求出相当短的基向量.
对于矩阵 ，HermiteDecomposition 给出矩阵 和 使得 是幺模，，并且 为简化行阶梯矩阵. 相对于RowReduce，枢轴（pivots）可能大于1，因为在整数环上没有分数. 枢轴（pivot）上的项通过减去枢轴同行的所有元素（pivot row）的适当的倍数来最小化.
在这种情况下，恢复原有的矩阵，因为它的连续梯队的形式.
In[57]:=
Click for copyable input
Out[57]=
这满足要求的恒等式.
In[58]:=
Click for copyable input
Out[58]=
这里，第二个矩阵具有一些大于1的枢轴（pivot），以及枢轴上的非零项.
In[59]:=
Click for copyable input
Out[59]=
DigitCount[n,b,d]n 在 b 进制表示下的数字 d 的数目

位计数函数.

这里是77在二进制表示下的各个位.
In[60]:=
Click for copyable input
Out[60]=
这个直接计算在二进制表示下1的个数.
In[61]:=
Click for copyable input
Out[61]=
位计数函数图形是自相似的.
In[62]:=
Click for copyable input
Out[62]=
BitAnd[n1,n2,...]整数 的位与
BitOr[n1,n2,...]整数 的位或
BitXor[n1,n2,...]整数 的位异或
BitNot[n]整数 n 的位非
BitLength[n]整数 n 中的二进制位数
BitSet[n,k]在整数 n 中，设置位 k 为1
BitGet[n,k]从整数 n 中获取位 k
BitClear[n,k]在整数 n 中，设置位 k 为0
BitShiftLeft[n,k]向左移动整数 n，移动量为 k 位，并使用零填充
BitShiftRight[n,k]向右移动，并且去掉最后 k 位

位运算.

位运算作用于表示为二进制的整数. BitAnd 产生一个整数其二进制表示的某一位为1当且仅当所有的 在该位为1. BitOr 产生一个整数其二进制表示的某一位为1，只要某个 在该位为1. BitXor 产生一个整数，其二进制表示的某一位为1，当且仅当 或者 中仅有一个在该位为1. BitXor 的二进制表示的某一位为1，当且仅当 中有奇数个在该位为1.     
这里求以二进制输入的 23 和 29 的位与.
In[63]:=
Click for copyable input
Out[63]//BaseForm=
位运算使用在各种组合算术中. 它们也常常用于低级计算机语言中操纵位域. 然而，在这些语言中，整数有受限制的位数，典型的是8的倍数. 在 Mathematica 中的位运算实际上允许整数有不受限制的序列. 这使得 BitNot[n] 简单地等于 .
SquareFreeQ[n]如果 n 不包含平方因子，则给出 True； 否则，给出 False

测试平方因子.

SquareFreeQ[n] 检查 n 是否具有平方素数因子. 这通过计算 MoebiusMu[n] 并且查看结果是否为0来实现；如果是，那么 n 包括平方素数因子，否则就不包括. 计算MoebiusMu[n] 涉及寻找 n 的最小素数因子 q. 如果 n 是一个小的素数因子（小于或者等于 ），这是很快的. 否则，用 FactorInteger 来寻找 q.
素数的积不包含任何平方因子.
In[64]:=
Click for copyable input
Out[64]=
平方数 4 除以 60.
In[65]:=
Click for copyable input
Out[65]=
SquareFreeQ 可以处理大整数.
In[66]:=
Click for copyable input
Out[66]=
NextPrime[n]给出大于 n 的最小素数
RandomPrime[{min,max}]返回 min 和 max 之间的随机素数
RandomPrime[max]返回小于或者等于 max 的随机素数
RandomPrime[{min,max},n]返回 min 和 max 之间的 n 个随机素数
RandomPrime[max,n]返回小于或等于 max 的 n 个随机素数

寻找素数.

NextPrime[n] 寻找最小的素数 p 使得 . 对于少于20位的 n，该算法对大于 n 的奇数，使用 PrimeQ 进行直接搜索. 对于超过20位的 n，该算法构建一个"小筛子"，并且首先检查候选素数是否可以在使用 PrimeQ 前被一个小素数整除. 这似乎比直接搜索速度更快一些.
这里给出 10 之后的下一个素数.
In[67]:=
Click for copyable input
Out[67]=
甚至对于大数，下一个素数也能相当快地得到计算.
In[68]:=
Click for copyable input
Out[68]=
这里给出小于 34 的最大素数.
In[69]:=
Click for copyable input
Out[69]=
对于 RandomPrime 和 RandomPrime[max]，如果 max 是小的，则通过从素数查找表中随机选择，获取一个随机素数 p；如果 max 是大的，则通过在整数中随机搜索整数获取该随机素数. 如果在指定范围内不存在素数，则返回未计算的输入，并显示一个错误信息.
这是在 10 和 100 之间的随机素数.
In[70]:=
Click for copyable input
Out[70]=
PrimePowerQ[n]决定 n 是否为一个有理素数的正整数幂

测试是否包含素数幂.

PrimePowerQ 的算法首先计算 n 的最小素因子 p ，并且尝试除以 n 直到或者当 n 是一个素数幂的时候，得到1，或者当 n 不是一个素数幂的时候尝试除以 n 直到不可以再进行除法运算的时候.
这个数是单个素数的幂.
In[71]:=
Click for copyable input
Out[71]=
在 GaussianIntegers 上，这是一个素数幂.
In[72]:=
Click for copyable input
Out[72]=
ChineseRemainder[list1,list2]给出最小的非负整数 r，并满足 Mod[r, list2]==list1

求解联立全等.

中国剩余定理规定，一定类型的联立全等问题总是有一个解. ChineseRemainder 寻找最小非负整数 r 使得 Mod 是 . 该解是唯一的 的元素的最小公倍数的模.
这意味着 、 以及 .
In[73]:=
Click for copyable input
Out[73]=
这里确认结果.
In[74]:=
Click for copyable input
Out[74]=
更长的列表仍然相当快.
In[75]:=
Click for copyable input
Out[75]=
PrimitiveRoot[n]给出 n 的原根，其中 n 是素数幂或者素数幂的两倍

计算原根.

PrimitiveRoot[n]返回一个生成器，该生成器生成与 n 在模 相乘互素的数形成的集合. 这里具有一个生成器，当且仅当 n 是 2、4、一个奇素数的幂、或者一个奇素数的幂的两倍. 如果 n 是一个素数或者素数幂，将返回最小正原根.
这是 5 的原根.
In[76]:=
Click for copyable input
Out[76]=
这里证实，它的确产生相应的数的组合.
In[77]:=
Click for copyable input
Out[77]=
这是一个素数幂的素数根.
In[78]:=
Click for copyable input
Out[78]=
这是一个素数幂的两倍的原根.
In[79]:=
Click for copyable input
Out[79]=
如果该变量是复合的，并且不是素数幂或者素数幂的两倍，该函数不进行计算.     
In[80]:=
Click for copyable input
Out[80]=
SquaresR[d,n]给出把整数 n 表示为 d 个平方数的和的表示法数目
PowersRepresentations[n,k,p]给出把整数 n 表示为 k 个非负第 p 次整数幂的和的不同表示方法

把一个整数表示为平方和或者其它幂的和.

这里把 101 表示为 3 个平方数的和.
In[81]:=
Click for copyable input
Out[81]=
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team
格式:   HTML  |  CDF