关于欧拉定理的疑问

longzaifei · 发表于 2014-3-26 08:39

本帖最后由 hbghlyj 于 2023-11-7 20:23 编辑 欧拉定理：若 $n,a$为正整数且互素，则 $ a^{\varphi(n)} \equiv 1 \pmod n$.

$\varphi(n)$不一定是最小的使上式成立的正整数。
我想问的是：如果使上式成立的最小正整数不是$\varphi(n)$，那么一定是$\varphi(n)$的二分之一，或者四分之一，或者八分之一。。？？？

Czhang271828 · 发表于 2022-2-19 17:54

老问题了, 这个问题可以用简单的群论基本讲透. 我们大致分为这么几步进行.

Step 1. $(\mathbb Z_n,+)$ 对加法构成群, 但对乘法不一定. 我们记 $\mathbb Z_n^*:=\{a:\gcd(a,n)=1\}$, 则 $(\mathbb Z_n^*,\cdot)$ 构成群.

所谓群就是带有某一二元运算 $\ast$ 的集合 $S$ 满足 $\forall x,y\in S$ 都有 $x\ast y\in S$, 即二元运算封闭性. 此外存在单位元 $e\in S$ 使得 $\forall x\in S$ 都有 $xe=ex=x$. 对任意 $x\in S$ 存在逆元 $y$ 使得 $xy=yx=e$. 此处易证明单位元和逆元均唯一.

Step 2. 记 $p_i$ 为第 $i$ 个质数, 设 $n$ 的准素分解为 $n=\prod_{i\geq 1}p_i^{n_i}$. 根据中国剩余定理有
$$
\mathbb Z_n^*=\bigoplus_{i\geq 1}\mathbb Z_{p_i^{n_i}}^*
$$
此处 $\oplus$ 为直和, 即 $\mathbb Z_n^*$ 可以和 $\{(x_1,x_2,\ldots):x_i\in \mathbb Z_{p_i^{n_i}}^*\}$ 一一对应.

Step 3. 由群论知识可得
1. $(\mathbb Z_2^*,\cdot )\cong (\{0\},+)$.
2. $(\mathbb Z_{2^{n+2}}^*,\cdot)\cong (\mathbb Z_{2^n}\oplus \mathbb Z_2,+)$ for any $n=0,1,2,\ldots$.
3. $(\mathbb Z_{p^n}^*,\cdot)\cong (\mathbb Z_{p^n-p^{n-1}},\cdot)$ for any prime number except $2$.

例如对 $\mathbb Z_8^*=\{1,3,5,7\}$ 而言, 有对应
$$
\begin{align*}
\cdot\quad&\Leftrightarrow &&+\\
\mathbb Z_8^*\quad&\Leftrightarrow &&\mathbb Z_2\oplus\mathbb Z_2\\
1\quad&\Leftrightarrow &&(0,0)\\
3\quad&\Leftrightarrow &&(1,0)\\
5\quad&\Leftrightarrow &&(0,1)\\
7\quad&\Leftrightarrow &&(1,1)\\
3\cdot 5\equiv 7\quad&\Leftrightarrow && (1,0)+(0,1)=(1,1)
\end{align*}
$$
Step 4. 由有限 Abel 群分类定理知, 对任意互质的整数 $a,b$, 均有 $\mathbb Z_{ab}\cong\mathbb Z_a\times \mathbb Z_b$. 于是我们可得到以下结论:

Ex 1. 以 $n=360$ 为例, 所有与 $360$ 互质的元素同构于群
$$
\begin{align*}
\mathbb Z_{360}^*\cong & \mathbb Z_{8}^*\oplus \mathbb Z_{9}^*\oplus \mathbb Z_{5}^*\\
\cong&(\mathbb Z_2\oplus\mathbb Z_2)\oplus \mathbb Z_6\oplus\mathbb Z_4\\
\cong& \mathbb Z_2\oplus \mathbb Z_2\oplus \mathbb Z_2\oplus \mathbb Z_3\oplus \mathbb Z_4
\end{align*}
$$
从而与 $360$ 互质的元素可以写作 $(a,b,c,d,f)$ 的形式, 其中 $a,b,c\in\mathbb Z_2$, $d\in\mathbb Z_3$, $f\in\mathbb Z_4$. 由于有限群 $G$ 中任意元素 $x$ 满足 $x^{|G|}=e$, 从而
$$
a^{12}\equiv 1\mod 360.
$$
是不是远小于 $\varphi(360)=96$?

求出这些数也简单, 观察 $\mathbb Z_2\oplus \mathbb Z_2\oplus \mathbb Z_2\oplus \mathbb Z_3\oplus \mathbb Z_4$, 每个群的循环阶数为 $(2,2,2,3,4)$, 其中 $3$ 与 $4$ 为主要的循环阶数. 顺着往前, 即是$\mathbb Z_9^*$ 中的 $3$ 阶或 $6$ 阶元 $\{2,4,5,7\}$ 与 $\mathbb Z_5^*$ 中的 $4$ 阶元 $\{2,4\}$ 了. 从而使得 $a^{12}\equiv 1\mod 360$ 取等的 $a$ 为
$$
\{a:a\equiv 2,4,5,7\mod 9\}\cap \{a:a\equiv 2,4\mod 5\}
$$
共 $64$ 个元素.

Prop. 由上述步骤可知, 不等式中指数 $\varphi(n)$ 能取到若且仅若 $n$ 为以下中的一者: $1$, $2$, $4$, 奇素数幂, 或两倍奇素数幂. 此时 $\mathbb Z_n^*$ 无非 $\varphi(p)$ 阶循环群. 循环群生成元数量即原根数量, 为 $\varphi(\varphi(n))$.

hbghlyj · 发表于 2022-6-17 05:07

Mathworld
Wikipedia

WolframAlpha

FiniteGroupData[{"CyclicGroupUnits", 360},"Name"]

group of units of the cyclic group of order 360

WolframAlpha

Select[Range[360], CoprimeQ[#, 360]&]

{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 119, 121, 127, 131, 133, 137, 139, 143, 149, 151, 157, 161, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 203, 209, 211, 217, 221, 223, 227, 229, 233, 239, 241, 247, 251, 253, 257, 259, 263, 269, 271, 277, 281, 283, 287, 289, 293, 299, 301, 307, 311, 313, 317, 319, 323, 329, 331, 337, 341, 343, 347, 349, 353, 359}

WolframAlpha

FiniteGroupData[{"CyclicGroupUnits", 360},"Elements"]

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96}

WolframAlpha

FiniteGroupData[{"CyclicGroupUnits", 360},"Order"]

96

WolframAlpha

FiniteGroupData[{"CyclicGroupUnits", 360},"Classes"]

FiniteGroupData[{"CyclicGroupUnits", 360},"Properties"]

FiniteGroupData[{"CyclicGroupUnits", 360},"CycleGraph"]

WolframAlpha

FiniteGroupData[{"CyclicGroupUnits", 360},"CayleyGraph"]

WolframAlpha

FiniteGroupData[{"CyclicGroupUnits", 360},"Cycles"]

{{1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}, {6, 1}, {7, 1}, {8, 1}, {9, 17, 1}, {10, 17, 2, 9, 18, 1}, {11, 17, 3, 9, 19, 1}, {12, 17, 4, 9, 20, 1}, {13, 17, 5, 9, 21, 1}, {14, 17, 6, 9, 22, 1}, {15, 17, 7, 9, 23, 1}, {16, 17, 8, 9, 24, 1}, {17, 9, 1}, {18, 9, 2, 17, 10, 1}, {19, 9, 3, 17, 11, 1}, {20, 9, 4, 17, 12, 1}, {21, 9, 5, 17, 13, 1}, {22, 9, 6, 17, 14, 1}, {23, 9, 7, 17, 15, 1}, {24, 9, 8, 17, 16, 1}, {25, 49, 73, 1}, {26, 49, 74, 1}, {27, 49, 75, 1}, {28, 49, 76, 1}, {29, 49, 77, 1}, {30, 49, 78, 1}, {31, 49, 79, 1}, {32, 49, 80, 1}, {33, 65, 73, 9, 41, 49, 81, 17, 25, 57, 89, 1}, {34, 65, 74, 9, 42, 49, 82, 17, 26, 57, 90, 1}, {35, 65, 75, 9, 43, 49, 83, 17, 27, 57, 91, 1}, {36, 65, 76, 9, 44, 49, 84, 17, 28, 57, 92, 1}, {37, 65, 77, 9, 45, 49, 85, 17, 29, 57, 93, 1}, {38, 65, 78, 9, 46, 49, 86, 17, 30, 57, 94, 1}, {39, 65, 79, 9, 47, 49, 87, 17, 31, 57, 95, 1}, {40, 65, 80, 9, 48, 49, 88, 17, 32, 57, 96, 1}, {41, 57, 73, 17, 33, 49, 89, 9, 25, 65, 81, 1}, {42, 57, 74, 17, 34, 49, 90, 9, 26, 65, 82, 1}, {43, 57, 75, 17, 35, 49, 91, 9, 27, 65, 83, 1}, {44, 57, 76, 17, 36, 49, 92, 9, 28, 65, 84, 1}, {45, 57, 77, 17, 37, 49, 93, 9, 29, 65, 85, 1}, {46, 57, 78, 17, 38, 49, 94, 9, 30, 65, 86, 1}, {47, 57, 79, 17, 39, 49, 95, 9, 31, 65, 87, 1}, {48, 57, 80, 17, 40, 49, 96, 9, 32, 65, 88, 1}, {49, 1}, {50, 1}, {51, 1}, {52, 1}, {53, 1}, {54, 1}, {55, 1}, {56, 1}, {57, 17, 49, 9, 65, 1}, {58, 17, 50, 9, 66, 1}, {59, 17, 51, 9, 67, 1}, {60, 17, 52, 9, 68, 1}, {61, 17, 53, 9, 69, 1}, {62, 17, 54, 9, 70, 1}, {63, 17, 55, 9, 71, 1}, {64, 17, 56, 9, 72, 1}, {65, 9, 49, 17, 57, 1}, {66, 9, 50, 17, 58, 1}, {67, 9, 51, 17, 59, 1}, {68, 9, 52, 17, 60, 1}, {69, 9, 53, 17, 61, 1}, {70, 9, 54, 17, 62, 1}, {71, 9, 55, 17, 63, 1}, {72, 9, 56, 17, 64, 1}, {73, 49, 25, 1}, {74, 49, 26, 1}, {75, 49, 27, 1}, {76, 49, 28, 1}, {77, 49, 29, 1}, {78, 49, 30, 1}, {79, 49, 31, 1}, {80, 49, 32, 1}, {81, 65, 25, 9, 89, 49, 33, 17, 73, 57, 41, 1}, {82, 65, 26, 9, 90, 49, 34, 17, 74, 57, 42, 1}, {83, 65, 27, 9, 91, 49, 35, 17, 75, 57, 43, 1}, {84, 65, 28, 9, 92, 49, 36, 17, 76, 57, 44, 1}, {85, 65, 29, 9, 93, 49, 37, 17, 77, 57, 45, 1}, {86, 65, 30, 9, 94, 49, 38, 17, 78, 57, 46, 1}, {87, 65, 31, 9, 95, 49, 39, 17, 79, 57, 47, 1}, {88, 65, 32, 9, 96, 49, 40, 17, 80, 57, 48, 1}, {89, 57, 25, 17, 81, 49, 41, 9, 73, 65, 33, 1}, {90, 57, 26, 17, 82, 49, 42, 9, 74, 65, 34, 1}, {91, 57, 27, 17, 83, 49, 43, 9, 75, 65, 35, 1}, {92, 57, 28, 17, 84, 49, 44, 9, 76, 65, 36, 1}, {93, 57, 29, 17, 85, 49, 45, 9, 77, 65, 37, 1}, {94, 57, 30, 17, 86, 49, 46, 9, 78, 65, 38, 1}, {95, 57, 31, 17, 87, 49, 47, 9, 79, 65, 39, 1}, {96, 57, 32, 17, 88, 49, 48, 9, 80, 65, 40, 1}}

WolframAlpha

FiniteGroupData[{"CyclicGroupUnits", 360},"CycleIndex"]@@{a,b,c,d}

$$(a^2 + b)^3 (a^3 + 2 c) (a^4 + b^2 + 2 d)\over96$$

WolframAlpha

FiniteGroupData[{"CyclicGroupUnits", 360},"IsomorphicGroups"]

\begin{pmatrix}96 &6\\\text{AbelianGroup} & \{4, 3, 2, 2, 2\}\end{pmatrix}
WolframAlpha

group of units of the cyclic group of order 360 Abelian decomposition

$ℤ_4×ℤ_3×ℤ_2×ℤ_2×ℤ_2$

hbghlyj · 发表于 2022-6-17 05:46

A group is cyclic if there is an element whose order is the group order. The order of {"CyclicGroupUnits", n} is EulerPhi[n], while CarmichaelLambda[n] gives the maximum order amongst its elements.

The condition EulerPhi[n]==CarmichaelLambda[n] is only obeyed for positive integers n of the form 2, 4, p^k, 2p^k with prime p≠2 and k≥1.

Wolfram language reference

hbghlyj · 发表于 2022-6-17 05:55

我想问的是：如果使上式成立的最小正整数不是$\varphi(n)$，那么一定是$\varphi(n)$的二分之一，或者四分之一，或者八分之一。。？？？

Carmichael's lambda function is the reduced totient function. It is the smallest positive divisor of Euler's totient function that satisfies the conclusion of Euler's theorem.
brilliant.org/wiki/carmichaels-lambda-function/

Definition

Let $ n $ be a positive integer. Then $ \lambda(n) $ is defined to be the smallest positive integer $ k $ such that $$ a^k \equiv 1 \pmod n $$ for all $ a $ such that $ \text{gcd}(a,n)=1.$

Note that $ \lambda(n) $ always exists because $ k= \phi(n) $ satisfies the equation above, by Euler's theorem. So $ \lambda(n) \le \phi(n).$ In fact, $ \lambda(n)|\phi(n),$ by a standard division algorithm argument: let $ \phi(n) = \lambda(n) q+r,$ $ 0 \le r < \lambda(n);$ then it's clear that $ a^r \equiv 1 \pmod n$ for all $ a $ coprime to $ n.$ This contradicts minimality of $\lambda(n) $ unless $ r=0.$

Computing Carmichael's Function

Values of Carmichael's lambda function can be calculated using the following formulas:

We have

$$\begin{aligned} \lambda\left(p^{\alpha}\right) &= \begin{cases} \phi\left(p^{\alpha}\right) &\text{ if } \alpha \leq 2 \text{ or } p \geq 3 \\ \frac{1}{2} \phi\left(p^{\alpha}\right) &\text{ if } \alpha \geq 3 \text{ and } p = 2 \end{cases} \\\\ \lambda\left( {p_1}^{\alpha_1} \cdots {p_k}^{\alpha_k} \right) &= \text{lcm} \, \big(\lambda\left({p_1}^{\alpha_1}\right), \cdots, \lambda\left({p_k}^{\alpha_k}\right)\big), \end{aligned}$$

where the $ p_i $ are distinct positive prime numbers.

These formulas will be proved in the next section. Two immediate consequences are as follows:

If $ a|b,$ then $ \lambda(a)|\lambda(b).$
$ \lambda\big(\text{lcm}(a,b)\big) = \text{lcm}\big(\lambda(a),\lambda(b)\big).$

Find the smallest positive integer $ a $ such that $ 360|(x^a-1) $ for any $ x $ relatively prime to $ 360. $

We have $ \lambda(360) = \text{lcm}\big(\lambda(2^3),\lambda(3^2),\lambda(5)\big) = \text{lcm}(2,6,4) = 12. $ $_\square$

Note in this example that $ 360\Big|x^3(x^{12}-1) $ for all $ x,$ since $ 2^3,3^2,5 $ all either divide $ x^3$ or $ x^{12}-1 $ depending on whether $ x $ is divisible by $2,3,5$ respectively.

Proof of the Formulas

Let $ p $ be an odd prime. An element of order $ \phi(p^\alpha) $ in $ \left( {\mathbb Z}/p^\alpha{\mathbb Z} \right)^* $ is called a primitive root. The wiki on primitive roots contains the full classification of integers $n$ for which there is a primitive root mod $ n;$ in particular, there is a primitive root $ g$ mod $ n$ when $ n $ is an odd prime power. Since the smallest positive integer power of $ g $ that is congruent to $ 1 $ is $ g^{\phi(p^{\alpha})},$ this shows that $ \lambda(p^{\alpha}) \ge \phi(p^\alpha).$ Since $ \lambda(p^{\alpha}) \le \phi(p^{\alpha}) $ from the discussion in the previous section, this shows that they are equal.

When $ p=2,$ the primitive roots wiki shows that $ \lambda(2^{\alpha})\big|2^{\alpha-2}$ for $ \alpha \ge 3,$ and an easy induction shows that $ 5^{2^{\alpha-3}} \equiv 1 + 2^{\alpha-1} \pmod {2^{\alpha}},$ so the order of $ 5 $ does not divide $ 2^{\alpha-3},$ but it is a power of 2, so it is $ 2^{\alpha-2}.$ This shows that $ \lambda(2^{\alpha}) = 2^{\alpha-2} = \frac12 \phi(2^{\alpha}).$

The last statement is a straightforward application of the Chinese remainder theorem. In particular, if $ n = p_1^{\alpha_1}\cdots p_k^{\alpha_k},$ then for any choice of primitive roots $ g_i \mod p_i^{\alpha_i}$ $\big($and $ g_i=5$ if $ p_i^{\alpha_i}$ is a power of 2 greater than 4$\big),$ there is a unique element $ g$ mod $ n $ that is congruent to each of the $ g_i$ mod $ p_i^{\alpha_i},$ and it is easy to show that the order of $ g $ equals the LCM of the $ \lambda(p_i^{\alpha_i}).$ On the other hand, a similar Chinese remainder theorem argument shows that any element raised to that LCM must be $ 1 $ mod $ n$ since it is $ 1 $ modulo all the prime powers. $_\square$

One important fact that is immediate from the proof is there is always an element $g \in ({\mathbb Z}/n{\mathbb Z})^*$ whose multiplicative order equals $ \lambda(n).$ Such $ g $ are sometimes called primitive lambda-roots.

Find a primitive lambda-root modulo $ 720.$

Start with $ \lambda(144) = \text{lcm}\big(\lambda(2^4),\lambda(3^2),\lambda(5)\big) = \text{lcm}(4,6,4) = 12.$ The idea is to find primitive lambda-roots modulo $ 2^4, $ $ 3^2, $ and $ 5,$ and apply the Chinese remainder theorem. $ 5 $ always works modulo powers of $ 2,$ and $ 5 $ is actually a primitive root modulo $ 3^2 $ as well. For a primitive root mod $ 5,$ $ 3 $ will suffice. So now solve $$\begin{aligned} x &\equiv 5 \pmod{2^4} \\ x &\equiv 5 \pmod{3^2} \\ x &\equiv 3 \pmod{5} \end{aligned}$$ to get the solution $ x \equiv 293 \pmod{720}.$ This is not unique (exercise: how many different primitive lambda-roots are there?). $_\square$

Application to Primality Testing

Since Fermat's little theorem implies that $ a^{p-1} \equiv 1 \pmod p $ for all positive integers $ a$ less than a given prime $ p,$ a natural test for primality is as follows: given a large number $n,$ pick an integer $ a<n$ and compute $ a^{n-1} \pmod n.$ If the answer is not $ 1,$ then $ n $ is not prime.

But if $ a^{n-1} \equiv 1 \pmod n $ $\big($and $ \text{gcd}(a,n)=1\big),$ is it possible to say that $ n$ is prime? The answer is no; for instance, $ 2^{340} \equiv 1 \pmod {341},$ but $341 = 11\cdot 31.$ On the other hand, $ 3^{340} \equiv 56 \not\equiv 1 \pmod {341},$ so varying the choice of $ a $ takes care of $ 341.$

Unfortunately, there are some composite values of $ n $ for which any choice of $ a $ relatively prime to $ n $ will result in an inconclusive test. If $ \lambda(n)\big|(n-1),$ say $ \lambda(n)k = n-1,$ then $ a^{n-1} \equiv \big(a^{\lambda(n)}\big)^k \equiv 1 \pmod n,$ so no choice of $ a $ will show that $ n $ is composite. A composite number $n $ which cannot be proved composite by this primality test is called a Carmichael number. By a division algorithm argument (similar to the one given earlier in this wiki), the converse of this criterion is true as well: $ n$ is a Carmichael number if and only if $ \lambda(n)\big|(n-1).$

$ \lambda(561) = \text{lcm}\big(\lambda(3),\lambda(11),\lambda(17)\big)=\text{lcm}(2,10,16) = 80,$ which divides $ 560.$ So $ 561$ is a Carmichael number (in fact, it is the smallest Carmichael number).

See the Carmichael numbers wiki for more details.

——————————————————————————————————————

en.wikipedia.org/wiki/Carmichael_function

The following table compares the first 36 values of $λ(n)$ (sequence A002322 in the OEIS) with Euler's totient function $φ$ (in bold if they are different; the $n$s such that they are different are listed in OEIS: A033949).

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36
$λ(n)$	1	1	2	2	4	2	6	2	6	4	10	2	12	6	4	4	16	6	18	4	6	10	22	2	20	12	18	6	28	4	30	8	10	16	12	6
$φ(n)$	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8	12	10	22	8	20	12	18	12	28	8	30	16	20	16	24	12

hbghlyj · 发表于 2022-6-17 06:59

我想问的是：如果使上式成立的最小正整数不是$\varphi(n)$，那么一定是$\varphi(n)$的二分之一，或者四分之一，或者八分之一。。？？？

这是错误的，例如$\dfrac{ϕ(63)}{λ(63)}=6$不是2的幂，$\dfrac{ϕ(91)}{λ(91)}=6$不是2的幂。
利用下面这段代码

Pick[Range[10000],
Function[n, BitClear[n, BitLength[n] - 1] != 0]@*
Function[n, EulerPhi[n]/CarmichaelLambda[n]] /@ Range[10000]]

复制代码

可以找到1到10000的不符合“$\dfrac{ϕ(n)}{λ(n)}$是2的幂”的$n$
{63,91,117,126,133,171,182,189,217,234,247,252,259,266,273,275,279,301,315,333,341,342,351,364,378,387,399,403,427,434,441,451,455,468,469,481,494,504,511,513,518,532,546,549,550,553,558,559,567,585,589,602,603,630,637,651,657,665,666,671,679,682,684,693,702,703,711,721,728,741,756,763,774,775,777,781,793,798,806,817,819,825,837,854,855,868,871,873,882,889,902,903,910,927,931,936,938,945,949,962,973,981,988,999,1001,1008,1022,1023,1025,1026,1027,1036,1053,1057,1064,1071,1085,1092,1098,1099,1100,1106,1111,1116,1118,1134,1141,1143,1147,1159,1161,1170,1178,1183,1197,1204,1206,1209,1235,1247,1251,1260,1261,1267,1271,1273,1274,1281,1287,1295,1302,1314,1323,1330,1332,1333,1339,1342,1351,1353,1358,1359,1364,1365,1368,1375,1386,1387,1393,1395,1404,1406,1407,1413,1417,1421,1422,1441,1442,1443,1449,1456,1463,1467,1477,1482,1501,1505,1512,1519,1521,1525,1526,1533,1539,1541,1547,1548,1550,1554,1561,1562,1575,1586,1591,1596,1603,1612,1629,1634,1638,1647,1650,1651,1659,1661,1665,1674,1677,1687,1701,1705,1708,1710,1729,1736,1737,1742,1746,1755,1764,1767,1775,1778,1791,1804,1806,1807,1809,1813,1820,1827,1843,1854,1862,1872,1876,1881,1890,1891,1897,1898,1899,1911,1924,1925,1935,1939,1946,1953,1957,1962,1963,1971,1976,1981,1989,1991,1995,1998,2002,2007,2013,2015,2016,2037,2041,2044,2046,2047,2050,2052,2054,2059,2061,2071,2072,2077,2079,2093,2101,2106,2107,2109,2114,2119,2128,2133,2135,2142,2149,2163,2169,2170,2184,2191,2196,2198,2200,2201,2205,2212,2222,2223,2232,2236,2255,2257,2261,2263,2268,2275,2282,2286,2289,2294,2317,2318,2321,2322,2325,2331,2340,2343,2345,2353,2356,2359,2366,2379,2387,2394,2405,2408,2412,2413,2418,2439,2443,2449,2451,2457,2470,2475,2479,2493,2494,2501,2502,2509,2511,2520,2522,2525,2527,2534,2542,2546,2547,2548,2555,2562,2565,2569,2574,2583,2587,2590,2604,2611,2613,2619,2623,2628,2639,2641,2646,2651,2653,2660,2664,2666,2667,2678,2684,2691,2701,2702,2706,2709,2716,2717,2718,2728,2730,2736,2743,2745,2750,2761,2763,2765,2772,2774,2779,2781,2783,2786,2790,2793,2795,2808,2812,2814,2817,2821,2826,2834,2835,2842,2844,2847,2849,2863,2869,2881,2882,2884,2886,2898,2899,2907,2911,2912,2919,2923,2925,2926,2934,2943,2945,2947,2954,2961,2964,2977,2979,2981,2983,2989,2997,3002,3003,3007,3010,3015,3024,3025,3031,3033,3038,3042,3050,3052,3053,3059,3066,3069,3073,3075,3078,3081,3082,3087,3091,3094,3096,3097,3100,3108,3122,3124,3131,3133,3139,3141,3150,3157,3159,3171,3172,3182,3185,3192,3193,3199,3206,3211,3213,3224,3241,3249,3255,3258,3268,3275,3276,3277,3283,3285,3294,3297,3300,3302,3303,3311,3318,3322,3325,3330,3333,3339,3348,3354,3355,3357,3367,3374,3379,3393,3395,3397,3402,3409,3410,3411,3416,3420,3421,3423,3429,3439,3441,3458,3465,3472,3474,3477,3479,3483,3484,3492,3493,3510,3515,3523,3528,3534,3549,3550,3555,3556,3573,3575,3577,3582,3589,3591,3601,3605,3608,3612,3614,3618,3626,3627,3640,3641,3654,3661,3663,3667,3679,3681,3683,3686,3689,3705,3708,3717,3724,3731,3741,3744,3751,3752,3753,3762,3775,3780,3781,3782,3783,3787,3789,3794,3796,3798,3801,3811,3813,3815,3819,3822,3829,3843,3848,3850,3857,3861,3870,3871,3875,3878,3885,3892,3897,3905,3906,3913,3914,3924,3926,3933,3937,3942,3951,3952,3962,3965,3969,3978,3982,3990,3991,3996,3997,3999,4004,4009,4014,4017,4026,4030,4032,4033,4039,4053,4059,4061,4069,4074,4077,4082,4085,4087,4088,4092,4094,4095,4100,4104,4108,4113,4118,4122,4123,4125,4141,4142,4144,4154,4158,4161,4167,4171,4179,4185,4186,4187,4199,4202,4207,4212,4214,4218,4221,4228,4237,4238,4239,4249,4251,4256,4257,4263,4266,4270,4275,4277,4284,4291,4298,4303,4309,4323,4326,4329,4331,4333,4338,4340,4347,4351,4355,4365,4368,4381,4382,4383,4389,4392,4396,4400,4401,4402,4403,4410,4411,4417,4424,4429,4431,4433,4444,4445,4446,4453,4459,4464,4472,4473,4491,4501,4503,4510,4514,4515,4522,4525,4526,4536,4537,4550,4557,4563,4564,4572,4575,4577,4578,4579,4588,4599,4617,4623,4627,4631,4634,4635,4636,4641,4642,4644,4650,4655,4662,4675,4680,4681,4683,4686,4687,4690,4693,4697,4699,4706,4707,4711,4712,4718,4725,4732,4741,4743,4745,4753,4758,4771,4773,4774,4775,4788,4797,4809,4810,4816,4819,4823,4824,4826,4836,4837,4849,4851,4859,4865,4867,4869,4878,4886,4887,4891,4898,4902,4905,4914,4921,4923,4927,4940,4941,4950,4953,4958,4959,4961,4963,4977,4983,4986,4988,4991,4995,5002,5004,5005,5018,5022,5031,5040,5044,5047,5050,5053,5054,5061,5068,5071,5084,5089,5092,5094,5096,5103,5110,5115,5117,5124,5125,5130,5131,5135,5138,5139,5143,5148,5149,5159,5161,5166,5173,5174,5180,5187,5193,5208,5211,5222,5225,5226,5229,5238,5239,5246,5256,5257,5263,5265,5275,5278,5282,5285,5291,5292,5293,5299,5301,5302,5306,5317,5320,5325,5328,5332,5334,5341,5355,5356,5368,5369,5371,5373,5377,5382,5383,5401,5402,5404,5409,5412,5418,5421,5425,5427,5432,5434,5436,5439,5453,5456,5460,5461,5463,5467,5472,5473,5481,5486,5490,5495,5499,5500,5509,5517,5522,5526,5529,5530,5537,5544,5548,5551,5555,5558,5562,5566,5571,5572,5580,5586,5587,5590,5607,5611,5616,5621,5624,5628,5629,5634,5642,5643,5652,5661,5668,5670,5673,5677,5679,5681,5684,5688,5691,5694,5697,5698,5705,5707,5713,5715,5719,5726,5731,5733,5735,5738,5761,5762,5764,5767,5768,5772,5775,5787,5795,5796,5797,5798,5803,5805,5809,5814,5817,5822,5824,5833,5838,5846,5850,5852,5859,5863,5868,5871,5886,5889,5890,5894,5908,5913,5915,5917,5921,5922,5928,5941,5943,5947,5949,5951,5954,5957,5958,5962,5963,5966,5967,5971,5973,5977,5978,5983,5985,5994,6004,6006,6013,6014,6019,6020,6021,6025,6030,6031,6039,6045,6048,6050,6057,6062,6066,6076,6083,6084,6097,6100,6104,6106,6111,6118,6119,6123,6132,6138,6139,6141,6146,6149,6150,6156,6161,6162,6164,6169,6174,6175,6177,6181,6182,6183,6188,6191,6192,6194,6200,6201,6213,6216,6219,6223,6231,6235,6237,6244,6248,6251,6253,6255,6262,6266,6275,6278,6279,6281,6282,6283,6289,6293,6300,6303,6305,6314,6318,6321,6325,6327,6331,6335,6342,6344,6349,6355,6357,6363,6364,6365,6370,6381,6384,6386,6398,6399,6403,6405,6412,6417,6422,6426,6433,6435,6447,6448,6461,6475,6479,6482,6487,6489,6493,6498,6499,6507,6510,6516,6517,6533,6536,6541,6543,6550,6552,6554,6559,6566,6570,6573,6579,6588,6594,6597,6600,6603,6604,6606,6611,6615,6622,6631,6633,6636,6643,6644,6649,6650,6651,6660,6665,6666,6669,6678,6695,6696,6697,6708,6710,6714,6727,6734,6741,6748,6751,6755,6758,6759,6765,6769,6771,6775,6783,6786,6789,6790,6794,6795,6799,6804,6811,6813,6818,6820,6822,6825,6832,6840,6842,6846,6851,6858,6867,6875,6878,6882,6901,6903,6913,6916,6921,6923,6930,6931,6935,6937,6941,6943,6944,6948,6951,6954,6958,6963,6965,6966,6968,6973,6975,6979,6984,6986,6993,7007,7009,7011,7020,7025,7029,7030,7033,7035,7046,7049,7051,7056,7059,7063,7065,7068,7077,7081,7083,7085,7087,7098,7099,7100,7105,7110,7111,7112,7119,7137,7141,7146,7147,7150,7154,7161,7163,7164,7171,7175,7178,7182,7189,7201,7202,7205,7210,7215,7216,7224,7227,7228,7231,7236,7239,7245,7252,7254,7259,7267,7271,7273,7280,7282,7299,7303,7308,7315,7317,7322,7326,7329,7334,7335,7347,7353,7357,7358,7362,7363,7366,7371,7372,7378,7381,7385,7399,7407,7410,7416,7421,7423,7425,7434,7437,7441,7448,7461,7462,7469,7471,7479,7482,7483,7488,7497,7501,7502,7503,7504,7505,7506,7511,7519,7524,7525,7527,7533,7543,7550,7553,7560,7562,7564,7566,7574,7575,7578,7581,7588,7592,7595,7596,7601,7602,7605,7609,7613,7622,7623,7625,7626,7630,7638,7641,7644,7651,7657,7658,7659,7663,7665,7667,7677,7686,7693,7695,7696,7700,7705,7707,7711,7714,7722,7731,7733,7735,7740,7742,7747,7749,7750,7756,7761,7770,7771,7775,7777,7781,7783,7784,7794,7805,7807,7810,7812,7813,7819,7821,7826,7828,7831,7833,7839,7843,7847,7848,7852,7857,7861,7866,7869,7874,7875,7884,7891,7893,7902,7903,7904,7917,7923,7924,7930,7931,7938,7947,7953,7955,7956,7957,7959,7964,7969,7973,7975,7980,7982,7987,7991,7992,7994,7998,7999,8001,8008,8015,8018,8023,8028,8029,8034,8037,8047,8052,8060,8064,8066,8071,8073,8078,8091,8099,8103,8106,8107,8113,8118,8119,8122,8127,8137,8138,8145,8148,8149,8151,8154,8163,8164,8170,8174,8176,8177,8184,8188,8190,8197,8200,8203,8208,8216,8226,8227,8229,8235,8236,8244,8246,8250,8251,8253,8255,8261,8271,8275,8281,8282,8283,8284,8288,8289,8295,8299,8305,8307,8308,8316,8321,8322,8325,8334,8337,8341,8342,8343,8349,8358,8359,8370,8371,8372,8374,8379,8385,8393,8398,8401,8404,8407,8414,8424,8428,8433,8435,8436,8442,8451,8456,8463,8471,8473,8474,8476,8478,8479,8491,8498,8502,8505,8509,8512,8514,8525,8526,8532,8540,8541,8547,8550,8554,8557,8568,8569,8582,8587,8589,8591,8593,8596,8606,8607,8611,8617,8618,8631,8643,8645,8646,8649,8651,8652,8658,8659,8662,8666,8676,8680,8683,8685,8687,8694,8697,8702,8703,8710,8711,8721,8723,8729,8730,8733,8736,8743,8749,8757,8762,8764,8766,8769,8773,8775,8778,8784,8792,8797,8800,8802,8804,8806,8820,8822,8827,8829,8834,8835,8841,8848,8858,8862,8866,8869,8875,8883,8888,8890,8892,8897,8901,8906,8911,8917,8918,8919,8921,8928,8931,8937,8943,8944,8946,8949,8953,8955,8957,8967,8973,8982,8983,8987,8991,9002,9006,9009,9017,9020,9021,9028,9030,9031,9035,9037,9044,9045,9050,9052,9063,9065,9072,9073,9074,9075,9079,9081,9093,9099,9100,9114,9121,9126,9128,9131,9135,9139,9144,9150,9154,9156,9158,9159,9176,9177,9189,9191,9198,9207,9211,9215,9217,9219,9225,9234,9243,9246,9247,9253,9254,9261,9262,9268,9269,9270,9271,9272,9273,9282,9284,9288,9289,9291,9297,9300,9301,9310,9313,9324,9331,9333,9350,9351,9360,9362,9366,9372,9373,9374,9380,9386,9387,9393,9394,9398,9399,9401,9405,9412,9414,9417,9422,9423,9424,9436,9443,9450,9451,9455,9457,9459,9464,9471,9477,9481,9482,9485,9486,9490,9495,9503,9506,9513,9516,9517,9529,9542,9546,9548,9550,9555,9567,9576,9577,9579,9581,9583,9589,9594,9597,9603,9607,9618,9620,9621,9625,9632,9633,9637,9638,9639,9641,9646,9648,9652,9653,9657,9667,9672,9674,9675,9691,9695,9698,9702,9703,9709,9711,9718,9723,9730,9734,9737,9738,9747,9751,9756,9763,9765,9772,9773,9774,9779,9782,9783,9785,9793,9796,9804,9810,9815,9821,9825,9828,9831,9837,9841,9842,9846,9847,9849,9854,9855,9880,9881,9882,9889,9891,9900,9905,9906,9909,9916,9918,9919,9922,9926,9933,9937,9943,9945,9947,9954,9955,9961,9966,9972,9975,9976,9982,9990,9991,9997,9999}

总计2003个.

——————————————————————————————————————

设$n=2^km,2\nmid m$，则\begin{array}l
λ(n)=\begin{cases}\operatorname{lcm}(2^{k-2},λ(m))&k>2\\\operatorname{lcm}(2^{k-1},λ(m))&k⩽2\end{cases}\\ϕ(n)=2^{k-1}ϕ(m)
\end{array}所以$$
{ϕ(n)\overλ(n)}=\begin{cases}\dfrac{2^{k-1}ϕ(m)}{\operatorname{lcm}(2^{k-2},λ(m))}&k>2\\\dfrac{2^{k-1}ϕ(m)}{\operatorname{lcm}(2^{k-1},λ(m))}&k⩽2\end{cases}$$又可以写成$$
{ϕ(n)\overλ(n)}=\begin{cases}2·\dfrac{ϕ(m)}{λ(m)}·\dfrac{2^{k-2}·λ(m)}{\operatorname{lcm}(2^{k-2},λ(m))}&k>2\\\dfrac{ϕ(m)}{λ(m)}·\dfrac{2^{k-1}λ(m)}{\operatorname{lcm}(2^{k-1},λ(m))}&k⩽2\end{cases}$$由$\gcd(a,b)=\dfrac{ab}{\operatorname{lcm}(a,b)}$得：$$
{ϕ(n)\overλ(n)}=\begin{cases}2·\dfrac{ϕ(m)}{λ(m)}·\gcd(2^{k-2},λ(m))&k>2\\\dfrac{ϕ(m)}{λ(m)}·\gcd(2^{k-1},λ(m))&k⩽2\end{cases}$$

		自动登录	找回密码
密码			快速注册

[数论] 关于欧拉定理的疑问

相关帖子

评分