半阶

hbghlyj

抄一下半阶的一点想法 隐藏/显示

问题：对于什么样的 $a$ 及素数 $p$ ，使得 $a^{k}+1\equiv 0\pmod p$ 有解 $k$ ? 我们知道 $a^{t}\equiv 1\pmod p$ 的最小解是 $\delta_p(a)$ 叫做阶，那么上述最小的解 $k$ 就称为半阶。 但是，半阶是不一定每个存在的。查阅[1]发现

当 $m \geqslant 3,(a, m)=1$ 时, 满足 $a^{x} \equiv-1\pmod m$ 的最小正整数 $x$ 称为 $a$ 关于 $m$ 的半阶. 需要注意的是半阶不一定存在. 例如, 2 关于模 15 的半阶就不存在.

半阶什么时候存在呢？ 设 $\text{mod}\ p$ 的一个原根为 $g$ ，并且设 $a\equiv g^t\pmod p$ 。 我们知道 $g^{\frac{p-1}{2}}\equiv-1\pmod p$ ，于是问题转化为: 是否存在 $k$ ，使得$g^{k\cdot t}\equiv g^{\frac{p-1}{2}}\pmod p$ 由费马小定理及原根的性质，这等价于 $k\cdot t\equiv \frac{p-1}{2}\pmod{p-1}$ 即存在 $l$ ，使得 $k\cdot t= \frac{p-1}{2}+l(p-1)$ 即 $k\cdot t= \frac{p-1}{2}\cdot(2l+1)$ 。（这里面 $k,l$ 都是任取的） 即 $t| \frac{p-1}{2}\cdot(2l+1)$ 。 分析两边的质因子，发现右边的奇质因子可以任意多，而 $2$ 的幂次是有限的。于是我们只需要 $\nu_{2}(t)\leq \nu_{2}(p-1)-1$ 。（其中 $\nu_{p}(n)$ 表示 $n$ 中含有 $p$ 幂次的个数）。这就得到了所要的答案。

参考文献

[1] 利用阶与半阶解数论问题_田开斌.pdf (463.76 KB, Downloads: 53)

2023-2-20 01:56 Upload

Click on the file to download the attachment

[J]. 中等数学(High-School Mathematics), 2014-05-15, 000(005):2-6.

hbghlyj

Euler's criterion
Kernel/image of map between units of ring

Suppose $p$ is an odd prime. Show that the map $\phi : \mathbb{F}_p^* \rightarrow \mathbb{F}_p^*$ (where $\mathbb{F}_p$ is $\mathbb{Z}/p\mathbb{Z}$, and $\mathbb{F}_p^*$ denotes the set of units of  $\mathbb{F}_p$) given by $x \mapsto x^{(p-1)/2}$ has kernel of size at most $(p-1)/2$, and hence has image $\{\pm1\}$.
Deduce that if $p \equiv 1 \ \text{mod} \ 4$ then $-1$ is a square modulo $p$

One way is to note that $\ker(\phi)$ is precisely the solutions to the polynomial $X^{(p-1)/2}-1\in\mathbb{F}_p[X]$, which has at most $(p-1)/2$ solutions as a polynomial of degree $(p-1)/2$ over a field. To see that there are at least $(p-1)/2$ solutions, in order to conclude $\mathrm{im}(\phi)=\{\pm 1\}$, you can use the fact that $\mathbb{F}_p^\ast$ is cyclic, and then consider the even powers of the generator.

Then from the isomorphism theorems,
$$
\mathbb{F}_p^\ast/\ker(\phi)\simeq\operatorname{im}(\phi)
$$
so that
$$
|\operatorname{im}(\phi)|=|\mathbb{F}_p^\ast/\ker(\phi)|=(p-1)/((p-1)/2))=2.
$$
But the only subgroup of order $2$ in $\mathbb{F}_p^\ast$ is necessarily $\{\pm 1\}$, as it must contain $1$ and an element of order $2$. But $-1$ is the unique element of order $2$. To see this, note any element of order $2$ is a root of $X^2-1=(X-1)(X+1)\in\mathbb{F}_p[X]$, and $\mathbb{F}_p[X]$ is an integral domain...

hbghlyj

费马小定理和欧拉定理是数论中非常重要的两个定理,是解决整除问题和同余问题的有力武器.同时,与这两个定理相关的阶与半阶,在解决某些问题时也有着强大的功能.本文简要介绍阶与半阶的概念,并通过几道例题,讲述其应用.

基础知识

(1)欧拉函数
对于任意正整数$m$, $φ(m)$表示不大于$m$且与$m$互素的正整数的个数.

设$m$的标准分解式为$$
m=p_1^{\alpha_1} p_2^{\alpha_4} \cdots p_k^{\alpha_k}
$$
则 $\varphi(m)=m\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots\left(1-\frac{1}{p_k}\right)$.

(2)欧拉定理
若$(a,m)=1$,则$a^{φ(m)}≡1\pmod m$.

(3)费马小定理
若$p$为素数, 且$(a,p)=1$, 则$a^{p-1}≡1\pmod m$.

(4)阶数与原根
当$(a,m)=1$时,则存在最小的正整数$λ$使得$a^\lambda \equiv 1\pmod m$, 称$λ$为$a$关于$m$的阶数.
显然, $λ≤φ(m)$.
若$λ=φ(m)$, 则称$a$为$m$的原根.

阶数的性质:
(i)$1,a,a^2,…,a^{λ-1}$中的任何两个数对$m$不同余;
(ii) $a^t \equiv 1\pmod n \Leftrightarrow \lambda \mid t$;
(iii) $\lambda\mid\varphi(m)$;
(ⅳ) 若$a$为$m$的原根, 则$1,a,a^2,…,a^{λ-1}$构成模$m$的一组简系.

(5)半阶
当 $m \geqslant 3,(a, m)=1$ 时, 满足 $a^{x} \equiv-1\pmod m$ 的最小正整数 $x$ 称为 $a$ 关于 $m$ 的半阶.
需要注意的是半阶不一定存在. 例如, 2 关于模 15 的半阶就不存在.

半阶的性质:
(i)设$m≥3,(a,m)=1$,若$a$关于模$m$的阶为$λ$,半阶为$τ$,则$λ=2τ$;
(ii)设$m≥3,(a,m)=1$,$a$关于模$m$的半阶为$τ$,若正整数$t$使得$a^t≡-1 \pmod m$,则$t$为$τ$的奇数倍.

例1. 设$m∈\Bbb Z^+$.若$(2^{m+1}+1)\mid(3^{2^m}+1)$, 证明:$2^{m+1}+1$是素数.^{[2](2003,韩国数学奥林匹克)}

证明

根据条件知$3^{2^m} \equiv-1\pmod{2^{m+1}+1}$
所以,$3^{2^{m+1}}≡1\pmod{2^{m+1}+1}.$
设3关于模$2^{m+1}+1$的阶数为$λ$.
则$λ\mid2^{m+1}$,且$λ\midφ(2^{m+1}+1)$.
若$λ=2^{k}(k≤m)$,则$$
3^{2^m} \equiv\left(3^{2^k}\right)^{2^{m-k}} \equiv 1\pmod{2^{m+1}+1}.
$$这与$3^{2^m}≡-1\pmod{2^{m+1}+1}$矛盾.
所以$λ=2^{m+1}$.
故$2^{m+1}\midφ(2^{m+1}+1)$.
若$2^{m+1}+1$不是素数,设$p$为其任意一个素因子.易知,$$
\varphi\left(2^{m+1}+1\right) \leqslant\left(2^{m+1}+1\right)\left(1-\frac{1}{p}\right)<2^{m+1}
$$这与$2^{m+1}\midφ(2^{m+1}+1)$矛盾.
因此, $2^{m+1}+1$为素数.

例2. 求所有的整数$m$、$n$使得 $m n\mid\left(3^m+1\right)$, $m n\mid\left(3^n+1\right)$ ^{[3](2005,韩国数学奥林匹克)}

解

分两种情形讨论.
(1)$m$、$n$中有一个为$1$.
不妨设$m=1$. 则$mn=n,3^{m}+1=4$.
从而,$n\mid4⇒n=1,2或4$.
经检验,知$(m,n)=(1,1),(1,2)$满足题设条件.
对称地,此时方程的解为$(m, n)=(1,1),(1,2),(2,1)$.

(2) $m≥2,n≥2$.
若$m$、$n$同为偶数,则$4∣(3^{m}+1)$.
而$3^{m}+1≡(-1)^{m}+1≡2\pmod4$,故$4 \nmid\left(3^m+1\right)$矛盾.
于是,$m$、$n$中至少有一个为奇数,不妨设$m$为奇数.
设$p$为$m$的最小素因子.
注意到,$3\nmid(3^{m}+1)$.所以,$p≥5$.
而 $m n∣\left(3^m+1\right) \Rightarrow p∣\left(3^m+1\right)
\Rightarrow 3^m \equiv-1\pmod p \Rightarrow 3^{2 m} \equiv 1\pmod p$
又根据费马小定理知$3^{p-1} \equiv 1\pmod p$
设3关于$p$的阶为$λ$.则$$3^\lambda \equiv 1\pmod p, \lambda∣2 m, \lambda∣(p-1), \lambda \nmid m$$
注意到, $p$为$m$的最小素因子.
所以$(m,p-1)=1$.
从而$(2m,p-1)=2$.
于是$λ∣2⇒λ=2$.
因此$3^{2}≡1\pmod p⇒p∣8$, 这与$p≥5$为素数矛盾.
综上,满足条件的$(m, n)=(1,1),(1,2),(2,1)$

References
[1] 王连笑.费马小定理与欧拉定理的应用[J].中等数学,2010(11).
[2] 第16届韩国数学奥林匹克(2003)[J].中等数学,2004(增刊).
[3] 第18届韩国数学奥林匹克(2005)[J].中等数学,2006(增刊).

hbghlyj

Proposition 5.1. Suppose that $n \equiv 3\pmod4
$. Then $n$ is prime if and only if the following is true: for every $a \in(\mathbb{Z} / n \mathbb{Z})^{\times}, a^{(n-1) / 2} \equiv \pm 1\pmod n
$.

Proof. We have already shown the "only if" direction in proving Euler's criterion. (This bit does not use the fact that $n \equiv 3\pmod4
$.) Conversely, we must show that if $n \equiv 3\pmod4
$ is composite then there is some $a \in(\mathbb{Z} / n \mathbb{Z})^{\times}$with $a^{(n-1) / 2} \not \equiv$ $1\pmod n
$

Suppose first that $n=p^k$ is a prime power, $k \geqslant 2$. Consider $a=1+p$. Then
$$
a^{(n-1) / 2}=1+p \frac{n-1}{2}+p^2 m
$$
for some integer $m$, by the binomial theorem. This certainly cannot be $-1\pmod{p^k}$ (it's not even $-1\pmod p
)$. It is also not $1\pmod{p^k}$ since, though $a^{(n-1) / 2}-1$ is divisible by $p$, it is not divisible by $p^2$.

Now suppose that $n$ is not a prime power, say $n=p^k n'$ with $\left(n', p\right)=1$. By the Chinese remainder theorem, there is $a$ with $a \equiv-1\pmod{p^k}$ and $a \equiv 1\pmod{n'}$. But then $a^{(n-1) / 2} \equiv-1\pmod{p^k}$ (since $(n-1) / 2$ is odd $)$ and $a^{(n-1) / 2} \equiv 1\pmod{n'}$. Thus $a^{(n-1) / 2} \not \equiv \pm 1\pmod{n'}$, because $-1 \not \equiv 1\pmod{n'}$ and $-1 \not \equiv 1\pmod{p^k}$.