引言

定义1  设m>1, (a, m)=1，则使a^r≡1(mod m) 成立的最小的正整数r称为a对模m的指数，记为δ_m(a)。

定义2  若δ_m(a)=φ(m)，则称a是模m的原根。

定义3  对任意正整数n，伪Smarandache函数Z(n) 定义为满足$n\left| \frac{m (m+1)}{2} \right.$的最小的正整数m。即就是：$Z\left (n \right)=\text{min}\left\{ m:n\left| \frac{m\left (m+1 \right)}{2}, m\in {{\boldsymbol{N}}^{+}} \right. \right\}。$。其中，N⁺表示所有正整数集合。

例如，Z(n) 的前几个值分别为Z(1)=1, Z(2)=3, Z(3)=2, Z(4)=7, Z(5)=4, Z(6)=3, 该函数是由David Gorski在文献[1]中提出的，同时他本人还研究了Z(n) 的初等性质，获得了一系列有趣的结果。其中的一些重要性质如：(1) 如果p>2是一个素数，那么Z(p)=(p)-1；(2) 如果n=2^k，那么Z(n)=2^k+1-1；(3) 设p>2为素数，那么Z(2p)=p。其他有关伪Smarandache函数的工作可参阅文献[2-4]。另外, Kenichiro Kashihara还建议我们求方程$\sum\limits_{k=1}^{n}{Z (k)=\frac{n (n+1)}{2}}$的所有正整数解, 寻找伪Smarandache函数Z(n) 为n的原根的所有正整数n，本文利用初等方法及解析方法对这两类问题进行了研究，得到了2个有趣的结论。

1 引理及证明

引理1^[5]  设n>1为正整数，a为任意整数且 (a, n)=1，则a^φ(n)≡1(mod n)，其中：φ(n) 为Euler函数，即φ(n) 表示不超过n且与n互素的正整数的个数。

引理2^[6]  对于任意正整数n，有$\sum\limits_{k\le n}{Z (2k)}\le \frac{15{{n}^{2}}}{16}+\frac{9n}{2}+\frac{45}{4}$。

证明  以下分两种情况进行讨论:

(1) 当n=2m(m为自然数) 为偶数时，有

$ \sum\limits_{k\le n}{Z\left( 2k \right)}=\sum\limits_{k\le m}{Z\left( 2\left( 2k-1 \right) \right)}+\sum\limits_{k\le m}{Z\left( 4k \right)}。 $

(1)

注意到Z(2(2k-1))≤2k-1, 如果2|k，则有Z(2(2k-1))≤2k-2;如果，则有

$ \sum\limits_{k\le m}{Z\left( 2\left( 2k-1 \right) \right)}\le Z\left( 2 \right)+\sum\limits_{1 < k < m}{(2k-1)=\frac{{{n}^{2}}}{4}}+2。 $

(2)

设$u=\left[\frac{m+1}{2} \right]$表示不超过$\frac{m+1}{2}$的最大整数, 则有

$ \sum\limits_{k\le m}{Z\left( 4k \right)}\le \sum\limits_{k\le u}{Z\left( 4\left( 2k-1 \right) \right)}+\sum\limits_{k\le u}{Z\left( 8k \right)}。 $

(3)

当2k-1>4时, 注意到：Z(4(2k-1))≤2k-2。如果k≡1(mod 4), 则Z(4(2k-1))≤2k-1;如果k≡0(mod 4)，则Z(4(2k-1))≤3(2k-1)-1;如果k≡2(mod 4)，则Z(4(2k-1))≤3(2k-1);如果k≡3(mod 4)，则有

$ \begin{align} & \sum\limits_{k\le u}{Z\left( 4\left( 2k-1 \right) \right)}\le Z\left( 4 \right)+Z\left( 12 \right)+\sum\limits_{3\le k\le u}{3\left( 2k-1 \right)}\text{ } \\ & =4-1+\sum\limits_{k\le u}{3\left( 2k-1 \right)}=3({{u}^{2}}+1)\le 3+\frac{3{{\left( m+1 \right)}^{2}}}{4}。 \\ \end{align} $

(4)

注意到Z(2n)≤4n-1, 因此

$ \sum\limits_{k\le u}{Z\left( 8k \right)}\le \sum\limits_{k\le u}{\left( 16-1 \right)}\le 8u\left( u+1 \right)-u\le 2{{\left( m+1 \right)}^{2}}+\frac{7\left( m+1 \right)}{2}。 $

(5)

由 (3)(4)(5) 式可得

$ \begin{array}{l} \sum\limits_{k \le m} {Z\left( {4k} \right)} \le \sum\limits_{k \le u} {Z\left( {4\left( {2k-1} \right)} \right)} + \sum\limits_{k \le u} {Z\left( {8k} \right)} {\rm{ }}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \frac{{11{n^2}}}{{16}} + \frac{{9n}}{2} + \frac{{37}}{4}。 \end{array} $

(6)

由 (1)(2)(6) 式可得

$ \sum\limits_{k \le n} {Z\left( {2k} \right)} = \sum\limits_{k \le m} {Z\left( {2\left( {2k-1} \right)} \right)} + \sum\limits_{k \le m} {Z\left( {4k} \right)} \le \frac{{15{n^2}}}{{16}} + \frac{{9n}}{2} + \frac{{45}}{4}。 $

于是，证明了当n为偶数时结论成立。

(2) 当n为奇数时，设n=2m+1(m为自然数), 利用Z(2(2m+1))≤2m+1及上面已经证明的结果有

$ \sum\limits_{k \le n} {Z\left( {2k} \right)} = \sum\limits_{k \le 2n + 1} {Z\left( {2k} \right)} = Z\left( {2\left( {2m + 1} \right)} \right) + \sum\limits_{k \le 2m} {Z\left( {2k} \right)} < \frac{{15{n^2}}}{{16}} + \frac{{9n}}{2} + \frac{{45}}{4}. $

于是，完成了引理的证明。

引理3^[7]  若p为奇素数, 则模p有原根。

证明  在模p的简化剩余系1, 2, …, p-1里，每一整数对模p都有它自己的指数。从这p-1个指数中取出所有不同的指数，记作δ₁, δ₂, …, δ_r，令τ=[δ₁, δ₂, …, δ_r]。

(1) 设τ=q₁^α₁q₂^α₂…q_k^α_k为τ的标准分解式，则对每一s来说，在δ₁, δ₂, …, δ_r里一定有一δ使得δ=aq_s^α_s，由δ₁, δ₂, …, δ_r的意义知有一整数，它对模p的指数是δ。设这个整数为x，由指数的性质可得x_s=x^α对模p的指数为q_s^α_s，故在1, 2, …, p-1里有k个数x′₁, x′₂, …, x′_k使x′_s(s=1, 2, …, k) 对模p的指数是q_s^α_s。令g=x′₁x′₂…x′_k，由引理1可知g=x′₁x′₂…x′_k对模p的指数是τ。

(2) 因为δ_s(s=1, 2, …, r) 是τ的因数, 而1, 2, …, p-1中任一数的指数在δ₁, δ₂, …, δ_r中出现, 故x^r≡1(mod p), x=1, 2, …, p-1, 即x^r≡1(mod p) 至少有p-1个解, 从而p-1≤r, 但由指数的性质可知δ_s|p-1 (s=1, 2, …, r), 故τ|p-1, 由此可得τ≤p-1, 故τ=p-1。

引理4  若p为奇素数, 则模p^α有原根, 其中α≥1为整数。

证明  不妨设α>1。由于g是模p的原根, 则 (g, p)=1, 因此存在整数x₀, 使得g^p-1=1+px₀, 于是, 对于任意的整数t有

$ {\left( {g + pt} \right)^{p-1}} = {g^{p-1}} + p\left( {p-1} \right)t{g^{p - 2}} + \cdots = 1 + p({x_0} - {g^{p - 2}}t) + {p^2}{Q_2}。 $

其中：Q₂∈Z。

从而 (g+pt)^p-1≡1+p(x₀-g^p-2t)(mod p²), 当p不能整除x₀时, 取t₀=0；当p能整除x₀时, 取t₀=1, 故p不能整除x₀-g^p-2t₀=y₀, 于是

$ \begin{array}{l} {(g + p{t_0})^{p-1}} = 1 + p{y_0} \equiv 1({\rm{mod }}{p^2}), \\ {(g + p{t_0})^{p(p-1)}} = {(1 + p{y_0})^p} = 1 + {p^2}{y_1}。 \end{array} $

其中：y₁=y₀+C_P²y₀²+…+p^p-2y₀^p≡y₀(mod p)。

因此，当p不能整除y₁时, 同理可得

$ \begin{array}{l} {(g + p{t_0})^{{p^2}(p-1)}} = {(1 + {p^2}{y_1})^p} = 1 + {p^3}{y_2}, \\ {(g + p{t_0})^{{p^3}(p-1)}} = {(1 + {p^3}{y_1})^p} = 1 + {p^4}{y_3}, \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \cdots \cdots \\ {(g + p{t_0})^{{p^{}}\alpha-1}}\left( {p - 1} \right) = {(1 + {p^{\alpha - 1}}{y_1})^p} = 1 + {p^\alpha }{y_{\alpha - 1}}。 \end{array} $

其中：y_α-1≡y_α-2≡…≡y₀(mod p), 因此，p不能整除y_i(0≤i≤α-1)。

设g+pt₀对模p^α的指数为δ, 则 (g+pt₀)^δ≡1(mod p^α), 由此即得 (g+pt₀)^δ≡1(mod p), 但g+pt₀是模p的一个原根, 故p-1能整除δ。另一方面, 由δ的定义知δ|φ(p^α), 即δ|p^α-1(p-1), 故δ=p^r-1(p-1), 1≤r≤α, 由此结果可得1+p^ry_r-1≡1(mod p^α), 即p^ry_r-1≡1(mod p^α), 从而有r≥α, 故r=α, g+pt₀是模p^α的一个原根。

引理5  关于模m(>1) 有原根的充要条件是m是形如2, 4, p^k, 2p^k的数，其中:p为奇素数，k为正整数。

证明  (1) 必要性：

若m不具备定理中的形式，则

$ m = {2^k}\left( {k \ge 3} \right), $

(7)

$ m = {2^k}p_1^{{k_1}}p_2^{{k_2}} \ldots p_l^{{k_l}}, \left( {k \ge 2, l \ge 1} \right), $

(8)

$ m = {2^k}p_1^{{k_1}}p_2^{{k_2}} \ldots p_l^{{k_l}}, \left( {k \ge 0, l \ge 2} \right), $

(9)

其中：p_i(1≤i≤l) 为奇素数，k_i(1≤i≤l) 为正整数。

若m是形如 (8) 式的数，那么对任意a，(a, m)=1，有

$ \begin{array}{l} {a^{\varphi ({2^k})}} \equiv 1({\rm{mod }}{2^k}), \\ {\rm{ }}{a^{\varphi (p_i^ki)}} \equiv 1({\rm{mod}}{p_i}^{{k_i}}), 1 \le i \le l, \\ {a^{\lambda (m)}} \equiv 1({\rm{mod }}{2^k}), \\ {\rm{ }}{a^{\lambda (m)}} \equiv 1({\rm{mod}}{p_i}^{{k_i}}), 1 \le i \le l, \\ {a^{\lambda (m)}} \equiv 1\left( {{\rm{mod }}m} \right)。 \end{array} $

(10)

设正整数的标准分解式为m=2^kp₁^k₁p₂^k₂…p_l^k_l，记λ(m)=φ(2^k), φ(p₁^k₁), …, φ(p_l^k_l)，易证λ(m) < φ(m)，由 (10) 式可知任何与m互素的数a都不是模m的原根。同理，若m为形如 (7) 或 (9) 式中的数，模m也没有原根。

(2) 充分性：

1) 若m=2ⁿ。当n=1时，m=2，此时φ(m)=1，显然1是它的原根。当n=2时，m=4，此时φ(m)=2，易知1，3是模4的简化剩余系，显然3是它的原根。当n≥3时，对任意奇数a，由于a=2a₁+1，从而a²=4a₁(a₁+1)+1≡1(mod 2³)，则

$ {a^{{2^2}}} = {(1 + 8{t_1})^2} = 1 + 16({t_1} + 4t_1^2) \equiv 1({\rm{mod }}{2^4})。 $

若a^2(n-1)-2≡1(mod 2^n-1)，则a^2n-2=(1+2^n-1t_n-3)²=1+2ⁿ(t_n-3+2^n-2t_n-3²)≡1(mod 2ⁿ)，从而a^2n-2≡1(mod 2ⁿ), (a, 2ⁿ)=1永远成立，故模m=2ⁿ没有原根。

2) 若m=p^k。当k=1时，m=p，此时φ(m)=p-1，设p-1=q₁^k₁…q^k_rr，如果我们能够找到关于模p的阶数是q_i^k_i的数b_i(i=1, 2, …, r)，由引理2，q=b₁b₂…b_r的阶数就是p-1，即q是模p的原根。为此，考虑${x^{\frac{{p-1}}{{{q_i}}}}} < p-1$，因为p为素数，所以，它的不同解的个数不大于$\frac{{p-1}}{{{q_i}}} < p-1$，因此在p的简化剩余系中一定有不适合${x^{\frac{{p-1}}{{{q_i}}}}} \equiv 1({\rm{mod }}p)$的a_i存在，令${b_i} = a_i^{q\frac{{p-1}}{{i{k_i}}}}$，下证b_i关于模p的阶数λ_i=q_i^k_i，因为${b_i}^{{q_i}{k_i}} = {(a_i^{q\frac{{p-1}}{{i{k_i}}}})^{q_i^{{l_i}}}} = (a_i^{q\frac{{p-1}}{{i{k_i}-{l_i}}}}) \equiv 1\left ({{\rm{mod }}p} \right)$，所以λ_i|q_i^k_i, 即λ_i=q_i^l_i, l_i < k_i，又b_i^λ_i≡1(mod p)，从而${(a_i^{q\frac{{p-1}}{{i{k_i}}}})^{{\lambda _i}}} = {(a_i^{q\frac{{p-1}}{{i{k_i}}}})^{q_i^li}} = {\rm{ }}(a_i^{q\frac{{p-1}}{{i{k_i}-{l_i}}}}) \equiv 1\left ({{\rm{mod }}p} \right)$，于是$a_i^{\frac{{p-1}}{{{q_i}}}} \equiv 1\left ({{\rm{mod }}p} \right)$，与假设矛盾，因此，b_i关于模p的阶数λ_i=q_i^k_i，即q是模p的原根。当k≥2时，假设g是模p的原根，即g^p-1≡1(mod p)，于是g^p-1≢1(mod p²)，或者g^p-1≡1(mod p²)。

下证，若g^p-1≢1(mod p²)，g是p^k的原根，若g^p-1≡1(mod p²)，g+p是p^k的原根。事实上，当g^p-1≢1(mod p²) 时，假定关于模p^k，g的阶数是λ，那么λ|φ(p^k)，即λ|p^k-1(p-1)，令λ_s=p^k-1(p-1)，因为p^k≡1(mod p^k)，所以g^λ≡1(mod p)，于是 (p-1)|λ，即λ=(p-1)t，因此p^k-1=ts，也就是说，t=p^e, e≤k-1，所以λ=p^e(p-1)，假如e < k-1，那么e+2 < k，于是g^λ≡1(mod p^e+2)，但是g^λ=g^pe(p-1)=(g^p-1)^ep=(1+hp)^pe≡1+hp^e+1(mod p^e+2)，所以hp^e+1≡0(mod p^e+2)，因此h≡0(mod p)，它与$ph{≢ }0(\text{mod}\ {{p}^{2}})$的假设不符，于是e=k-1，λ=p^k-1(p-1)，也就是说，当${{g}^{p-1}}{≢ }1(\text{mod}\ p)$时，q是模p^k的原根。

当g^p-1≡1(mod p²)，因为g+p是模p^k的原根，这时 (g+p)^p-1-1≡g^p-1-1+p(p-1)g^p-2≡p(p-1)g^p-2(mod p²)，又因为 (g, p)=1，所以 (g+p)^p-1≢1(mod p²)，利用前面的证明过程可得，若g^p-1≡1(mod p²)，则g+p是p^k的原根。

3) 若m=2p^k，此时φ(m)=φ(2)φ(p^k)，g是模p^k的原根，那么，当g为奇数时，g是模m的原根，这是因为 (g, m)=1，g^φ(m)≡1(mod m)，假设g关于模m的阶数λ < φ(m)，则从g^λ≡1(mod m)，即有g^λ≡1(mod p^k)，而这与g是模p^k的原根的假设矛盾，因此λ=φ(m)，于是g是模m的原根。当g为偶数时，因为g+p^k是p^k的原根，而g+p^k为奇数，所以g+p^k也是模m的原根。

于是完成了引理的证明。

2 结论及证明

定理1  方程$\sum\limits_{k=1}^{n}{Z\left (k \right)}=\frac{n\left (n+1 \right)}{2}$的解为且只能为n=1, 3。

证明  当n≥64时，有$\sum\limits_{k=1}^{n}{Z (k)} < \frac{n (n+1)}{2}$。

事实上, 当n≥64时，设$u=\left[\frac{n+1}{2} \right]$，注意到Z(2k+1)≤2k，由引理2有

$ \begin{array}{l} \sum\limits_{k \le n} {Z\left( k \right)} = \sum\limits_{k \le n} {Z\left( {2k-1} \right)} + \sum\limits_{k \le \frac{n}{2}} {Z\left( {2k} \right)} \le 1 + \sum\limits_{2 \le k \le n} {\left( {2k-2} \right)} + \frac{{15{n^2}}}{{64}} + \frac{{9n}}{4} + \frac{{45}}{4}{\rm{ }}\\ \;\;\;\;\;\;\;\;\;\;\;\;\; \le \frac{{31{n^2}}}{{64}} + \frac{{5n}}{4} + \frac{{49}}{4} < \frac{{n(n + 1)}}{2}. \end{array} $

所以，当n≥64时，有不等式$\sum\limits_{k = 1}^n {Z (k) < } \frac{{n (n + 1)}}{2}$，因此，当n≥64时，方程$\sum\limits_{k = 1}^n {Z (k) = } \frac{{n (n + 1)}}{2}$没有正整数解。当n < 64时，由引理3及参考文献[8]可得，n=1及n=3是方程$\sum\limits_{k = 1}^n {Z (k) = } \frac{{n (n + 1)}}{2}$的解。

定理2  设n是存在原根的正整数，则伪Smarandache函数Z(n) 为n的原根当且仅当n=2, 3, 4。

证明  显然，Z(2)=3是2的一个原根，Z(4)=7是4的一个原根，现在考虑n=p^α，其中：p为奇素数。若Z(n) 是模n=p^α的原根。则由Z(n) 的定义及性质知Z(n)=p^α-1，所以p^α-1为模n=p^α的原根。又由于Z²(n)=(p^a-1)²≡1(mod p^a) 且p^α-1为模n=p^α的原根，所以2=φ(p^α)=p^a-1(p-1), 由此式立刻推出α=1，p-1=2。即就是p=2+1=3。因此，当n=p^α(p为奇素数) 时，Z(n) 为n的原根当且仅当n=p=3。

当n=2p^α时，注意到前面列出Z(n) 的性质，我们分两种情况讨论：

(1) 若p^α≡3(mod 4)，则由Z(n) 的定义及性质可得Z(n)=p^α，因为 (p^α, 2p^α)=p^α>1，所以Z(n)=p^α不可能为n=2p^α的原根。

(2) 若p^α≡1(mod 4)，则由Z(n) 的定义及性质可得Z(n)=p^α-1。因为 (p^α-1, 2p^α)=2>1，所以Z(n)=p^α-1也不可能为n=2p^α的原根。

综合以上结果及引理4、引理5可得，Z(n) 为n的原根当且仅当n=2, 3, 4。