高斯整数环学习心得随笔

过些天补上~

代码

• ==：两个高斯整数相伴，即为相等。
• 小于和大于：用复数的范数Norm来比较。应用场景举例：高斯整数环的唯一分解定理证明。
• 整除和取模（带余除法）：复数除法的结果是个有理数，但为了方便还是直接用double存了。设两个高斯整数a,b，复数除法结果为a / b = x+yi，则一种可行的取法是round(x)+round(y)*i，这就是整除结果。而g = (x-round(x))+(y-round(y))*i就是带余除法定义中一个可行的“范数小于等于1/2的复数”，g*b即取模结果。具体看代码。
• gcd：既然有带余除法，直接运行辗转相除法即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 1e3 + 5;
const int mod = 998244353;
int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1};

void dbg(){puts("");}
template<typename T, typename... R>void dbg(const T &f, const R &... r) {
    cout << f << " ";
    dbg(r...);
}
template<typename Type>inline void read(Type &xx){
    Type f = 1;char ch;xx = 0;
    for(ch = getchar();ch < '0' || ch > '9';ch = getchar()) if(ch == '-') f = -1;
    for(;ch >= '0' && ch <= '9';ch = getchar()) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read(){}
template<typename T,typename ...R>void read(T &x,R &...r){
    read(x);
    read(r...);
}

struct GI;
LL norm(const GI &x);
GI gcd(const GI &x,const GI &y);

struct GI{
    int a,b;
    GI():a(0),b(0){}
    GI(int a,int b):a(a),b(b){}
    //相伴
    bool operator == (const GI &rh) const{
        return a == rh.a && b == rh.b ||
        a == -rh.a && b == -rh.b ||
        a == -rh.b && b == rh.a ||
        a == rh.b && b == -rh.a;
    }
    bool operator < (const GI &rh) const{
        return norm(*this) < norm(rh);
    }
    bool operator <= (const GI &rh) const{
        return norm(*this) <= norm(rh);
    }
    bool operator > (const GI &rh) const{
        return norm(*this) > norm(rh);
    }
    bool operator >= (const GI &rh) const{
        return norm(*this) >= norm(rh);
    }
    GI operator + (const GI &rh) const{
        return {a+rh.a,b+rh.b};
    }
    GI operator - (const GI &rh) const{
        return {a-rh.a,b-rh.b};
    }
    GI operator * (const GI &rh) const{
        return {a*rh.a-b*rh.b,a*rh.b+b*rh.a};
    }
    //整除
    GI operator / (const GI &rh) const{
        double x = 1.0*(a*rh.a+b*rh.b)/norm(rh),y = 1.0*(b*rh.a-a*rh.b)/norm(rh);
        return {round(x),round(y)};
    }
    GI operator % (const GI &rh) const{
        double x = 1.0*(a*rh.a+b*rh.b)/norm(rh),y = 1.0*(b*rh.a-a*rh.b)/norm(rh);
        complex<double> g = {x-round(x),y-round(y)};
        g *= complex<double>(rh.a,rh.b);
        return {round(g.real()),round(g.imag())};
    }
    GI operator %= (const GI &rh){
        GI u = (*this) % rh;
        a = u.a;b = u.b;
        return u;
    }
    friend ostream& operator << (ostream &sm,const GI &x){
        sm << "(" << x.a << "," << x.b << ")";
        return sm;
    }
};
LL norm(const GI &x){return x.a*x.a+x.b*x.b;}
GI gcd(const GI &x,const GI &y){
    return y == GI() ? x : gcd(y,x%y);
}

void test_op(){
    dbg("test_op");
    GI x(4,3),y(3,4);
    assert(GI(4,3) == GI(-4,-3) && GI(4,3) == GI(-3,4) && GI(4,3) == GI(3,-4));
    assert(!(x == y) && x <= y && x >= y);
    GI z(4,4);
    assert(x < z && x <= z && z > x && z >= x);
    assert(x+y == GI(7,7));
    assert(x*y == GI(0,25));
}

//对拍：https://jingyan.baidu.com/article/e75aca8526c6a7142fdac67f.html
void test_div(){
    dbg("test_div");
    GI u = GI(1,8) % GI(-1,5);
    dbg(u);//(-2,-3)
    assert(u == GI(2,3));
    
    GI x(18,5),y(7,5);
    u = x - x / y * y;
    dbg(x / y,u);//x / y = (2,-1), u = (-1,2)
    dbg(x % y);//(-1,2)
    assert(u == x % y);
    dbg(y / u);//(1,-4)
    dbg(y % u);//(0,-1)
    
    x = {112,1};
    y = {-57,79};
    dbg(x / y);//(-1,-1)
    u = x % y;
    dbg(u);//(-24,23)
    assert(u == GI(-24,23));
    
    x %= y;swap(x,y);
    u = x % y;
    dbg(u);//(-8,-14)
    assert(u == GI(-8,-14));
    
    x %= y;swap(x,y);
    u = x % y;
    dbg(u);//(-4,-7)
    assert(u == GI(4,7));
}

void test_gcd(){
    dbg("test_gcd");
    GI g = gcd(GI(18,5),GI(7,5));
    dbg(g);//(0,-1)
    assert(g == GI(0,-1));
    g = gcd(GI(112,1),GI(-57,79));
    dbg(g);//(-4,-7)
    assert(g == GI(4,7));
    g = gcd(GI(32,9),GI(4,11));
    dbg(g);//(0,-1)
    assert(g == GI(1,0));
    g = gcd(GI(11,3),GI(1,8));
    dbg(g);//(1,-2)
    assert(g == GI(1,-2));
    g = gcd(GI(4,5),GI(4,-5));
    dbg(g);//(0,1)
    assert(g == GI(1,0));
}

int main(int argc, char** argv) {
    test_op();
    test_div();
    test_gcd();
    return 0;
}

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

以下内容摘自 我的文章：算法竞赛中的数论问题 - 数论全家桶（信奥 / 数竞 / ACM）作者孟繁宇，四万字，十三万字符的竞赛数论完全总结，将会择机发布，敬请期待 ~

0x90 高斯整数

0x90.0 复数

复数分为实部和虚部，可以描述为一个二元组 $(x,y)$，表示这个数等于$x+y\sqrt{-1}$。一般用 $i$ 表示 $\sqrt{-1}$。

由于是个二元组，所以它在理解的时候可以抽象为一个二维向量，分布在平面直角坐标系上。

事实上，它确实也有不少性质和向量相同。

• 复数的模

定义复数的模，为复平面原点到 $(a,b)$的距离，即$|z|=\sqrt{x^2+y^2}$

定义 $z$ 的范数 $N(z)=|z{|}^2=x^2+y^2$。

• 共轭复数

复数 $z=a+bi$ 的共轭是 $z^{\prime }=a-bi$，记作 $\bar{z}$。

性质：$z\times \bar{z}=a^2+b^2$，$|z|=|\bar{z}|$。

• 复数的大小

复数可以看做和向量一样，无法比较大小。

• 复数的加减

对应部 的加减，如 $(a,c)+(b,d)=(a+b,c+d)$

• 复数乘法

两个复数 $z_1=a_1+b_{1}i,z_2=a_2+b_{2}i$ 相乘的结果为

$$z_0=z_1\times z_2=(a_1+b_{1}i)\times (a_2+b_{2}i)=a_1{a}_2+a_1{b}_{2}i+a_2{b}_{1}i+b_1{b}_2{i}^2$$

又因为 $i^2=-1$，所以

$z_0=(a_1{a}_2-b_1{b}_2)+(a_1{b}_2+a_2{b}_1)i$

在复平面上，$z_1,z_2,z_0$ 所对应的幅角 ${\theta }_1,{\theta }_2,{\theta }_0$

有关系：${\theta }_0={\theta }_1+{\theta }_2$

• 复数的除法

对于两个复数 $z_1=a_1+b_{1}i,z_2=a_2+b_{2}i$，他们相除的结果为

$$z_0=\frac{z_1}{z_2}$$

考虑分数上下同时乘 $\overline{z_2}$ ，有

$$z_0=\frac{z_1\overline{z_2}}{a_2^2+b_2^2}$$

分母是一个实数，可以直接将分子的实部虚部除以分母。

或者也可以展开：

$$\frac{a+c\times i}{b+d\times i}=\frac{(a+c\times i)(b-d\times i)}{(b+d\times i)(b-d\times i)}=\frac{(ab+cd)+(bc-ad)\times i}{b^2+d^2}$$

即：

$$\frac{(a,b)}{(c,d)}=(\frac{ab+cd}{b^2+d^2},\frac{bc-ad}{b^2+d^2})$$

• 复数指数幂：

有欧拉公式$e^{i\theta }=\cos \theta +i\sin \theta$其中 $e$ 是自然对数的底数

当取 $\theta =\pi$ 时，有$e^{i\pi }=\cos \pi +i\sin \pi$$
又因为 $$\cos \pi =1,sin\pi =0$

所以$e^{i\pi }=-1$

也就是：$e^{i\pi }+1=0$

0x91 高斯整数

• 定义

形如 $a+bi$ （其中$a,b$ 是整数）的复数被称为高斯整数，高斯整数全体记作集合 Z [ i ] = { a + b i ∣ a , b ∈ Z } ,   w h e r e   i 2 = − 1 Z[i] = \{ a + bi | a,b \in Z\}, \ where \ i^2 = -1 Z[i]={a+bi∣a,b∈Z}, where i2=−1，换言之，高斯整数是实部和虚部都为整数的复数。由于高斯整数在乘法和加法下交换，它们形成了一个交换环。也就是高斯整数是加、减、乘运算下封闭。

满足加法、乘法以及交换律、结合律、分配率并有 $0$ 元和单位元的集合称为交换环。

在复平面上，高斯整数是二维复平面上的整点$(a,b)$。

高斯整数的模是它和自己共轭复数的乘积，即范数 $N(a+bi)=(a+bi)(a-bi)=a^2+b^2$，它的模可以表示为两个数字的平方和，所以不能表示为 $4k+1,wherek\in Z$。

• 整除

设 $\alpha ,\beta$ 是高斯整数，我们称 $\alpha$ 整除 $\beta$ ，是指存在一个高斯整数 $\gamma$，使得 $\beta =\alpha \gamma$。同整数集，若 $\alpha$ 整除 $\beta$ ，记作 $\alpha |\beta$反之记作 ，$\alpha \nmid \beta$ 。

• 带余除法

也称欧几里得除法，高斯整环 $Z[i]$ 是欧几里得环，所以它具有很多在整数域和多项式域上成立的特性，比如辗转相除，裴蜀定理，主理想，欧几里德引理，唯一分解定理，中国剩余定理。

定理91.1： 设 $\alpha ,\beta$ 为高斯整数且 $\beta \ne 0$，则存在高斯整数 $\gamma$ 和 $\rho$ ，使得 $\alpha =\beta \gamma +\rho$。

而且 $0\le N(\rho )\le N(\beta )$。这里的 $\gamma$ 被成为商， $\rho$ 被称为 余数 。

欧几里德引理

$$\begin{gathered} \forall a,b,pwherepisaprime \\ p|ab\Rightarrow p|aorp|b \end{gathered}$$

如果将高斯整数 $a$ 写为 $a=bq+r$，有$N(r)\le \frac{N(b)}{2}$。

证明：

令 $\frac{a}{b}=x+yi$，令$-\frac{1}{2}\le x-m\le \frac{1}{2},-\frac{1}{2}\le y-n\le \frac{1}{2}$，令$q=m+ni$，由$a=bq+r$，$r=b(x-m+(y-n)i)$，故$N(r)\le \frac{N(b)}{2}$。

0x92 高斯素数

定义92.1 ： 若 $ϵ|1$，则称高斯整数 $ϵ$ 是 单位 ，若 $ϵ$ 是单位，则称 $ϵ\alpha$ 是高斯整数 $\alpha$ 的一个相伴，高斯整数的单位为 $1,-1,i,-i$。

定义92.2： 若非零高斯整数 $\pi$ 不是单位，而且只能够被单位和它的相伴整除，则称之为高斯素数。

定理92.3： 若 $\pi$ 是高斯整数，而且 $N(\pi )=p$，其中 $p$ 是有理整数，则 $\pi$ 和 $\bar{\pi }$ 是高斯素数，而 $p$ 不是高斯素数。

高斯整数形成了一个唯一分解域。高斯整数只有当且仅当它是一个素数时才不可约分，高斯整数中 $Z[i]$ 的素数称为高斯素数。

1. 高斯素数的共轭复数依然为高斯素数。

2. 高斯素数的相伴复数依然为高斯素数。

   $\forall a+bi\in Z[i],-a+bi\in Z[i]$

3. 作为高斯素数的整素数 $p$ 是 $4k+3$ 型素数，其余的素数可以写为 $2$ 个共轭高斯素数的乘积

4. 一个高斯整数 $a+bi$ 是高斯素数当且仅当以下两个条件之一成立：

• $a,b$ 中一个为 $0$，且另一个数字为 $4k+3$ 型素数

  若 $p$ 为 $4k+3$ 型素数，存在 $d$，$d$ 不等于单位元，也不等于 $p$ ，满足 $d|p$ ，则 $d\bar{d}|p$ ，由于 $d\bar{d}$ 为整数，有 $d\bar{d}=p$，得出 $p=a^2+b^2$，$a^2+b^2\equiv 0,1,2(mod4)$ ，与 $p$ 为 $4k+3$ 型素数矛盾。

• $a,b$ 都非 $0$ ，且 $a^2+b^2$ 是素数

  令 $u=a+bi$ ，则 $u\bar{u}=p$，$p$ 为一个素数，若存在存在 $d$，$d$ 不等于单位元，也不等于 $u$，$d|u$，则 $d\bar{d}|p$，由于 $d\bar{d}$ 为整数，有 $d\bar{d}=p$，得出 $d=u$，与假设矛盾。

0x93 唯一分解

由于高斯整环是一个唯一分解域，所以每一个高斯整数都可以写为一个单位元和若干高斯素数的乘积，这种分解是唯一的（忽略共轭和相伴）。

∀ a ∈ Z [ i ] ,   a = u ⋅ ( 1 + i ) e 0 ∏ p m e i ,   w h e r e   u   ∈ { 1 , − 1 , i , − i } ,   0 ≤ e i \forall a \in Z[i], \ a = u \cdot (1+i)^{e_0} \prod p_m ^{e_i}, \ where \ u \ \in \{ 1, -1,i, -i\}, \ 0 \le e_i ∀a∈Z[i], a=u⋅(1+i)e0​∏pmei​​, where u ∈{1,−1,i,−i}, 0≤ei​

0x94 最大公约数

两个高斯整数的最大公约数并不唯一，加入 $d$ 是 $a$ 与 $b$ 的最大公约数，则 $a,b$ 的最大公约数为 $d,-d,id,-id$。

若$a=i^k\prod p_m^{{\nu }_m},b=i^n\prod p_m^{{\mu }_m}$，则其中一个最大公约数为

$$d=\prod p_m^{{\lambda }_m},where{\lambda }_m=min({\nu }_i,m{u}_i)$$

可以根据带余除法里的结论，进行辗转相除，时间复杂度为 $O(log(n))$。

Complex div(Complex a, Complex b) {
	long double mo = b.norm();
	Complex c = a * b.conj();
	long double r = 1. * c.r / mo, i = 1. * c.i / mo;
	return Complex(round(r), round(i));
}
Complex gcd(Complex a, Complex b) {
	if (b.r == 0 && b.i == 0) return a;
	Complex c = div(a, b);
	return gcd(b, a - b * c);
}

0x95 同余和剩余系

给定一个高斯整数 $z_0$ ，对于高斯整数 $z_1,z_2$ ，如果它们的差是 $z_0$ 的整数倍，即 $z_1-z_2=k{z}_0,k\in Z$，那么称 $z_1$ 与 $z_2$ 模 $z_0$ 同余，写作 $z1\equiv z2(\mathrm{m}\mathrm{o}\mathrm{d}z0)$。

模 $z_0$ 同余是一种等价关系，它将高斯整数分成若干个等价类，称为剩余类，剩余类写作 $Z/z_{0}Z$ ，剩余类形成了一个交换环。

0x96 费马二平方和定理

$p$ 是一个素数，$p$ 可以写成两个平方数的和，当且仅当 $p=2$ 或 $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$。

充分性：令 $p=a^2+b^2$ ，对任意一个整数 $x$ ，有 $x2\equiv 0,1,2(\mathrm{m}\mathrm{o}\mathrm{d}4)$，故 $a^2+b^2\equiv 0,1,2(\mathrm{m}\mathrm{o}\mathrm{d}4)$，由于 $p$ 是素数，所以 $p=2$ 或 $p\equiv 1(mod4)$。

必要性：当 $p=2，2=12+12$，当 $p$ 为 $4k+1$ 型素数，由于 $p$ 不是高斯素数，所以可以进行分解，即 $p=u\bar{u}$, $u=a+bi$，故 $p=a^2+b^2$。

0x97 分解4k+1型素数

$p$ 为 $4k+1$ 型素数，如果存在 $k2\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p)$ ，则 $p|(k+i)(k-i)$，由于 $p=u\bar{u}$，有$u|(k+i)$，故 $u=(k+i,p)$ ，即可将 $p$ 分解为两个平方数的和。

由于有一半的数在模$p$下存在平方剩余，随机一个 $t$ ，检验 $t^{\frac{p-1}{2}}\equiv -1(modp)$，令 $k=t^{\frac{p-1}{4}}$，时间复杂度为 $O(Tlog(p)),T$ 为测试次数。

0x98 构造 $a^2+b^2=n$的方案

1. 首先将 $n$ 分解为 $n=\prod p_m^{e_m}$ 的形式
2. 将 $2$ 分解为 $(1+i)(1-i)$ ，将 $4k+1$ 型素数分解为 $u\bar{u}$，其中 $u$ 为高斯素数，$4k+3$ 型素数不可分解
3. $n=\prod p_m^{e_i},0\le e_i$，由$ n=u \bar u $，故需要将$n$中的高斯素数分成两部分，使得两部分共轭。考虑素数 $p_m$ ，对于 $4k+1$ 型素因子，分解为 $u^{e_m}{\bar{u}}^{e_m}$ ，左边可以放 $k$ 个 $u$，$e_m-k$ 个 $\bar{u}$；对于 $4k+3$ 型素因子，因为不能进行分解，所以左右两边的数量应该一样多，即 $4k+3$ 型的素数 $p_m$ 出现的次数必须为偶数。

令 $f(n)=\frac{1}{4}{\sum }_{x,y\in Z}[x^2+y^2=n]$，除以 $4$ 是因为由 $4$ 个单位元。由于素因子可以分开考虑，所以该函数为积性函数。

1. $f(2^k)=1$
2. $f(p^e)=e+1$，当 $p$ 为 $4k+1$ 型素数
3. $f(p^{2e+1})=0$， $f(p^{2e})=1$，当 $p$ 为 $4k+3$ 型素数

0x99 竞赛例题选讲

Problem A、 A math problem （HDU 2650）

给出 $a+bj$，其中 $j=\sqrt{-2}$ ，判断 $a+bj$ 是否为高斯素数。

Solution

我们按照上面证明的判断高斯素数的方法直接模拟即可。

注意这里不是正常的复数，这里设 $j=\sqrt{-2}$。

$|j|=\sqrt{a^2+(\sqrt{-2}b{)}^2}$

很明显原来的判定中 $a^2+b^2$ 就变成了 $a^2+2b^2$。同理若 $j=\sqrt{-k}$，就是 $a^2+k{b}^2$。

由于这里的数据很大，所以我们判断素数的时候需要用到$\mathtt{M}\mathtt{i}\mathtt{l}\mathtt{l}\mathtt{e}\mathtt{r}\_\mathtt{R}\mathtt{a}\mathtt{b}\mathtt{i}\mathtt{n}$算法

typedef long long ll;
ll mul(ll a, ll b, ll m) {
    ll ans = 0;
    while (b) {
        if (b & 1) {
            ans = (ans + a) % m;
            b--;
        }
        b >>= 1;
        a = (a + a) % m;
    }
    return ans;
}
ll qpow(ll a, ll b, ll m) {
    ll ans = 1;
    a %= m;
    while (b) {
        if (b & 1) {
            ans = mul(ans, a, m);
            b--;
        }
        b >>= 1;
        a = mul(a, a, m);
    }
    return ans;
}

bool Miller_Rabin(ll n) {
    if (n == 2)
        return true;
    if (n < 2 || !(n & 1))
        return false;
    ll a, m = n - 1, x, y;
    int k = 0;
    while ((m & 1) == 0) {
        k ++ ;
        m >>= 1;
    }
    for (int i = 0; i < Times; i++) {
        a = rand() % (n - 1) + 1;
        x = qpow(a, m, n);
        for (int j = 0; j < k; j++) {
            y = mul(x, x, n);
            if (y == 1 && x != 1 && x != n - 1)
                return false;
            x = y;
        }
        if (y != 1)
            return false;
    }
    return true;
}

int main() {
    ll a, b;
    while (~scanf("%lld%lld", &a, &b)) {
        if (a == 0) {
            if (b % 4 == 3 && Miller_Rabin(b))
                puts("Yes");
            else
                puts("No");
        } else {
            ll t = a * a + 2 * b * b;
            if (Miller_Rabin(t))
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}

Problem B Gaussian Prime Factors （POJ 3361）

求一个数的高斯素因子。

Solution

我们根据高斯素数的判定原理，我们只需要将输入的数进行质因数分解，如果得到的质数是 $4x+3$ 的形式就保存，不是就枚举,找到 $a$，求得 $b$ 看 $b$ 是否是整数，找到 $a$ 和 $b$，保存 $a+bi$ 和 $a-bi$，最后排序输出即可。

typedef long long ll;
struct complex
{
    ll a, b;
    char op;
} c[1100];
ll cp;
bool cmp(complex m, complex n)
{
    bool ret = 0;
    if (m.a < n.a)
        ret = 1;
    if (m.a == n.a && m.b < n.b)
        ret = 1;
    if (m.a == n.a && m.b == n.b && m.op == '+' && n.op == '-')
        ret = 1;
    return ret;
}
void getResult(ll p)
{
    ll i, j;
    if ((p - 3) % 4) {
        for (i = 1;; i++) {
            j = ll(sqrt(double(p - i * i)));
            if (i * i + j * j == p) {
                c[cp].a = i, c[cp].b = j, c[cp++].op = '+';
                c[cp].a = i;
                c[cp].b = j, c[cp++].op = '-';
                break;
            }
        }
    }
    else
        c[cp].a = p, c[cp].b = 0, c[cp++].op = '*';
}
int main()
{
    ll in, num = 0, i, j, k, tmp, isFir;
    while (scanf("%lld", &in) != EOF) {
        tmp = in;
        isFir = 1;
        cp = 0;
        printf("Case #%lld: ", ++ num);

        for (i = 2; i * i < tmp; i ++ ) {
            if (tmp % i == 0) {
                getResult(i);
                while (tmp % i == 0)
                    tmp /= i;
            }
        }
        if (tmp != 1)
            getResult(tmp);
        sort(c, c + cp, cmp);
        for (i = 0; i < cp; i++) {
            if (i)
                printf(", ");
            if (!c[i].b)
                printf("%lld", c[i].a);
            else if (c[i].b == 1)
                printf("%lld%cj", c[i].a, c[i].op);
            else
                printf("%lld%c%lldj", c[i].a, c[i].op, c[i].b);
        }
        printf("\n");
    }
    return 0;
}

一、高斯整数

形如 。（其中a，b是整数）的复数被称为高斯整数，高斯整数全体记作Z[i]。注意到若 γ=a+bi 是高斯整数，则它是满足如下方程的代数整数：

通常我们使用希腊字母来表示高斯整数，例如α，β，γ和δ。注意到若 n 是一个整数，则 n=n+0i 也是高斯整数。当我们讨论高斯整数的时候，把通常的整数称为有理整数。

加、减、乘运算

高斯整数在加、减、乘运算下是封闭的，正如下面定理所述。

定理1：设 α=x+iy 和 β=w+iz 是高斯整数，其中 x，y，w 和 z 是有理整数，则 α+β，α-β 和 αβ 都是高斯整数。

虽然高斯整数在加、减和乘运算下封闭，但是他们在除法运算下并不封闭，这一点与有理整数类似。此外，若 α=a+bi 是高斯整数，则a的范数 N(α)= 是非负有理整数。

整除性

我们可以像研究有理整数那样去研究高斯整数。整数的许多基本性质可以直接类推到高斯整数上。要讨论高斯整数的这些性质，我们需要介绍高斯整数类似于通常整数的一些概念。特别地，我们需要说明一个高斯整数整除另一个高斯整数的意义，并给出高斯素数的定义。

定义1：设 α 和 β 是高斯整数，我们称α整除β，是指存在一个高斯整数 γ 使得β=αγ。若α整除β，我们记作α|β ；若α 不整除β ，记作αβ 。

高斯整数的整除也满足有理整数整除的一些相同的性质。例如，若α，β和γ 是高斯整数，α|β，β|γ，则α|γ。再者，若α，β，γ，ν和μ 是高斯整数，γ|μ，γ|β，则γ|(μα+νβ)。

高斯素数

1, −1, i及−i都是高斯整数环里面的单位元。除此之外，在高斯整环里面不能因子分解的数称为高斯素数。高斯素数分为两类，其中一类是形式为4n+3（n是整数）的普通素数，如3，7等，它们在高斯整环里面也不能够因子分解。但是所有形式是4n+1的普通素数如5，13等，在高斯整环里面都可以唯一因子分解成两个共轭的高斯素数的乘积，如5=(2+i)(2-i)。需要注意的是，这里我们也可以写成5=(1+2i)(1-2i)，这个是因为(2-i)i=1+2i，而i是单位元，所以我们可以认为这两种分解是等价的。此外，素数2也可以分解，即2=(1+i)(1-i)。

 

二、费马平方和定理

费马平方和定理是指由法国数学家费马在1640年提出的一个猜想，但他没有提出有力的数学证明，1747年，瑞士数学家莱昂哈德•欧拉提出证明后成为定理。

费马平方和定理的表述是：奇质数能表示为两个平方数之和的充分必要条件是该素数被4除余1。

费马二平方定理(Fermat's Two Squares Theorem)

费马二平方定理是指除了2这个特殊的素数，所有的素数都可以分两类：被4除余1的素数，如5，13，17，29，37，41；第二类则是被4除余3的素数如3，7，11，19，23，31.第一类素数都能表示为两个整数的平方和，第二类都不能。

费马二平方定理指出，当且仅当或时，素数可以表示为两个非零平方之和。 并且这种表示是唯一的。

 

三、拉格朗日四平方定理（Lagrange's four-square theorem）

拉格朗日的四平方定理，也称为Bachet猜想，由Diophantus陈述缺乏必要条件而推论得出。它指出，每一个正整数可以写成的总和至多四个正方形。尽管该定理由费马使用无限下降来证明，但该证明被抑制了。欧拉无法证明该定理。拉格朗日（Lagrange）于1770年给出了第一个公开的证明，并利用了欧拉四方形恒等式。

拉格朗日的四平方定理（也称为Bachet猜想）指出，每个自然数都可以表示为四个整数平方之和。 其中四个数字是整数。它是費馬多邊形數定理和華林問題的特例。