此为 Mathematica 4 文档,内容基于更早版本的 Wolfram 语言
查看最新文档(版本11.2)

3.2.4 整数和数论中的函数

一些整数函数

17 除以 3 的余数

17/3 的整数部分

Mod 也可用于实数

Mod 得到的结果,其符号与第二个自变量的符号相同

对任何整数   .

带偏心距的整数余数

特别当使用 Mod 来获得部分对象的索引时,指定一个偏心距常常是方便的.

在对列表循环处理下,提取列表的第 18 个元素

最大公约数函数 GCD[ ,  , ... ]  的最大整数. 当输入 两个整数的比时,Mathematica 使用 GCD 约去公因式,并给出最简有理数.
最小公倍数函数  的所有因子的 最小整数.

整除 24 和 15 的最大整数是 3

Kronecker Delta Kronecker 符号 KroneckerDelta[ ,  , ... ]  全相等等于 1,否则等于 0.  .

这里给出一个秩为 3 的全对称张量

整数因子分解和相关函数

给出 24 的所有因子为   . 每个子列表的第一个元素是因子,第二个元素是其指数

这是一个较大的整数的因子

应当认识到,按照现代数学的观点,整数因子分解是本质上困难的计算问题. 因此,用户能容易地输入一个整数,而 Mathematica 对其分解因子可能要花 费天文数字长度的时间. 只要用户给出的整数位数小于 25,FactorInteger 将不会有任何困难. 然而,在一些特殊情况下,它能处理长的多的整数. (用户可以通过设置选项 FactorInteger->False 使某些因子分解问 题进行的更快, 这样 FactorInteger[n]  中分出简单的因子)

这是一个相当特殊的长整数

Mathematica 能容易地分解这个特殊整数

尽管 Mathematica 可能分解不了大整数,但它常常能检测该整数是否 为素数. 此外,Mathematica 有一个寻找第 个素数的快速方法.

检测一个数是否是素数常常比分解它的因子快得多

这是前 100 个素数的图形

这是第一百万个素数

在数论中,知道素数的分布比知道它们的值常常更重要. 函数 PrimePi[x]  的素数个数.

给出小于10亿的素数个数

缺省时,FactorInteger 只允许实整数,但通过设置选项 GaussianInteger->True, 它也能处理高斯整数实部和虚部均为整数的复数. 正如它能 唯一地分解出实素数一样. 它也能唯一地分解出高斯素数.然而,在高斯 素数的选择中有一些潜在的二义性. 在 Mathematica 中,除了初始的 -1 此外,因子总是被选为正实部和非负虚部.

在高斯整数上,2 能分解为

这里是一个高斯整数的所有因子

数论中的一些函数

模幂函数 PowerMod[a, b, n] 给出与 Mod[a^b, n]  时的相同的结果. 但是 PowerMod 更有效,因为它避免生成  的完全形式.
使用 PowerMod[a, b, n]  PowerMod[a, b, n]  mod  (当这样的整数存在时,它是唯一的). 如果不存在这样的整数 Mathematica 就使 PowerMod 不再计算.

PowerMod 等价于先使用 Power,再使用 Mod,但更有效率

这给出 3 模 7 的模逆

3 乘以该逆模 7 得 1

当欧拉 totient 函数 Phi(n) 给出小于 n 且与 n 互素的正整数的个数. 一个重要的关系(费马小定理)是对与 n 互素的所有 a (mod n).
莫比乌斯函数 Mu(n) 被定义为: 当 nk 个不同素数的积时,Mu(n)= ,当 n=1 时 Mu(n)=1, 当 n 包含素数的平方时 Mu(n)=0. 一个重要的关系是莫比乌斯逆公式,即如果 对所有 n 成立,那么 ,其中  是对所有整除 n 的正整 d 求积.
除数函数  n 的所有约数的 k 次幂的和.  给出 n 的约数的总数,并常常表示为  .  等于 n 的所有约数的和,常常表示为 Sigma(n).

对素数 n

像费马小定理保证的那样,结果为 1

这里给出 24 的所有约数的列表

 给出 24 的不同的约数的总数

雅可比符号 JacobiSymbol[n, m]m 为奇数时归结为勒让德符号  ,勒让德符号是:当 nm 整除时其值为零,否则,当 n 是二次余数 (模素数 m) 其值为 1,若不然其值为 -1. 一个与 m 互素的整数 n 称为二次余数 (模 m) 是指存在一个整数 k 使得  (mod m). 完全雅可比符号是关于m 的所有素因

 的连乘.
扩展 gcd ExtendedGCD[m,n]给出一个列表{g,{r,s}},其中g是 mn 的 最大公约数,r,s 是满足  的整数.扩展 gcd 在求线性丢番图方程的 整数解中是重要的.

列表中的第一个数是 105 和 196 的最大公约数

第二个数对满足  .

多重阶函数 MultiplicativeOrder[k, n]  (mod   偶尔被使用.
广义多重阶函数   (mod  成立的最小整数. MultiplicativeOrder[k, n,  -1, 1 ] 有时称作k模 n 的次阶函数记为  .
卡米切尔函数或最小通用  (mod .
 被使用在几种现代算术 中.   ,  有许多可能的 "基向量"  LatticeReduce 所做的事情是找出 对于该格的具有某种特殊性质的化简的基向量

沿着三个坐标轴的三个单位向量已经构成简化的基

这里给出由三个向量指定的四维空间中的一个格的化基

In[28]:=
Out[28]=

注意在上一个例子中,LatticeReduce 用更正交的向量代替几乎平行的向量. 在这个过程中,求出相当短的基向量.

连续分式

这里生成 Pi 的连续分式表示的前 10 项

重构由连续分式项的列表代表的数

结果接近 Pi

连续分式出现在许多数论的设置中,有理数有最终连续的分式表示. 二次的无理数有重复的连续分式表示.

数的完全表示

 的连续分式表示从第八项开始,然后涉及永远重复的项的序列

这里从其连续分式表示中重构

这里显示 3/7 的十进制位的循环序列

重构原来的数

位计数函数

这里是 77 在二进制表示下的各个位

这个直接计算在二进制表示下 1 的个数

位计数函数图形是自相似 的

位运算

位运算作用于表示为二进制的整数. BitAnd[ ,  ,...] 产生一个整数 其二进制表示的某一位为 1 当且仅当所有的 ni在该位为 1. BitOr[ ,  ,...] 产生一个整数其二进制表示的某一位为1,只要某个 ni 在该位为 1. BitXor[ ,  ] 产生一个整数其二进制表示的 某一位为 1,当且仅当 n1n2中仅有一个在该位为1. BitXor[ ,  ,...] 的二进制表示的某一位为 1,当且仅当 ni 中有奇数个在该位为 1.

这里求以二进制输入的 23 和 29 的位与

Out[39]//BaseForm=

位运算使用在各种组合算术中 . 它们也常常用于低级计算机语言中操纵位域. 然而,在这些语言中,整数有受限制的位数,典型的是 8的倍数.Mathematica 中的位运算实际上允许整数有不受限制的序列. 这使得 BitNot[n]简单地等于 .