“数论基础”课程学习笔记


整数

  • 整数的一部分,最简单的数学模型——自然数。
  • Peano 自然数公理:如果有一些对象(可数集),除了它们的数目之外其它性质我们不予考虑的话,我们就可以用自然数来数它们。

整除

  • \(0\) 是任何非零整数的倍数

同余方程

一次

设 \(m\in Z^{+} ,a,b\in Z,(a,m)=1\) ,则一次同余式 \(ax\equiv b(mod \; m)\) 恰有一个解,且其解为 \(x\equiv ba^{\varphi(m)-1}\) 。

设 \(m,n\in Z^{+} ,a_1.a_2,\cdots ,a_n,b\in Z\) ,则一次同余式 \(a_1x_1+a_2x_2+\cdots +a_nx_n\equiv b(mod \; m)\) ,有解的充分必要条件是 \(d|b\) ,其中 \(d=(a_1,a_2,\cdots a_n,m)\) ,此时同余方程解的个数为 \(m^{n-1}d\) 。

二次同余

\(ax^2+bx+c\equiv 0(mod\; p^{\alpha})\)

配方可以得到 \((2ax+b)^2\equiv b^2-4ac(mod \; p^{\alpha})\)

只有 \(p\) 是奇素数的时候成立,令 \(X=2ax+b,B=b^2-4ac\) ,有 \(X^2\equiv B(mod\; p^{\alpha})\)。

给定 \(m\in Z^{+},a\in Z,(a,m)=1\) 如果同余式 \(x^2\equiv a(nod\; m)\) 有解,则 \(a\) 叫做模 \(m\) 的二次剩余。

设 \(p\) 是奇素数,\((a,p)=1\) ,则

  1. \(a\) 是模 \(p\) 的二次剩余,当且仅当\(a^{\frac{p-1}{2}}\equiv 1(mod\; p)\) ,且 \(x^2\equiv a(nod\; m)\) 恰有两解。

设 \(p\) 是奇素数,\((a,p)=(b,p)=1\) ,则

  1. 如果 \(a,b\) 都是模 \(p\) 的二次剩余,则 \(ab\) 是模 \(p\) 的二次剩余
  2. 如果 \(a,b\) 都不是模 \(p\) 的二次剩余,则 \(ab\) 是模 \(p\) 的二次剩余

设 \(p\) 是奇素数,则模 \(p\) 的简化剩余系中,二次剩余和二次非剩余的个数都是 \(\frac{p-1}{2}\) 个,且 \(\frac{p-1}{2}\) 个二次剩余和序列 \(1^2,2^2,\cdots ,(\frac{p-1}{2})^2\) 中的一个数且仅有一个数同余。

勒让德符号

设 \(p\) 为素数,则定义勒让德符号 \((\frac{a}{p}) = \left\{\begin{matrix}
1 & \text{若} a \text{是模} p \text{的二次剩余} \\
-1 & \text{若} a \text{是模} p \text{的非二次剩余} \\
0 & \text{若} a|p
\end{matrix}\right.\)

如果 \(p\) 为奇素数可以发现 \((\frac{a}{p}) \equiv a^{\frac{p-1}{2}}(mod\; p)\) 。

  • \((\frac{a}{p})=(\frac{a+p}{p}) \)
  • \((\frac{ab}{p})=(\frac{a}{p}) (\frac{b}{p}) \)
  • 如果 \((a,p)=1\) ,\((\frac{a^2}{p})=1\)
  • \(a\equiv b(mod\; p)\) ,则
    • \((\frac{a}{p})= (\frac{b}{p})\)
    • \((\frac{ab^2}{p})= (\frac{a}{p})\)

高斯引理

设 \(p\) 为奇素数,\((a,p)=1\) ,如果整数 \(a(mod\; p),2a(mod \; p),\cdots , \frac{p-1}{2}a(mod\; p)\) 中大于 \(\frac{p}{2}\) 的个数是 \(m\) ,则 \((\frac{a}{p})=(-1)^m\)

  • 设 \(p\) 为奇素数,则
    • \((\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}\)
    • 设 \((a,2p)=1\) ,则 \((\frac{a}{p})= (-1)^{\sum _{k=1}^{\frac{p-1}{2}}[\frac{ak}{p}]}\)
  • 设 \(p\) 为奇素数,则
    • \((\frac{2}{p}) = \left\{\begin{matrix}
      1 & \text{若} p \equiv \pm 1(mod \; 8) \\
      -1 & \text{若} p \equiv \pm 3(mod \; 8) \\
      \end{matrix}\right.\)

二次互反率

\((\frac{p}{q})=(-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}(\frac{q}{p})\)

雅可比符号

设大于 \(1\) 的正奇数 \(m\) 表示为奇素数的乘积形式 \(m=p_1p_2\cdots p_s\),则对于任意与 \(m\) 互素的整数 \(a\) ,定义雅可比符号 \((\frac{a}{m})=(\frac{a}{p_1})(\frac{a}{p_2})\cdots (\frac{a}{p_s})\) 。

  • 雅可比符号的值,不能完全确定 \(a\) 是否是模 \(m\) 的二次剩余
  • 设 \(m\) 是正奇数,\(a\) 为奇数,若 \((\frac{a}{m})=-1\) ,则 \(a\) 是模 \(m\) 的二次非剩余
  • \((\frac{a+m}{m})=(\frac{a}{m})\)
  • \((\frac{ab}{m})=(\frac{a}{m})(\frac{b}{m})\)
  • \((\frac{a^2}{m})=1\)
  • \((\frac{1}{m})=1\)
  • \((\frac{-1}{m})=(-1)^{\frac{m-1}{2}}\)
  • \((\frac{2}{m})=(-1)^{\frac{m^2-1}{8}}\)
  • \((\frac{n}{m})=(-1)^{\frac{n-1}{2} \cdot \frac{m-1}{2}}(\frac{m}{n})\)

模 \(p\) 平方根算法

设 \(p\) 为奇素数, \(a\) 是和 \(p\) 互素的整数,且 \((\frac{a}{p})=1\) ,则同余式 \(x^2\equiv a(mod \; p)\) ,算法如下:

令 \(p-1=2^t\cdot s\) ,其中 \(s\) 为奇数,且 \(t\ge 1\) ,计算 \(x_{t-1}=a^{\frac{s+1}{2}}(mod \; p)\)

  • 如果 \(t=1\) ,则有 \(x_{t-1}^2=x_0^2\equiv a^{s+1}=a^{\frac{p-1}{2}}\cdot a\equiv (\frac{a}{p})\cdot a=a (mod \; p)\) ,因此 \(x_0\) 为同余式 \(x^2\equiv a (mod \; p)\)
  • 如果 \(t\neq 1\) ,任取模数 \(p\) 的二次非剩余 \(n\) ,则 \((\frac{n}{p})=-1\) ,计算 \(b=n^s (mod \; p)\) ,则有 \(b^{2^t}\equiv n^{2^t\cdot s}=n^{p-1}\equiv 1 (mod\; p )\) ,且 \(b^{2^{t-1}}=n^{\frac{p-1}{2}}\equiv -1 (mod \; p)\) 。同理可知 \((a^{-1} x_{t-1}^2)^{2^{t-1}}\equiv 1(mod \; p)\) .

原根

  • 设 \(m,a\in Z^{+},m > 1 , (a,m)=1\) , \(\varphi(m)\) 的标准分解式 \(\varphi(m)=p_1^{\alpha _1}p_2^{\alpha _2}\cdots p_s^{\alpha _s}\) ,则 \(a\) 是模 \(m\) 的原根当且仅当 \(a^{\frac{\varphi(m)}{p_i}}\not\equiv 1(mod\; m)\)
  • 设 \(m,a\in Z^{+},m > 1 , (a,m)=1\) ,\(a\) 不是模 \(m\) 的原根,设 \(a\) 模 \(m\) 的次数为 \(d\) ,则 \(a^k\) 不是模 \(m\) 的原根,其中 \(k=1,2,\cdots ,d\) 。
  • 设 \(m,a,b\in Z^{+},m > 1,(a,m)=(b,m)=1\)  ,则 \((ord_m(a),ord_b(m))=1\) 当且仅当 \(ord_m(ab)=ord_m(a)ord_m(b)\)
  • 设 \(m,a,b\in Z^{+},m,n > 1,(a,m)=(a,n)=1\) ,则
    • 若 \(m|n\) ,那么 \(ord_m(a)|ord_n(a)\)
    • 若 \((m,n)=1\) ,那么 \(ord_{mn}(a)=[ord_m(a),ord_n(a)]\)
  • 设 \(p,q\) 是不相同的素数,\(a\) 是正整数,\((a,p)=(a,q)=1\) ,则 \(ord_{pq}(a)=[ord_p(a),ord_q(a)]\)
  • 设 \(m,n\in Z^{+},(m,n)=1,m,n > 1\),则对 \(mn\) 互素的整数 \(a_1,a_2\) ,都存在整数 \(a\) ,使得 \(ord_{mn}(a)=[ord_m(a_1),ord_n(a_2)]\)
  • 设 \(m,a,b\in Z^{+},(a,m)=(b,m)=1\) ,则存在 \(c\in Z^{+}\) ,使得 \(ord_m(c)=[ord_m(a),ord_m(b)]\)
  • 原根存在性
    • 设 \(m\in Z^{+}\),则模 \(m\) 有原根当且仅当 \(m=2,4,p^{\alpha},2p^{\alpha}\) ,其中 \(p\) 为奇素数,\(\alpha \in Z^{+}\)
    • 设 \(p\) 为奇素数,\(g\) 为模 \(p\) 的原根,则 \(g\) 和 \(g+p\) 中必有一个模 \(p^2\) 的原根
    • 设 \(p\) 为奇素数,\(\alpha \ge 2\),\(g\) 为模 \(p^2\) 的原根,则 \(g\) 是模 \(p^{\alpha}\) 的原根
    • 设 \(p\) 为奇素数,\(\alpha \ge 1\),\(g\) 为模 \(p^{\alpha}\) 的原根,则 \(g\) 和 \(g+p^{\alpha}\) 是模 \(2p^{\alpha}\) 的原根

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 53,565

Categories

Archive

Comments