欧拉定理

欧拉定理：对 \(\forall a,b\) 满足 \((a,b)=1\)， 有 \(a^{\varphi(b)}\equiv 1\: (mod ~b)\)

证明：由简化剩余系的基本性质易得

\(a_0a_1...a_{\varphi(m)-1}\equiv(aa_0)(aa_1)...(aa_{\varphi(m)-1})\ (mod ~m)\)

推广：对 \(\forall a,b,n\) 有 \(a^n\equiv a^{n\: mod \:\varphi(b)+\varphi(b)}\: (mod~m)\)

和 \(a^n\equiv a^{n-\varphi(n)}\:(mod~n)\)

我们留作练习，只要把 \(n\) 分成与 \(a\) 互质的部分和不互质的部分即可，对相同的素因子分析 \(v_p\) 函数。

例1

\(a\in N^*,a>1\) ，求证：集合 \(\{a^n+a^{n-1}-1\mid n=2,3,...\}\) 有无穷子集 \(X\) 使得 \(X\) 中任两数互素。

假定 \(X\) 中已选定 \(x_1,x_2,...,x_n\) ，取 \(N=\varphi(x_1x_2x_3...x_n)\) ，则有

\(a^{N+1}+a^N-1\equiv a\:(mod~x_1x_2...x_n)\)

又 \(a\nmid x_i\) ，知取 \(x_{n+1}=a^{N+1}+a^N-1\) 即可

注记：利用欧拉函数的积性进行次幂类构造是常用的手法

例2

对任意 \(r,m,c,a\in Z^*\) ，存在无穷多 \(t\) ，使得 \(ca^t-t\equiv r\:(mod~m)\)

我们对 \(m\) 归纳证明命题。 \(m=2\) 是显然的。

数列 \(\{ca^t\}\) 最终是周期的，我们设这个周期是 \(T\) 。根据欧拉定理的推广 \(1\) 可以看出最终 \(T\le \varphi(m)<m\)

记 \(f(x)=ca^x-x\) ，于是对充分大 \(x\) 有 \(f(x+kT)\equiv f(x)-kT\:(mod~m)\)

设 \(d=gcd(T,m)\) ，并记 \(m=dm_0\) ，然后使用归纳假设，找到 \(t_1,t_2,...,t_d\) 使得 \(f(t_i)\equiv i\:(mod~d)\)

我们设 \(t_{ij}=t_i+jT,1\le j\le m_0\) ，因为 \(d\mid T\) ，可以看到 \(f(t_{ij})\equiv i\:(mod~d)\)

我们说 \(f(t_{ij})\ne f(t_{ik})\:(mod~m)\) 。如果不是这样，我们会得到 \(f(t_{ij})=f(t_{ik})-(j-k)T\equiv f(t_{ik})\:(mod~m)\) ，从而 \(m\mid (j-k)T\) ，这是不可能的

于是 \(f(t_{i1}),f(t_{i2}),...,f(t_{im_0})\) 模 \(m\) 余 \(i,i+m_0,...,i+(d-1)m_0\) ，当 \(i=1,2,...,d\) 时遍历模 \(m\) 的完系。

至此我们已经找到了 \(f(x)\equiv r\:(mod~m)\) 的至少一个解，而 \(x+kmT\) 给出了无穷组解。

注：巴西 \(2015\) 是有关 \(c=1\) 的情况，采用了 \(\varphi(n)\rightarrow n\) 的归纳方法，有一定的启发性，但是本做法更加自然一些。

例3

1. 证明：对所有正整数 \(n\) 与整数 \(a\) ，有 \(\sum\limits_{d\mid n} \varphi(d)a^{\frac nd}\equiv 0\:(mod~n)\)

2. 证明： \(n\mid \sum_{i=1}^na^{\gcd(i,n)}\)

设 \(f(n)=\sum\limits_{d\mid n} \varphi(d)a^{\frac nd}\)

首先我们看到，如果 \(n=uv,(u,v)=1\) ，我们只要证命题对 \(u,v\) 分别成立，因为

\(\large f(n) = \sum\limits_{d\mid u}\sum\limits_{e\mid v}\varphi(d)\varphi(e)a^{\frac{uv}{de}} =(\sum\limits_{d\mid u}\varphi(d)a^{\frac ud})(\sum\limits_{e\mid v}\varphi(e)a^{\frac ve})\)

我们只要证明 \(p^\alpha\) 的情况。这个可以计算

\(\large f(p^\alpha)=a^{p^n}+(p-1)a^{p^{n-1}}+p(p-1)a^{p^{n-2}}+...=a^{p^n}-a^{p^{n-1}}+pf(p^{\alpha-1})\)

根据欧拉定理，只要 \(p^{\alpha-1}\mid f(p^{\alpha-1})\) ，可以归纳证明，奠基是显然的。

回忆 \(\sum\limits_{d\mid n}\varphi(d)=n\) 的证明，实际上我们证明了：满足 \(\gcd(i,n)=d\) 的整数 \(\in\{1,2,...,n\}\) 恰好有 \(\varphi(\frac nd)\) 个，于是

\(\large\sum\limits_{i=1}^na^{\gcd(i,n)}=\sum\limits_{d\mid n}\varphi(\frac nd)a^d\)

完成证明。

例4

正整数 \(x,y\) 满足对 \(\forall n\in Z_+\) 有 $2^ny+1\mid x^{2n}-1 $ ，求证： \(x=1\)

考虑 \(p\mid 2^ny+1\) ，则 \(x^{2^n}-1\equiv 0\:(mod~p)\)

根据费马数的一些基本性质也可以考虑到如果取 \(p>x+1\) 且 \(p\equiv 3\:(mod~4)\) 就可以矛盾了 （\(x^2+1\) 所有素因子模 \(4\) 余 \(1\)）

我们证明 \(S=\{2^ny+1\mid n\in Z_+\}\) 的素因子集中存在无穷个模 \(4\) 余 \(3\) 的素数

这里只需证明 \(y\) 是奇数的情况即可，特别地，由于 \(2y+1\) 是模 \(4\) 余 \(3\) 的，我们将其模 \(4\) 余 \(3\) 的素因子记为 \(p_1^{\alpha_1},...,p_k^{\alpha_k}\)

将其余数的模 \(4\) 余 \(3\) 素因子记为 \(y_1,...,y_t\) ，\(t\) 可能为 \(0\)

指数幂相关构造，考虑欧拉定理，取 \(N=\varphi(y_1...y_tp_1^{\alpha_1+1}...p_k^{\alpha_k+1})+1\)

那么可知 \(2^Ny+1\equiv 2y+1\:(mod~y_1...y_tp_1^{\alpha_1+1}...p_k^{\alpha_k+1})\)

那么就可以知道 \(y_i\mid 2^Ny+1,p_i^{\alpha_i}\mid\mid 2^Ny+1\)

这说明 \(2^Ny+1\) 的模 \(4\) 余 \(3\) 素因子与 \(2y+1\) 完全相同。然而后者模 \(4\) 余 \(3\) ，矛盾

注：多少用到了素因子幂次控制的思想，具体可见相关笔记，那里有更多欧拉定理的习题。

例5

整数 \(a_0,a_1,...,a_n\) 满足 \(a_0x_0^k+a_1x_1^k+...+a_nx_n^k=0\) 对所有 \(1\le k\le r\) 成立，求证： \(m\mid a_0x_0^m+a_1x_1^m+...+a_nx_n^m\) 对所有 \(r+1\le m\le 2r+1\) 成立

对素数幂 \(m=p^t\)，问题非常显然，用欧拉定理将幂次降至 \(m-\varphi (m)\ge t\) （如果 \(p\mid x_i\) ，则 \(p^t\mid x_i^{m-\varphi(m)}\) ，否则欧拉定理给出）

而 \(t+\varphi(u)\ge \frac 12m\) （特别地 \(m=2r+1\) 不是 \(2\) 的幂），所以 \(m-\varphi(m)\le r\) ，所以

\(a_0x_0^m+...+a_nx_n^m\equiv a_0x_0^{m-\varphi(m)}+...+a_nx_n^{m-\varphi(m)}=0\:(mod~m)\)

对其余合数考虑 \(m=uv\) ，其中 \((u,v)=1\) ，对 \(u,v\) 分别证明。

如果可以使 \(\varphi(u)\le \frac 12r\) ，就用推广 \(1\) ，如果 \(u\) 为素数幂，就要不断减去 \(\varphi(u)\) 直至次数落到 \([t,t+\varphi(u))\) 区间内，因为 \(u\le r\) ，然后 \(t\le \frac 1pu\) 给出 \(t+\varphi(u)\le r\) 。

特别地， \(u=2,3\) 是容易的（当 \(r=1\) 需要单独论证）。不妨 \(u<v\) ，如果 \(u=2,3\) 并且 \(v\) 是素数幂，那么用第二种方法，否则 \(u< v\le \frac 12 r\) 用第一种方法。

例6

设 \(x_1,x_2,...,x_n\) 是整数，满足 \(\gcd(x_1,x_2,...,x_n)=1\) ，设 \(s_i=x_1^i+x_2^i+...+x_n^i\) ，证明： \(\gcd(s_1,s_2,...,s_n)\mid \text{lcm}(1,2,...,n)\)

对于这类等幂和问题，由于 \(2022\) 高联 \(T3\) 考了，大家都应该非常熟悉了。不过数论里一般不用构造多个取等的多项式，构造 \(x^n\) 即可。类似的题目在拉格朗日定理笔记中出现了。

我们要证：对任意 \(p^k>n\) ，不存在 \(x_1,x_2,...,x_n\) 使得 \(x_1^i+x_2^i+...+x_n^i\equiv0\:(mod~p^k)\) 对所有 \(1\le i\le n\) 成立

如果对 \(m\) 有 \(x_1^i+x_2^i+...+x_n^i\equiv0\:(mod~p^k)\) 对所有 \(1\le i\le n\) 成立，那么

\((x_1-c)^i+(x_2-c)^i+...+(x_n-c)^i\equiv nc^i\:(mod~m),\forall 1\le i\le n,1\le c\le m\)

简单的情况是 \(m=p>n\) ，如果成立，根据牛顿恒等式就知道 \((x-x_1)(x-x_2)...(x-x_n)\equiv x^n\:(mod~p)\) ，但是很显然 \(x^n\equiv 0\:(mod~p)\) 的唯一根是 \(x=0\) ，于是 \(p\mid x_i\) ，这就与条件中的 \(x_i\) 互质矛盾了

考虑对 \(m=p^k,k\ge 2\) 成立，那么前置条件是对 \(p^{k-1}\) 成立，设 \(n=s\cdot p^{k-1}+t,s<p\)

考虑

\((x_1-c)^{\varphi(p^{k-1})}+(x_2-c)^{\varphi(p^{k-1})}+...+(x_n-c)^{\varphi(p^{k-1})}\equiv nc^{\varphi(p^{k-1})}\:(mod~p^{k-1})\)

请注意，只要 \(p\mid x\) ，就有 \(p^{k-1}\mid x^{\varphi(p^{k-1})}\) ，因为 \(\varphi(p^{k-1})\ge k-1\)

代入 \(p\nmid c\) ， \(nc^{\varphi(p^{k-1})}\equiv t\) ，因此在 \(x_1,x_2,...,x_n\) 中模 \(p\) 余 \(c\) 的数出现次数是 \(p^{k-1}\) 的整数倍

我们令 \(p\mid c\) ，得到 \(x_i-c\) 中 \(t+C\cdot p^{k-1}\) 个在模 \(p\) 下是 \(0\)

现在把每 \(p^{k-1}\) 个相同的数组成一组，我们得到 \(c_1,c_2,...,c_s\) ，满足 \(\sum c_i^k\equiv 0\:(mod~p)\) 对 \(k=1,2,...,n\) 成立，而且 \(n\ge p\)

然后 \((x-c_1)(x-c_2)...(x-c_s)\equiv x^s\:(mod~p)\) ，唯一的根是 \(0\) 给出 \(p\mid c_i\)，与 \(c_i\) 两两互质矛盾。

例7

证明：存在 \(n\) 个连续的数，每个都不被自己的数码和整除。

我们考虑 \(S(n)+k\nmid 10^{a_1}+10^{a_2}+...+10^{a_k}+n\)

一个直接的想法是让 \(S(n)+k\) 充分大，而 \(a_1,...,a_k\) 都是 \(\varphi(S(n)+k)\) 的倍数，在模 \(S(n)+k\) 的意义下右侧是 \(k+n\) ，而 \(\frac 12(n+k)<S(n)+k<n+k\)

这样的话为了防止出问题最后再给右边加个 \(1\) 就 ok 了。读者应该很乐于完成这个证明的细节。