免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[数论] 一起来研究数论问题集

本帖最后由 hbghlyj 于 2020-1-29 14:01 编辑

暂时不会解的题用红色标出了。
这贴主要是提出一些疑问基于250 Problems in Elementary Number Theory - Sierpinski (1970)
Problems in Elementary Number TheoryPeter Vandendriessche&Hojoo Lee
Mathlink数论难题
Hojoo Lee数论问题集A 1-57周晓东的解答载于《初等数论难题集(第二卷)上》
下面是《算术问题集Problems in Arithmeticae》附录2,3(少部分有答案)

1

0001.jpg
2020-1-21 23:02

2

0002.jpg
2020-1-21 23:02

3

0003.jpg
2020-1-21 23:02

4

0004.jpg
2020-1-21 23:02

5

0005.jpg
2020-1-21 23:03

6

0006.jpg
2020-1-21 23:03

7

0007.jpg
2020-1-21 23:03

8

0008.jpg
2020-1-21 23:03

9

0009.jpg
2020-1-21 23:03

10

0010.jpg
2020-1-21 23:03

11

0011.jpg
2020-1-21 23:04

12

0012.jpg
2020-1-21 23:04

13

0013.jpg
2020-1-21 23:04

14

0014.jpg
2020-1-21 23:04

15

0015.jpg
2020-1-21 23:04

16

0016.jpg
2020-1-21 23:04

17

0017.jpg
2020-1-21 23:04

18

0018.jpg
2020-1-21 23:04

19

0019.jpg
2020-1-21 23:04

20

0020.jpg
2020-1-21 23:05

21

0021.jpg
2020-1-21 23:05

22

0022.jpg
2020-1-21 23:05

269.质数p$\equiv7\pmod8$,计算$\sum\limits_{n=1}^{p-1}n\left(\frac{4n+1}p\right)$("级数"一章中介绍了一个关于勒让德符号裂项的方法)
270.求证$\sin(A-B)\sin(C-D)=\sin(A-D)\sin(C-B)-\sin(A-C)\sin(B-D)$
托勒密定理
271.对于不定方程$\varphi(n)=2m$,求证
(1)如果m的任何>1的约数d都使得2d+1是合数,那么方程无解
(2)如果m所有质因子模3余1,那么方程无解
(3)m是>3的质数的平方,无解
(4)取定m,那么解的个数是0,2,4中的一个
272.p是>3的质数,a,b是正整数,求证$C_{ap-1}^{p-1}\equiv C_{bp-1}^{p-1}\pmod {p^3}$
273.计算$\sum\limits_{abk|n\\(a,b)=1}\varphi(abk)\varphi(k)$
274.求证对任意正整数n,方程$\varphi(x+n)=3\varphi(x)$至少有1个解.
275.利用积性计算$\sum\limits_{1\le k\le n}2^{\omega(k,n)}$.
276.求证$(n+1)[C_n^1,C_n^2,C_n^3,\cdots,C_n^n]=[1,2,3,4,\cdots,n+1]$
277.质数p,q满足p=2q+1,4|q-3,求证如下方程组无整数解.\[\left\{ \begin{array}{l}
p|{x^x} - 1\\
1 < x < p - 1
\end{array} \right.\]求证无数个质数p使得上述方程组有解.
278.完全数n的最小素因子是p,求证$\omega(n)\ge p$
279.n!+2|(2n)!,求所有满足条件的自然数
280.计算$\prod\limits_{d|n}d^{\varphi(d)+\varphi(\frac nd)}$
约数凑对,答案$n^n$
281.求证\[n!(n+1)!(n+2)!\cdots(2n-1)!|1!4!7!\cdots(3n-2)!.\]来自一个有关幻方的计数题 波利亚
282.$\overline{aabbbbcccc}-7$是平方数(比如$34641^2=1199998881$),$\overline{abc}=\underline{\quad}$
283.找出形如$\overline{aabbccddee}$的平方数,比如$74162^2=5500002244$
284.定义f(n)表示n的某些约数的乘积,这些约数都是n的整数次算术根.计算$\sum\limits_{n\in\mathbf N^+}\left(\frac{f(n)}{n+1}\right)^{\frac1n}$

本帖最后由 hbghlyj 于 2020-4-17 15:33 编辑

《Sierpinski250》
Ⅰ整除
1.求所有正整数n使得$n+1|n^2+1$
$\because n+1|n^2-1\therefore n+1|2,n+1=2,n=1$
2.求所有$\ne$3的整数使得$x-3|x^3-3$
$x-3|3^3-3=24,x=-21, -9, -5, -3, -1, 0, 1, 2 ,4, 5, 6, 7, 9, 11, 15, 27$
3.存在无穷多正整数n使得$4n^2+1$同时被5和13整除
取$n=65k\pm4$即可
4.对任意正整数n证明$169|3^{3n+3}-26n-27.$
$27(27^n-1)-26n=27\bullet26(27^{n-1}+27^{n-2}+\cdots+1)-26n\equiv26(27^{n-1}+27^{n-2}+\cdots+1-n)\equiv0\pmod{169}.$
5.对任意自然数k证明$19|2^{2^{6k+2}}+3$
$19=2^{2^2}+3|2^{2^{6k+2}}+3^{2^{6k}}$,只需证$19|3^{2^{6k}-1}-1$,只需证$18|4^{3k}-1$,
6.证明Kraïtchik定理:$13|2^{70}+3^{70}$
$13=2^2+3^2|2^{70}+3^{70}$
7.求$20^{15}-1$的最小的四个质因子
$20^{15}-1\equiv(-1)^{15}-1=-2\pmod3$
$20^{15}-1\equiv-1\pmod5$
$20^{15}-1\equiv(-1)^{15}-1=-2\pmod7$
$20^{15}-1\equiv64^{15}-1=2^{90}\equiv0\pmod{11}$
$\cdots$
$20^{15}-1\equiv1^{15}-1=0\pmod{19}$
$\cdots$
$20^{15}-1\equiv144^{15}-1=12^{30}-1\equiv0\pmod{31}$
$\cdots$
$20^{15}-1\equiv81^{15}-1=3^{60}-1\equiv0\pmod{61}$
事实上$20^{15}-1=11\bullet19\bullet31\bullet61\bullet251\bullet421\bullet3001\bullet261451$
8.证明:对正整数m和a>1有$\left(\frac{a^m-1}{a-1},a-1\right)=(a-1,m)$
设b=a-1,$\left(\frac{(b+1)^m-1}b,b\right)=(b^{m-1}+C_m^2b^{m-2}+\cdots+C_m^2b+m,b)=(b,m)$
9.对任意正整数n,$1^3+2^3+\cdots+n^3\mid3(1^5+2^5+\cdots+n^5)$
$3(1^5+2^5+\cdots+n^5)=(1^3+2^3+\cdots+n^3)(2n^2+2n+1)$
10.求所有整数n>1使得$n\mid1^n+2^n+\cdots+(n-1)^n$
若n为奇数,首尾配对,命题显然成立.若n为偶数,设$2^s\parallel n,s\in\mathbf N_+$,由于$2^s\ge s,$对偶数k有$2^s|k^n$,对奇数k(在$1,2,\cdots,n-1$中有$\frac12n$个),由欧拉定理,$k^{2^{s-1}}\equiv1\pmod{2^s},k^n\equiv1\pmod{2^s}$.故$1^n+3^n+\cdots+(n-3)^n+(n-1)^n\equiv\frac12n\pmod{2^s}$,从而$1^n+2^n+\cdots+(n-1)^n\equiv\frac12n\pmod{2^s}$.
反过来,如果n是偶数且$n\mid1^n+2^n+\cdots+(n-1)^n$,由$2^s|n$得$\frac12n\equiv0\pmod{2^s},2^s|\frac12n,2^{s+1}|n,$与s的定义相矛盾.
因此,满足条件的n是所有奇数.
按:设n是素数,由费马小定理易得$n|1^{n-1}+2^{n-1}+\cdots+(n-1)^{n-1}+1$,但我们不知道有多少合数满足这个关系.G.Ginga猜测没有满足这个关系的合数,并证明了$n<10^{1000}$范围内没有这种合数.
11.求正整数n使得$5\mid a_n=2^{2n+1}-2^{n+1}+1$
求正整数n使得$5\mid a_n=2^{2n+1}+2^{n+1}+1$
考虑四种情况:
1°n=4k,k$\in\mathbf N_+$,则$a_n=2^{8k+1}-2^{4k+1}+1\equiv2-2+1\equiv1\pmod5,b_n=2^{8k+1}+2^{4k+1}+1\equiv2+2+1\equiv0\pmod5$
2°n=4k+1,k$\in\mathbf N$,则$a_n=2^{8k+3}-2^{4k+2}+1\equiv8-4+1\equiv0\pmod5,b_n=2^{8k+3}+2^{4k+2}+1\equiv8+4+1\equiv3\pmod5$
3°n=4k+2,k$\in\mathbf N$,则$a_n=2^{8k+5}-2^{4k+3}+1\equiv2-8+1\equiv0\pmod5,b_n=2^{8k+5}+2^{4k+3}+1\equiv2+8+1\equiv1\pmod5$
4°n=4k+3,k$\in\mathbf N$,则$a_n=2^{8k+7}-2^{4k+4}+1\equiv8-1+1\equiv3\pmod5,b_n=2^{8k+7}+2^{4k+4}+1\equiv8+1+1\equiv0\pmod5$
因此,$5|a_n\Leftrightarrow n\equiv1,2\pmod4,5|b_n\Leftrightarrow n\equiv0,3\pmod4$,所以只有一组$a_n,b_n$是5的倍数
12.证明:对任意正整数n,存在正整数x使得数列$x+1,x^x+1,x^{x^x}+1,\cdots$的各项均被n整除
13.证明:存在无穷多正整数n,对任意偶数x,数列$x+1,x^x+1,x^{x^x}+1,\cdots$的各项均不被n整除
14.对正整数n,证明:$n^2\mid (n+1)^n-1$
15.对正整数n,证明:$(2^n-1)^2\mid 2^{(2^n-1)^n}-1$
16.存在无穷多正整数n使得$n\mid 2^n+1$;找到其中所有的素数
17.对任意正整数a>1,存在无穷多正整数n使得$n\mid a^n+1$
18.存在无穷多正整数n使得$n\mid2^n+2$
19.求所有正整数a使得$10\mid a^{10}+1$
条件等价于a是奇数且$5\mid a^{10}+1$,$-1\equiv a^{10}\equiv a^2\pmod5$,$a\equiv\pm2\pmod5$,总之,$a\equiv 3,7\pmod{10}$
20.不存在整数n>1使得$n\mid 2^n-1$
存在无穷多正整数n使得$n\mid 2^n+1$
21.求所有级数n使得$n\mid 3^n+1$
22.求所有正整数n使得$3\mid n2^n+1$
23.对任意奇素数p存在无穷多正整数n使得$p\mid n2^n+1$
24.对任意正整数n存在正整数x>n和y,$x\ne y$,使得$x^x\mid y^y$
25.对奇数n,证明:$n\mid2^{n!}-1$
26.数列$2^n-3(n=2,3,4,\cdots)$包含无穷多5的倍数和无穷多13的倍数,但不含$5\cdot13$的倍数
27.求最小的合数n使得$n\mid2^n-2$且$n\mid3^n-3$
28.求最小正整数n使得$n\mid2^n-2$且$n\not\mid3^n-3$
29.求最小整数n使得$n\not\mid2^n-2$且$n\mid3^n-3$
30.对任意正整数a,求合数n使得$n\mid a^n-a$
31.整数a,b,c满足$9\mid a^3+b^3+c^3$,则$3\mid abc$
反证法,若$3\not\mid n$,则$n^3\equiv\pm1\pmod9$,而三个$\pm1$之和不能为9的倍数
32.正整数$a_k(k=1,2,3,4,5)$满足$9|a_1^3+a_2^3+a_3^3+a_4^3+a_5^3,$则$3\mid a_1a_2a_3a_4a_5$
做法同31
33.正整数x,y,z满足(x,y)=1,$x^2+y^2=z^4$,则$7\mid xy$;说明条件(x,y)=1是必要的.
34.整数a,b满足$7\mid a^2+b^2,$则$7\mid a,7\mid b$
做法同31.若$7\not\mid n$,则$n^2\equiv 1,2,4\pmod7$.
35.存在无穷多正整数x,y使得$x(x+1)\mid y(y+1),x\not\mid y,x+1\not\mid y,x\not\mid y+1,x+1\not\mid y+1,$并求最小的一对(x,y)
36.对每个正整数s$\le25$和s=100,求最小的n的倍数$n_s$,它在十进制下的数字和为s.
37.对任意正整数s存在s的倍数n,它在十进制下的数字和为s.
38.证明
(a)每个正整数的4k+1型因子不少于4k+3型因子
(b)存在无穷多正整数,其4k+1型因子数等于4k+3型因子数
(c)存在无穷多正整数,其4k+1型因子数大于4k+3型因子数
39.若a,b,c是整数,n是>3的整数,则存在整数k使得k+a,k+b,k+c都不是n的倍数
40.$F_n=2^{2^n}+1$,证明$F_n\mid2^{F_n}-2$
由平方差公式易得


补充题第一组:
1.陶平生式枚举
将2019表示成一个正整数等比数列的连续三项之和.则表达式为
注意到2019=$3\bullet673$,且673为3n+1型素数,可唯一表示为形如$a^2+ab+b^2$(正整数a与b互素)的一个等比数列的三项和
由$673=a^2+ab+b^2$解得a=8,b=21,所以192,504,1323满足题设
事实上满足题设的所有三项等比正整数列为
192,504,1323
169,481,1369
还有一种含有负整数
1369,-1850,2500
换成2020,方程$2020=\frac{b^2}{a}+a+b$就无解,只有$2020=-\frac{b^2}{a}+a+b$即中项是负整数的情况:
404,-808,1616
320,-720,1620
500,-900,1620
4,-88,1936
1764,-1848,1936
2.证明:有无穷多个n使得$\frac{n^{15} - 1}{n-1}$的质因子的个位均为1
$\frac{n^{15} - 1}{n-1}=\left(n^2+n+1\right) \left(n^4+n^3+n^2+n+1\right) \left(n^8-n^7+n^5-n^4+n^3-n+1\right)$
即:有无穷多个n使得$\frac{n^{15} - 1}{n-1}$的素因子均为5k+1型
$(n^3)^5\equiv 1\pmod p$,要么$n^3=1 \pmod p$,要么5|p-1,只需构造这样的n的无穷序列,使得$\frac{n^3- 1}{n-1}$的素因子均为5k+1型
3.x、y、z都是正整数,证明:(xy+t)(yz+t)(zx+t)是完全平方数,当且仅当(xy+t)、(yz+t)、(zx+t)都是完全平方数。
4.n是正整数,当k∈{1,2,...,99}时,\[\frac{{{1^k} + {2^k} + ... + {n^k}}}{n}\]都是整数,证明n没有2到99之间的素因子
5.a,b,c是任意自然数,确定表达式$a^3+b^3+c^3-3abc$的所有可能值
这好像是哪一届初联题?
6.设a,b,c,n为满足如下条件的正整数
(1)a,b,c,a+b+c两两互素
(2)(a+b)(b+c)(c+a)(a+b+c)(ab+bc+ca)是完全n次方数.
证明:abc可表示为两个完全n次方数之差
7.a,b,c,d是不同的正整数,$\frac a{a+b}+\frac b{b+c}+\frac c{c+d}+\frac d{d+a}$是整数,求证a+b+c+d不是素数
8.证明有无穷多个正整数不能表为$2^a+3^b-5^c(a,b,c\in\mathbf N)$的形式
在模m的完全剩余系中可表为$2^a+3^b-5^c$形式的数最多有$f(2,n) f(3,n) f(5,n)$个.
只需找到这样的n,使$f(2,n) f(3,n) f(5,n)<n$,这里f(m,n)是数列$n,n^2,n^3,\cdots$模m的全部可能值数=第一个出现循环的项数-1=模m的周期+不属于周期的前几项数,比如m=120符合要求,因为$3\bullet5\bullet7=105<120$
下面给出10000以下的这种可用于构造的数
f[m_, n_] =
IntegerExponent[n, m] +
  MultiplicativeOrder[m, n/m^IntegerExponent[n, m]]; Select[
Range[2, 10000], f[2, #] f[3, #] f[5, #] < # &]
{120, 240, 504, 1040, 1560, 1638, 2184, 2520, 2730, 3120, 3276, 3640, \
4080, 4095, 4368, 4680, 4920, 5040, 5440, 5460, 6240, 6552, 6600, \
7280, 7812, 8160, 8190, 9360, 9576, 9840}
9.证明:对任意实数λ>0以及任意非负整数k,一定存在整数n使得$n^2+k$的最大素因子小于λn.
10.证明:素数倒数和发散
因为$(1+p_1+p_1^2+...)(1+p_2+p_2^2+...)...(1+p_n+p_n^2+...)>1+\frac12+\frac13+...+\frac1n$
这是因为每个自然数都是由前面几项乘起来的
而由熟知$1+\frac12+\frac13+...+\frac1n>\ln n$
所以$∑\ln(1+\frac 1{p_n}+\frac1{p_n^2}+...)>\ln\ln n$
而$1+\frac1{p_n}+\frac1{p_n^2}+...=1+\frac1{p_n-1}$
故$∑\frac1{p_n-1}$发散,$∑\frac1{p_n}$发散
11.数列$\{a_n\}:a_{n+1}=2^{a_n},a_0=1$,求$\{a_n\}$mod p
12.已知二次多项式f(x)=$ax^2+bx+c$,$n\in\mathbf N$,证明:至多存在一个n次多项式g(x),使得f(g(n))=g(f(n))
13.$\mathbb Z^n$中,如果两点的距离为1,就称它们相邻.求对哪些正整数n,存在点集S,$\forall P\in \mathbb Z^n,s(p)=\left\{ \begin{array}{l}
0\quad P \in S\\
1\quad P \notin S
\end{array} \right.$.其中s(p)为S中与P相邻的点数.
类似扫雷游戏?
n=1时,取$P=\{x\mid3|x\}$隔两个点取一个放进S中即可
n=2时,取$P=\{(x_1,x_2)\mid5|x_1+2x_2\}$类似五子棋八卦阵
一般地,取$P=\{(x_1,x_2,\cdots,x_n)\mid2n+1|x_1+2x_2+\cdots+nx_n\}$
把P平移到相邻的点就是把P的一个坐标±1,同时$x_1+2x_2+\cdots+nx_n$改变$±1,±2,\cdots,±n$,再加上,就构成了模2n+1的完全剩余系.由完全剩余系的性质满足条件.
14.$p=2^{2^m}+1$为素数,求证:使得$2^n\equiv1\pmod{p^{k+1}}$的最小正整数n=$2^{m+1}p^k$
15.a为奇数,n为正整数,求证$a^{2^n}\equiv1\pmod{2^{n+2}}$
证明:n=1时a-1,a+1为相邻偶数,其中恰有一个4的倍数,$8|a^2-1\Rightarrow a^2\equiv1\pmod8$
设命题对n=k为真,即$2^{n+2}|a^{2^n}-1$,而$2|a^{2^n}+1$,则$2^{n+3}|(a^{2^n}-1)(a^{2^n}+1)=a^{2^{n+1}}-1$,由归纳原理,命题对任意正整数n成立.

TOP

陶爷爷好像把2L的分解放在他模拟卷的前几题里

TOP

TOP

第八题的a,b,c是非负整数还是正整数?不能取0就没意义了。。

TOP

回复 5# Shiki
不理解5#的意思,能否详细说明一下?我觉得没问题啊。

TOP

回复 6# hbghlyj


    对正整数a,b,c原式只产生偶数值啊

TOP

本帖最后由 hbghlyj 于 2020-1-22 12:36 编辑

回复 7# Shiki
已改.这样更严谨些.
终于修好了程序,运行结果如下
QQ浏览器截图20191016125241.png
2020-1-22 12:35

120是最小的√

TOP

TOP

本帖最后由 realnumber 于 2020-1-28 11:58 编辑

14.对正整数n,证明:$n^2\mid (n+1)^n-1$
由公式$(a^n-1)=(a-1)(a^{n-1}+a^{n-2}+...+1)$
$(n+1)^n-1=n((n+1)^{n-1}+(n+1)^{n-2}+...+1)$
右边每个都用二项式定理展开,有n个1,这样就有$n^2\mid (n+1)^n-1$
一开始直接二项展开也可以的
15.n=2代入不对了,后面改成+1,n=4代入不对了
16.$n=3^k,k\in N^+$,用数学归纳法证,见下面20.
17.a为偶数时,$n=(a+1)^k,k\in Z$,特例参考16题,证明也用数归类似;a为奇数时,$n=2t,$t为奇数,且$t=\frac{a^2+1}{2^{m_0}},m_0$为某一适当大小的唯一的一个整数,特例参考21题,证明类似.
由费马小定理,素数$p\mid 2^{p-1}-1$,由$2^p+1=2(2^{p-1}-1)+3$,得到$p\mid 3$,所以只能有p=3.
20.不存在整数n>1,有$n\mid 2^n-1$,存在无数个正整数n,$n\mid 2^n+1$
假设存在这样的n,有$n\mid 2^n-1$,$2^n-1$为奇数,所以n也为奇数,假设p是n的最小的质因数.有$p\mid 2^n-1$
又由费马小定理$p\mid 2^{p-1}-1$,又假设满足$p\mid 2^x-1$的所有大于1的正整数x中,k是最小的一个,
以下先证明$k\mid n,k\mid p-1$
$n=rk+r_0,0\le r0<k,r,r_0\in Z$.
有$p\mid 2^k-1$,则有$p\mid 2^{kr}-1$,有$p\mid (2^n-1)-(2^{kr}-1)$,即$p\mid 2^{kr}(2^{r_0}-1)$
即$p\mid 2^{r_0}-1$,又k是最小正整数,所以$r_0=0$,即$k\mid n$,同理$k\mid p-1$
又p是n的最小因数,因而(n,p-1)=1,这与$k\mid n$,同理$k\mid p-1$矛盾
所以不存在整数n>1,有$n\mid 2^n-1$.
存在无数个正整数n,$n\mid 2^n+1$,令$n=3^{k},k\in Z$
由$2^{3^{k+1}}+1=(2^{3^k}+1)((2^{3^k})^2-2^{3^k}+1)$容易用数学归纳法证明.
21题(未证明所有解都在了),程序发现前几个依次是1,2,10,50,250,1250,以下用数学归纳法证明$n=2\times 5^k,k\in Z$都是解,被2整除显然,以下证明$5^k\mid 9^{5^k}+1$
$9^{5^{k+1}}+1=(9^{5^k}+1)((9^{5^k})^4-(9^{5^k})^3+(9^{5^k})^2-(9^{5^k})+1)$右边第2个括号可以被5整除,得证.
为什么没有其它解,还没想出来.
22.穷举n=6k,6k+1,6k+2,..,6k+5,k为整数,只有6k+1,6k+2都符合
23.以下字母都是正整数,令n=kp+r,0≤r<p
$p\mid n2^n+1$等价于$p\mid r2^{k+r}+1$,令r=p-1,即$p\mid 2^{k+p-1}-1$,
只需令k=t(p-1)即符合题意.即n=t(p-1)p+p-1.
24.题目打错了?n后面没出现
25.先做些整备工作,
p为奇素数,则$2^{p-1}=1(\mod p)$,可用数学归纳法证明(参考21的证明)$2^{p^{k-1}(p-1)}=1(\mod p^k,k\in Z^+)$
p,q为两个不同的奇素数,$2^{(p-1)(q-1)}=1 \mod pq$,进一步用数归可证$2^{p^{k-1}q^{m-1}(p-1)(q-1)}=1 \mod p^kq^m$,推广到多个不同奇素数都成立
n按质因数分解为$n=p^kq^m.....$,而$p^{k-1}q^{m-1}(p-1)(q-1)...$是小于n的一个数,必定包含在n!中,25题成立
26.当且仅当n=3+4k时,$5\mid 2^n-3$,n=4+12k时,$13\mid 2^n-3$,没有n符合2者
27.28.29.三题是程序找的,分别是n=561.n=341,n=6

TOP

回复 10# realnumber
24.应该没打错:x>n出现了n

TOP

回复 11# hbghlyj


    那,这样?x=n+1,y=2(n+1)

TOP

返回列表 回复 发帖