Blum 数

布卢姆数
术语名称	布卢姆数
英语名称	Blum integer

布卢姆数(Blum integer)指一个自然数是两个不同且均模 4 余 3 的质数乘积。是一种半质数。

性质

与 -1 相关的 Legendre 符号满足 [math]\displaystyle{ (\frac{-1}p)=(\frac{-1}q)=-1 }[/math] ， Jacobi 符号满足 [math]\displaystyle{ (\frac{-1}{n})=(\frac{-1}p)(\frac{-1}q) = 1 }[/math] 。

对和 [math]\displaystyle{ n }[/math] 互质的整数 [math]\displaystyle{ a }[/math] ，若 [math]\displaystyle{ (\frac{a}n)=1 }[/math] 则 [math]\displaystyle{ a,-a }[/math] 中有且仅有一个是 [math]\displaystyle{ n }[/math] 的二次剩余。

对和 [math]\displaystyle{ n }[/math] 互质的整数 [math]\displaystyle{ a }[/math] ，若是一个二次剩余，有两对平方根，其中有且仅有一个是模 [math]\displaystyle{ n }[/math] 的二次剩余。进一步地，模 [math]\displaystyle{ n }[/math] 二次剩余集合上的平方映射是一个置换。

由于每对 Jacobi 符号相同的平方根中一个小于 [math]\displaystyle{ n/2 }[/math] 一个大于 [math]\displaystyle{ n/2 }[/math] 。也就是说，四个平方根中，Jacobi 符号相同的，大小一定不在同一侧；大小在同一侧的， Jacobi 符号一定不同。

整除理论
整除关系	整除、倍数、因数	带余除法
正整数的分类	1、质数、合数
	质数测试	试除法、埃氏筛、线性筛
最大公约数理论	公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math]	辗转相除法
	互质
算术基本定理	算术基本定理	标准质因数分解