初等数论 课堂笔记 第三章 -- 欧拉函数一节的若干练习

1. 计算$\phi \left(60\right)$。
   解
   将$60$写成标准分解式
   $$60=2^2\times 3\times 5$$

   1. 法一（计算过程中出现分式）
      $$\phi \left(60\right)=60\times \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)=60\times \frac{1}{2}\times \frac{2}{3}\times \frac{4}{5}=16$$
   2. 法二（计算过程中不出现分式）
      $$\phi \left(60\right)=\phi \left(2^2\right)\phi \left(3\right)\phi \left(5\right)=\left(2^2-2\right)\left(3-1\right)\left(5-1\right)=2\times 2\times 4=16$$
      
      

2. 设$n\in {\mathbb{Z}}_{>0}$，$\phi \left(n\right)=8$，求$n$。
   解
   设$n$的标准分解式为
   $$n={p_1}^{e_1}\cdots {p_k}^{e_k}$$
   则有
   $$\begin{array}{rl}& \phi \left(n\right)=\left[{p_1}^{e_1-1}\left(p_1-1\right)\right]\cdots \left[{p_k}^{e_k-1}\left(p_k-1\right)\right]=8\\ & \Rightarrow \left(p_i-1\right)|8\Rightarrow p_i-1\le 8,p_i\le 9\\ & \Rightarrow p_i\in \left\{2,3,5,7\right\}\\ & \Rightarrow p_i-1\in \left\{1,2,4,6\right\}\end{array}$$
   由于$6\cancel{|}8$，因此有$p_i-1\ne 6\Rightarrow p_i\ne 7$。因此设$n=2^a{3}^b{5}^c$，$a,b,c\ge 0$。
   若$b\ge 2,3|3^{b-1}|\phi \left(3^b\right)|8$，矛盾，于是有$b\in \left\{0,1\right\}$
   若$c\ge 2$，$5|5^{c-1}|\phi \left(5^c\right)|8$，矛盾，于是有$c\in \left\{0,1\right\}$
   进行分类讨论如下。

   1. 若$b=c=0$
      1. 当$a=0$时，$n=1$
         $$\phi \left(n\right)=\phi \left(1\right)=1\ne 8$$
      2. 当$a\ne 0$时，$n=2^a$
         $$\phi \left(n\right)=2^{a-1}\left(2-1\right)=2^{a-1}=8\Rightarrow a-1=3\Rightarrow a=4\Rightarrow n=2^4=16$$
   2. 若$b=0,c=1$
      1. 当$a=0$时，有$n=5$
         $$\phi \left(n\right)=\phi \left(5\right)=4$$
      2. 当$a\ne 0$时，则有$n=2^a\times 5$
         $$\phi \left(n\right)=2^{a-1}\left(2-1\right)\left(5-1\right)=2^{a+1}=8\Rightarrow a+1=3\Rightarrow a=2\Rightarrow n=2^2\cdot 5=20$$
   3. 若$b=1,c=0$
      1. 当$a=0$时，有$n=3$
         $$\phi \left(n\right)=\phi \left(3\right)=2$$
      2. 当$a\ne 0$时，则有$n=2^a\times 3$
         $$\phi \left(n\right)=2^{a-1}\left(2-1\right)\left(3-1\right)=2^a=8\Rightarrow a=3\Rightarrow n=2^3\times 3=24$$
   4. 若$b=1,c=1$
      1. 当$a=0$时，$n=5\times 3=15$
         $$\phi \left(15\right)=\phi \left(5\right)\phi \left(3\right)=\left(5-1\right)\left(3-1\right)=8$$
      2. 当$a>0$时，有$n=2^a\times 5\times 3$
         $$\begin{array}{rl}& \phi \left(n\right)=2^{a-1}\left(2-1\right)\left(5-1\right)\left(3-1\right)=2^{a-1}\times 8=8\\ & \Rightarrow a=1,n=2\times 5\times 3=30\end{array}$$

综上，$n$的可能取值集为$\left\{15,16,20,24,30\right\}$。

3. 求$3^{1492}$的最后两位，即$3^{1492}\mathrm{m}\mathrm{o}\mathrm{d}100$。
   解
   $\gcd \left(3,100\right)=1$，由欧拉定理有
   $$3^{\phi \left(100\right)}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}100\right)$$
   由引理4的推广有
   $$\phi \left(100\right)=\phi \left(2^2\times 5^2\right)=\phi \left(2^2\right)\times \phi \left(5^2\right)=2^{2-1}\left(2-1\right)5^{2-1}\left(5-1\right)=40$$
   因此有
   $$3^{40}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}100\right)$$
   $$\begin{array}{rl}& 1492=40\times 37+12\Rightarrow 3^{1492}={\left(3^{40}\right)}^{37}\cdot 3^{12}\equiv 1^{37}\cdot 3^{12}\equiv 3^{12}\left(\mathrm{m}\mathrm{o}\mathrm{d}100\right)\\ & 3^{12}=9^6={81}^3\equiv {\left(-19\right)}^3=-361\times 19\equiv 39\times 19=741\equiv 41\left(\mathrm{m}\mathrm{o}\mathrm{d}100\right)\end{array}$$
   因此有
   $$3^{1492}\equiv 41\left(\mathrm{m}\mathrm{o}\mathrm{d}100\right)$$
   即$3^{1492}$的最后两位是41。
   
   

4. 设$p$是一个素数，$p>3$，求证$2^{p-2}+3^{p-2}+6^{p-2}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right)$
   证明
   设$2^{p-2}+3^{p-2}+6^{p-2}\equiv a\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right)$，$a\in {\mathbb{Z}}_{>0}$最小。则有
   $$\begin{array}{rl}& 6\cdot 2^{p-2}+6\cdot 3^{p-2}+6\cdot 6^{p-2}\equiv 6a\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right)\\ & \Rightarrow 3\cdot 2^{p-1}+2\cdot 3^{p-1}+6^{p-1}\equiv 6a\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right)\end{array}$$
   由于$p$是素数且$p>3$，因此有
   $$\gcd \left(p,2\right)=\gcd \left(p,3\right)=\gcd \left(p,6\right)=1$$
   即$p\cancel{|}2,p\cancel{|}3,p\cancel{|}6$，由费马小定理有
   $$2^{p-1}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right),3^{p-1}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right),6^{p-1}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right)$$
   于是有
   $$6a\equiv 3\cdot 2^{p-1}+2\cdot 3^{p-1}+6^{p-1}\equiv 3\cdot 1+2\cdot 1+1\equiv 6\left(\mathrm{m}\mathrm{o}\mathrm{d}p\right)$$
   由$a\in {\mathbb{Z}}_{>0}$的最小性，解得$a=1$。
   
   

5. 解$3x\equiv 7\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)$。
   解

   1. 法一（解二元一次不定方程法）
      问题等价于求解$3x+10y=7$的整数解。
      $\gcd \left(3,10\right)|7$，因此不定方程有整数解。
      $$10=3\times 3+1$$
      $$P_0=1,P_1=3;Q_0=0,Q_1=1$$
      因此$3x+10y=1$有特解$\left({\left(-1\right)}^1{P}_1,{\left(-1\right)}^{1-1}{Q}_1\right)=\left(-3,1\right)$
      $3x+10y=7$有特解$\left(-3\times 7,1\times 7\right)=\left(-21,7\right)$
      $3x+10y=7$的通解为
      $$\{\begin{array}{rl}& x=-21-10t\\ & y=7+3t\end{array},\forall t\in \mathbb{Z}$$
      因此$3x\equiv 7\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)$的解为
      $$x=-21-10t\equiv 9\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)$$

   2. 法二（同余法）
      $$\gcd \left(3,10\right)=1,\phi \left(10\right)=\phi \left(2\right)\phi \left(5\right)=\left(2-1\right)\left(5-1\right)=4$$
      由欧拉定理有
      $$3^{\phi \left(10\right)}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)\iff 3^4\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)$$
      $$x=1\cdot x\equiv 3^{4}x=3^3\cdot \left(3x\right)\equiv 3^3\times 7=27\times 7\equiv 7\times 7=49\equiv 9\left(\mathrm{m}\mathrm{o}\mathrm{d}10\right)$$
      
      

6. 在${\mathbb{F}}_{13}=\mathbb{Z}/13\mathbb{Z}=\left\{\overline{0},\overline{1},\overline{2},\cdots ,\overline{12}\right\}$中，求$\frac{\overline{1}}{\overline{5}}$。
   解
   通过解二元一次不定方程来求解的方法可见博文初等数论 课堂笔记 第三章 – 剩余类，剩余类环，完全剩余系中剩余类，剩余类环一节的例子3。这里介绍另一种解法。
   由费马小定理，有
   $$5^{12}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}13\right)$$
   于是在${\mathbb{F}}_{13}$中，有
   $$\begin{array}{c}\begin{array}{rl}& \frac{\overline{1}}{\overline{5}}=\frac{\overline{5^{12}}}{\overline{5}}=\overline{5^{11}}\\ & \end{array}\\ 5^{11}={\left(5^2\right)}^5\times 5={25}^5\times 5\equiv {\left(-1\right)}^5\times 5=-5\equiv 8\left(\mathrm{m}\mathrm{o}\mathrm{d}13\right)\Rightarrow \overline{5^{11}}=\overline{8}\end{array}\}\Rightarrow \frac{\overline{1}}{\overline{5}}=\overline{8}$$
   
   

7. 将纯循环小数$0.\overline{34}$表示为有理数形式。
   解
   $$\begin{array}{rl}& 0.\overline{34}=0.343434\cdots \\ & =0.34+0.0034+0.000034+\cdots \\ & =0.34+0.34\times 0.01+0.34\times {0.01}^2+\cdots \\ & =\sum _{n=0}^{\infty }0.34\times {\left(0.01\right)}^n\\ & =\frac{0.34}{1-0.01}\\ & =\frac{34}{99}\end{array}$$
   
   

8. 将混循环小数$0.1\overline{3}$表示为有理数。
   解
   $$\begin{array}{rl}& 0.1\overline{3}=0.1333\cdots \\ & =0.1+0.03+0.003+0.0003+\cdots \\ & =0.1+\sum _{n=0}^{\infty }0.03\times {\left(0.1\right)}^n\\ & =0.1+\frac{0.03}{1-0.1}\\ & =\frac{2}{15}\end{array}$$
   
   

9. 如果今天是星期一，问从今天开始，再过${10}^{{10}^{10}}$天是星期几。
   解
   问题等价于求解$${10}^{{10}^{10}}\equiv a\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)$$其中$a\in {\mathbb{Z}}_{>0}$最小。
   $7$是素数，由欧拉定理，有
   $${10}^6\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)$$
   因此有
   $$\begin{array}{rl}& {10}^{{10}^{10}}={\left({10}^{10}\right)}^{{10}^9}={\left({10}^6\times {10}^4\right)}^{{10}^9}\equiv {\left({10}^4\right)}^{{10}^9}\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)\\ & {\left({10}^4\right)}^{{10}^9}={\left({10}^{40}\right)}^{{10}^8}={\left[{\left({10}^6\right)}^6\times {10}^4\right]}^{{10}^8}\equiv {\left({10}^4\right)}^{{10}^8}\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)\\ & {\left({10}^4\right)}^{{10}^8}={\left({10}^{40}\right)}^{{10}^7}={\left[{\left({10}^6\right)}^6\times {10}^4\right]}^{{10}^7}\equiv {\left({10}^4\right)}^{{10}^7}\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)\end{array}$$
   依此类推，可得
   $${\left({10}^4\right)}^{{10}^7}\equiv {\left({10}^4\right)}^{{10}^6}\equiv \cdots \equiv {\left({10}^4\right)}^{{10}^1}\equiv {\left({10}^4\right)}^{{10}^0}={10}^4\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)$$

   1. 法一（直接方法，推荐）
      于是有$${10}^{{10}^{10}}\equiv {10}^4={100}^2\equiv 2^2=4\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)$$
      从星期一的今天再过${10}^{{10}^{10}}$天是星期五。
   2. 法二（绕弯路方法，不推荐）
      于是有
      $$\begin{array}{rl}& {10}^{{10}^{10}}\equiv {10}^4\equiv a\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)\\ & \Rightarrow 1\equiv {10}^6\equiv 100a\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)\end{array}$$
      $7\cancel{|}100$，由费马小定理，有
      $${100}^{7-1}={100}^6\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)$$
      于是有
      $$a=1\cdot a\equiv {100}^{6}a={100}^5\times \left(100a\right)\equiv {100}^5={10}^{10}\equiv 3^{10}=9^5\equiv 2^5=32\equiv 4\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)$$
      由$a\in {\mathbb{Z}}_{>0}$的最小性，解得$a=4$。因此最终解得
      $${10}^{{10}^{10}}\equiv 4\left(\mathrm{m}\mathrm{o}\mathrm{d}7\right)$$
      从星期一的今天再过${10}^{{10}^{10}}$天是星期五。
      
      

10. 求${\left({12371}^{56}+34\right)}^{28}$被$111$除的余数是多少。
    解
    $$\begin{array}{rl}& {\left({12371}^{56}+34\right)}^{28}\\ & \equiv {\left({50}^{56}+34\right)}^{28}\left(\because 12371=111\times 111+50\right)\\ & ={\left({2500}^{28}+34\right)}^{28}\\ & \equiv {\left({58}^{28}+34\right)}^{28}\left(\because 2500=111\times 22+58\right)\\ & ={\left({3364}^{14}+34\right)}^{28}\\ & \equiv {\left({34}^{14}+34\right)}^{28}\left(\because 3364=111\times 30+34\right)\\ & ={\left({1156}^7+34\right)}^{28}\\ & \equiv {\left({46}^7+34\right)}^{28}\left(\because 1156=111\times 10+46\right)\\ & ={\left({2116}^3\times 46+34\right)}^{28}\\ & \equiv {\left(7^3\times 46+34\right)}^{28}\left(\because 2116=111\times 19+7\right)\\ & \equiv {\left(10\times 46+34\right)}^{28}\left(\because 7^3=343=111\times 3+10\right)\\ & ={494}^{28}\\ & \equiv {50}^{28}\left(\because 494=111\times 4+50\right)\\ & ={2500}^{14}\\ & \equiv {58}^{14}\left(\because 2500=111\times 22+58\right)\\ & ={3364}^7\\ & \equiv {34}^7\left(\because 3364=111\times 30+34\right)\\ & ={1156}^3\times 34\\ & \equiv {46}^3\times 34\left(\because 1156=111\times 10+46\right)\\ & =\left({46}^2\right)\times \left(46\times 34\right)\\ & \equiv 7\times 10\left(\because 2116=111\times 19+7,46\times 34=111\times 14+10\right)\\ & =70\left(\mathrm{m}\mathrm{o}\mathrm{d}111\right)\end{array}$$
    
    

11. 求${\left({12371}^{5600}+34\right)}^{28}$被$111$除的余数是多少。
    解（先用欧拉定理压缩指数）
    $$\begin{array}{c}111=3\times 37\\ \begin{array}{rl}& \gcd \left(12371,3\right)=1\Rightarrow {12371}^{\phi \left(3\right)}={12371}^2\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}3\right)\\ & \Rightarrow {\left({12371}^2\right)}^{18}={12371}^{36}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}3\right)\\ & \end{array}\\ \gcd \left(12371,37\right)=1\Rightarrow {12371}^{\phi \left(37\right)}={12371}^{36}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}36\right)\end{array}\}\Rightarrow {12371}^{36}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}\left(lcm\left(3,36\right)=111\right)\right)$$
    因此有
    $$\begin{array}{rl}& {\left({12371}^{5600}+34\right)}^{28}\\ & ={\left({\left({12371}^{36}\right)}^{155}\times {\left(12371\right)}^{20}+34\right)}^{28}\\ & \equiv {\left({\left(12371\right)}^{20}+34\right)}^{28}\left(\because {12371}^{36}\equiv 1\left(\mathrm{m}\mathrm{o}\mathrm{d}111\right)\right)\\ & \equiv {\left({50}^{20}+34\right)}^{28}\left(\because 12371=111\times 111+50\right)\\ & ={\left[{\left({50}^2\right)}^{10}+34\right]}^{28}\\ & \equiv {\left({58}^{10}+34\right)}^{28}\left(\because {50}^2=111\times 22+58\right)\\ & ={\left[{\left({58}^2\right)}^5+34\right]}^{28}\\ & \equiv {\left({34}^5+34\right)}^{28}\left(\because {58}^2=111\times 30+34\right)\\ & ={\left[{\left({34}^2\right)}^2\times 34+34\right]}^{28}\\ & ={\left[\left({\left({34}^2\right)}^2+1\right)\times 34\right]}^{28}\\ & \equiv {\left[\left({46}^2+1\right)\times 34\right]}^{28}\left(\because {34}^2=111\times 10+46\right)\\ & \equiv {\left(8\times 34\right)}^{28}\left(\because {46}^2+1=2117=111\times 19+8\right)\\ & \equiv {50}^{28}\left(\because 8\times 34=272=111\times 2+50\right)\\ & \equiv 70\left(\mathrm{m}\mathrm{o}\mathrm{d}111\right)\end{array}$$