归档 220901 | 梅开四度：初等数论 - 整除，同余，排列组合

致敬经典：

数↗学，能够使我的灵↗魂↗得到升↗华↘。

1. 证明：任意奇数的平方减 \(1\) 是 \(8\) 的倍数。

   设该奇数为 \(2n+1\)，则：

   \[\begin {aligned} (2n + 1) ^ 2 - 1 &= (4n ^ 2 + 4n + 1) - 1 \newline &= 4n ^ 2 + 4n \newline &= 4(n ^ 2 + n) \end {aligned} \]

   1. 当 \(n\) 为奇数时

      \(n^2\) 为奇数，\(n ^ 2 + n\) 为偶数，\((2n + 1) ^ 2 - 1\) 为 \(8\) 的倍数。

   2. 当 \(n\) 为偶数时

      \(n^2\) 为偶数，\(n ^ 2 + n\) 为偶数，\((2n + 1) ^ 2 - 1\) 为 \(8\) 的倍数。

   综上，\((2n + 1) ^ 2 - 1\) 为 \(8\) 的倍数。

2. 证明：当 \(n\) 是非负偶数时，\(2\mid3^n+1\)；当 \(n\) 是奇数时，\(2^2\mid3^n+1\)；但无论 \(n\) 是偶数还是奇数，对任意正整数 \(\alpha>2\)，都有 \(2^ \alpha \nmid 3^n+1\)。

   有定理：\(a^b\bmod c=(a^{b-1}\bmod c) \times a \bmod c\ \ (b\geqslant 1)\)。

   已知 \(3^0 \bmod 8 = 1\)，则 \(3^1\bmod 8 = 3,\,3^2\bmod 8 = 1,\,3^3\bmod8=3,\dots\)。

   归纳可得：

   \[3^i\bmod 8= \begin{cases} 1\quad i\bmod2=0 \newline \newline 3\quad i\bmod 2=1 \end{cases} \newline \therefore(3^i\bmod8)+1=\begin{cases} 2\quad i\bmod2=0 \newline \newline 4\quad i\bmod 2=1 \end{cases} \]

   所以，当 \(n\) 是非负偶数时，\(2\mid3^n+1\)；当 \(n\) 是奇数时，\(2^2\mid3^n+1\)。

   因为模数为 \(8\) 且不存在值为 \(0\) 的项，所以 \(2^3\nmid3^n+1\)。而当 \((3^i\bmod8)+1\bmod2^3=0\) 时，\((3^i\bmod8)+1\bmod2^4\) 才可能为 \(0\)，所以当 \(\alpha>2\) 时，\(2^\alpha\nmid 3^n+1\)。

3. 设 \(a,b\in\Z\)，且 \(b\ne 0\)，证明：存在唯一的 \(q,r\in\Z\)，使得 \(a=qb+r\)，其中 \(-|b|\div2\leqslant r<|b|\div 2\)。

   1. 当 \(b>0\) 时：

      令 \(k=\lfloor a\div b \rfloor\)，则有 \(kb\leqslant a<(k+1)b\)。

      设 \(x=a-kb,\,y=(k+1)b-a\)，则 \(x+y=b\)。

      1. 当 \(x< b\div 2\) 时

         \(\because y=b-x\)

         \(\therefore y\geqslant b\div 2\)

         令 \(r=x\)，\(r\) 唯一，得证。

      2. 当 \(x\geqslant b\div 2\) 时

         \(\because y=b-x\)

         \(\therefore y\leqslant b\div 2\)

         令 \(r=-y\)，\(r\) 唯一，得证。

   2. 当 \(b<0\) 时：

      同理。

   综上，原命题成立。

4. 证明：如果 \(2a+3b,\, 9a+5b\) 中有一个能被 \(17\) 整除，那么另外一个也能被 \(17\) 整除。

   闲话：待定系数，永远的神

   设 \(17a+17b=x(2a+3b)+y(9a+5b)\)，则：

   \[\begin{cases} 2x+9y=17 \newline 3x+5y=17 \end{cases} \]

   解得：

   \[\begin{cases} x=4 \newline y=1 \end{cases} \]
   \[\therefore 17\mid 2a+3b \iff 17\mid 9a+5b \]

5. 假定 \(d_1,d_2,\cdots,d_k\) 是 \(n\) 的全部正因数，试证：\((d_1d_2\cdots d_k)^2=n\)。

   1. 当 \(n\) 是完全平方数，即 \(\exists\,\, x\) 使得 \({d_x}^2=n\) 时

      对于 \(\forall\,\, i=[1,\,k]\) 且 \(i\ne x,\,\exists\,\, j\) 使得 \(d_id_j=n\)。

      \[\therefore \prod\limits_{i\ne x}d_i=n^{(k-1)\div2}，\prod\limits_{i=1}^k d_i=n^{(k-1)\div2}\times d_x \newline \begin{aligned} \therefore (\prod_{i=1}^k d_i)^2&=(n^{(k-1)\div2}\times d_x)^2 \newline &=(n^{(k-1)\div2})^2\times {d_x}^2 \newline &=n^{k-1}\times n \newline &=n^k \end{aligned} \]

   2. 当 \(n\) 不是完全平方数，即 \(\not\exists \,\,x\) 使得 \({d_x}^2=n\) 时

      对于 \(\forall \,\, i=[1,\,k],\,\exists\,\,j\) 使得 \(d_id_j=n\)。

      \[\therefore \prod_{i=1}^k d_i=n^{k\div2} \newline \begin{aligned} \therefore (\prod_{i=1}^k d_i)^2&=(n^{k\div 2})^2 \newline &=n^k \end{aligned} \]

   综上，原命题成立。

6. 求下列最大公因数或最小公倍数：

   闲话：我可以欧几里得吗，，，

   1. 求 \((1492,1066)\)。

      \[1492 = 2\times 746 =2^2\times 373 \newline 1066 = 2\times 533 =2\times 13\times 41 \newline \therefore (1492,1066)=2 \]

   2. 求 \((24871,3468)\)。

      \[24871 = 7\times 3553 = 7\times 11\times 323=7\times 11\times 17\times 19 \newline 3468 = 2^2\times 867 =2^2\times 3\times289=2^2\times 3\times 17^2 \newline \therefore (1492,1066)=17 \]

   3. 求 \((120,504,882)\)。

      \[120 = 2^3\times 3 \times 5 \newline 504 = 2^3\times 3^2\times 7 \newline 882=2\times 3^2\times 7^2 \newline \therefore (120,504,882)=6 \]

   4. 求 \([135,513,3114]\)。

      \[135 = 3^3\times 5 \newline 513 = 3^3\times 19 \newline 3114=2\times 3^2\times 173 \newline \therefore [135,513,3114]=887490 \]

7. 将 \((1485,1745)\) 表成 \(1485s+1745t\) 的形式，其中 \(s,t\in\Z\)。

   \[1485=3^3\times 5\times 11 \newline 1475=5^2\times 59 \newline \therefore (1485,1745)=5 \]

   由题意得 \(1485s+1745t=5\)，程序 枚举得，一组合法解为 \(\begin{cases} s=-47 \newline t=40\end{cases}\) 。

8. 设整数 \(a>1\)，\(m,n\) 均是正整数，求证：\((a^m-1,a^n-1)=a^{(m,n)-1}\)。

9. 设 \(a,b\) 均为正整数，证明：在数列 \(a,2a,\cdots,ba\) 中，\(b\) 的倍数的个数等于 \((a,b)\)。

10. 设 \(n\) 和 \(a\) 都是正整数，且 \(\sqrt[\large n]a\) 不是整数。求证：\(\sqrt[\large n] a\) 是无理数。

闲话：这是不是已经脱离数论的范畴了，，，

11. 解下列一次不定方程：

    闲话：您干脆不装了是吧，，，

    1. \(19x+20y=1909\)
    2. \(1485x+1745y=15\)
    3. \(1492x+1066y=-4\)
    4. \(8x-18y+10z=16\)

12. 解不定方程组 \(\begin{cases}x+2y+3z=10\newline x-2y+5z=4\end{cases}\) 。

13. 鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁，鸡母和鸡雏各多少？

14. 证明：对任意整数 \(n\)，都有 \(121\nmid n^2+2n+12\)。

15. 设 \(a,b\) 是互素的正整数，\(d\mid ab\)，证明：存在唯一的 \(d_1\mid a\) 及 \(d_2\mid b\)，使得 \(d=d_1d_2\)。

16. 证明：如果 \(3\mid a^2+b^2\)，那么 \(3\mid a\) 且 \(a\mid b\)。

17. 设素数 \(p>3\)，证明：\(2p+1\) 和 \(4p+1\) 不能同时为素数。

18. 设 \(p\) 是素数，证明：满足 \(a^2=pb^2\) 的正整数 \(a,b\) 不存在。

19. 设整数 \(n>1\)，证明：如果 \(n\) 不能被小于或等于 \(\sqrt[\large 3] n\) 的素数整除，那么 \(n\) 为素数或两素数之积。

20. 求证：对任意 \(n\in\Z^+\)，第 \(n\) 个素数 \(p_n\) 满足 \(p_n\leqslant 2^{2^{\large n-1}}\)。

21. 试证：对任意正整数 \(k\)，都存在无穷多个整数 \(a\)，使得数列 \(a+1,a+2,\cdots,a+k-1\) 中没有一个素数。

22. 设整数 \(n>2\)，求证：在 \(n\) 和 \(n!\) 之间一定存在素数。