NumberTheory4


huangx607087学习数论的笔记4

1.欧拉$\phi()$函数的性质

任何数$n$的各个因数(包括$1$和自身)的$\phi$值之和等于$n$本身

例如:$15$的因数是$1,3,5,15$,$\phi(1)+\phi(3)+\phi(5)+\phi(15)=1+2+4+8=15$

(只上结论,不讲证明)

2.本原元(原根)

概念:使得$a^e\equiv 1 \pmod p$的最小$e$值为$p-1$的$a$值成为模$p$的本原元。

例如:$2^e\equiv 1 \pmod {11}$成立的最小$e$值为$10$,所以$2$是模$11$的本原元。而$3^e\equiv 1 \pmod {11}$成立的最小$e$值为$5$,所以$3$不是模$11$意义下的本原元。

在模$11$的意义下,我们可以设$\mathrm{ord}(x)$函数,此处有$\mathrm{ord}(2)=10,\mathrm{ord}(3)=5$。当然,如果放在模$7$的意义下,$\mathrm{ord}(2),\mathrm{ord}(3)$的值就分别变成了$3,6$。那么模$7$意义下,$3$就是本原元,$2$不是了。

我们看看在模$11$和模$7$的意义下各个数的$\mathrm{ord}$值

$x$ $\texttt{1}$ $\texttt{2}$ $\texttt{3}$ $\texttt{4}$ $\texttt{5}$ $\texttt{6}$ $\texttt{7}$ $\texttt{8}$ $\texttt{9}$ $\texttt{10}$
$\mathrm {ord}_7(x)$ $\texttt{1}$ $\texttt{3}$ $\texttt{6}$ $\texttt{3}$ $\texttt{6}$ $\texttt{2}$ $\texttt{undef}$ $\texttt{undef}$ $\texttt{undef}$ $\texttt{undef}$
$\mathrm {ord}_{11}(x)$ $\texttt{1}$ $\texttt{10}$ $\texttt{5}$ $\texttt{5}$ $\texttt{5}$ $\texttt{10}$ $\texttt{10}$ $\texttt{10}$ $\texttt{5}$ $\texttt{2}$

对于任意素数$p$来说,总有$\phi(p-1)$个本原元。例如:由于$\phi(10)=4$,所以模$11$的意义下,一共有$4$个本原元,分别是$2,6,7,8$。现在还没有求本原元的有效方法。不过根据表格,我们还可以观察到以下$3$个规律:
1. 任何小于$p$的$\mathrm{ord}$值均为$p-1$的因数
2. 二次剩余一定不是本原元,并且二次剩余的$\mathrm{ord}$值恰好为$\dfrac{p-1}{2}$
3. $\mathrm{ord}(p-1)=2$

COSTAS阵列

COSTAS阵列的性质:构建一个$p-1$阶的方阵,然后要求每行、每列都有一个$1$,其他元素均为$0$。并且任何两个$1$的连线的长度或斜率都不相同。

一般选择一个本源元即可构造一个COSTAS阵列。比如:$5$是模$7$意义下的一个本源元,于是有了序列$5,4,6,2,3,1$。所以我们可以构建一个$6×6$的矩阵$A$

1

存在$k$使得$A^k=E=\mathrm{diag}(1,1,1,1,1,1)$

3.指标(即离散对数)

由$2^9\equiv 5 \pmod {13}$,可以记为$I(5)=9\equiv \dfrac{\ln5}{\ln2} \pmod {13}$

当我们规定底数$a$时,我们可以设$I(x)=\dfrac{\ln x}{\ln a}$的对数形式,该对数的运算与数学上已知的对数形式一模一样。这也是我后面博客里谈到离散对数问题所要考虑到的东西。

我们也可以做个表,设$p=7,a=5$,那么$I(1)$到$I(6)$分别为$6,4,5,2,1,3$。如果我们想要计算$3×5$,我们可以查表得$I(3)=5,I(5)=3,5+3\equiv 1\pmod 7$所以我们可以得到$3×5\equiv1\pmod7$

不过离散对数中得密码学也是个极其难解的问题,后面如果可以,会增加相关推文。

4.二项式定理模$p$扩充

两个结论:
1.$\mathrm{C}_p^k \equiv 0 \pmod p,k \not = 0,p$
2.若$p$为素数,有$(A+B)^p\equiv A^p+B^p \pmod p$

5.Fibonacci数列

一般的Fibonacci数列:$1,1,2,3,5,8,……$,有$F_1=F_2=1,F_{n}=F_{n-1}+F_{n-2}$

1.类Fibonacci数列的求通项公式的方法

可以使用矩阵运算:

2

并且这个方法还可以推广到矩阵快速幂的计算上去。

我们可以扩展以下:假如有一个数列$G_n=aG_{n-1}+bG_{n-2}$,并给出初值$G_1,G_2$,我们可以构造下面的矩阵。

3

如果想求通项公式,只需要求出最左边矩阵的$2$个特征值$E_1,E_2$,那么通项公式就是$G_n=C_1E_1^n+C_2E_2^n$,带入初值即可求得待定系数。

我们可以继续扩展到三阶矩阵:$H_n=aH_{n-1}+bH_{n-2}+cH_{n-3}$

4

然后同样是求特征值之后用待定系数法利用初值列方程求解。

Fibonacci数列的模$p$周期

对于任意素数,有$T(p^k)=p^{k-1}T(p)$。

$T(2)=3,T(5)=20$是两个特殊值

如果$p\equiv 1 \text8{ or }4 \pmod 5$,那么$T(p)=p$。如果$p\equiv2 \text{ or } 3 \pmod 5$,那么$T(p)=2p+2$

当$a$是合数,$p$是不同的素数时,$a=p_1^{e_1}p_2^{e_2}…p_n^{e_n}$时,$T(a)=T(p_1)T(p_2)…T(p_n)$。

例如:$72=2^3×3^2$,那么有$T(72)=T(2)T(3)=3×8=24$


文章作者: huangx607087
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 huangx607087 !
  目录