Questions in category: 初等数论 (Elementary Number Theory)
数论 >> 一般数论 >> 初等数论
<[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] >

1. 关于阶乘

Posted by haifeng on 2019-07-28 23:12:54 last update 2019-07-28 23:34:22 | Answers (0) | 收藏


$4!+1==25==5^2$

$5!+1==121==11^2$

$7!+1==5041==71^2$

对于 $n!+1=m^2$, 除了上面的 $n=4,5,7$ 之外, 还有解吗?

$11!+1==39916801$ is a prime

 

 

References:

Richard K. Guy, Unsolved Problems in Number Theory, D25 Equations involving factorial $n$.

 

2. 求方程 $x^{341-1}\equiv 1\pmod{341}$ 的解, 这里 $x$ 为正整数.

Posted by haifeng on 2019-07-10 11:32:12 last update 2019-07-10 11:32:47 | Answers (0) | 收藏


求方程 $x^{341-1}\equiv 1\pmod{341}$ 的解, 这里 $x$ 为正整数.

 


我们这里使用 Calculator 进行计算

 

>> solve(x^340mod341==1,x,1,340)
in> solve(x^340@341~1,x,1,340)
ans>> x=1
ans>> x=2
ans>> x=4
ans>> x=8
ans>> x=15
ans>> x=16
ans>> x=23
ans>> x=27
ans>> x=29
ans>> x=30
ans>> x=32
ans>> x=35
ans>> x=39
ans>> x=46
ans>> x=47
ans>> x=54
ans>> x=58
ans>> x=60
ans>> x=61
ans>> x=63
ans>> x=64
ans>> x=70
ans>> x=78
ans>> x=85
ans>> x=89
ans>> x=91
ans>> x=92
ans>> x=94
ans>> x=95
ans>> x=97
ans>> x=101
ans>> x=108
ans>> x=109
ans>> x=116
ans>> x=120
ans>> x=122
ans>> x=123
ans>> x=125
ans>> x=126
ans>> x=128
ans>> x=139
ans>> x=140
ans>> x=147
ans>> x=151
ans>> x=153
ans>> x=156
ans>> x=157
ans>> x=159
ans>> x=163
ans>> x=170
ans>> x=171
ans>> x=178
ans>> x=182
ans>> x=184
ans>> x=185
ans>> x=188
ans>> x=190
ans>> x=194
ans>> x=201
ans>> x=202
ans>> x=213
ans>> x=215
ans>> x=216
ans>> x=218
ans>> x=219
ans>> x=221
ans>> x=225
ans>> x=232
ans>> x=233
ans>> x=240
ans>> x=244
ans>> x=246
ans>> x=247
ans>> x=249
ans>> x=250
ans>> x=252
ans>> x=256
ans>> x=263
ans>> x=271
ans>> x=277
ans>> x=278
ans>> x=280
ans>> x=281
ans>> x=283
ans>> x=287
ans>> x=294
ans>> x=295
ans>> x=302
ans>> x=306
ans>> x=309
ans>> x=311
ans>> x=312
ans>> x=314
ans>> x=318
ans>> x=325
ans>> x=326
ans>> x=333
ans>> x=337
ans>> x=339

------------------------

可以进行验算, 比如

>> 339^340mod 341
in> 339^340@341

out> 1

------------------------

也可以使用 expmo() 函数

>> expmo(339,340,341)
in> expmo(339,340,341)
calculate: 339^340(mod 341)
out> 1

 

3. 一些特殊的素数

Posted by haifeng on 2019-06-26 12:44:35 last update 2019-07-06 17:52:05 | Answers (0) | 收藏


 

229

 

19
109
1009
10009
1000000009
1000000000000000009
10000000000000000000009

 

>> factorise(1000000000001)
in> factorise(1000000000001)
73*137*99990001

 

>> factorise(1000000000000000001)
in> factorise(1000000000000000001)
101*9901*999999000001

 

>> factorise(10000000000000000001)
in> factorise(10000000000000000001)
11*909090909090909091

 

>> factorise(100000000000000000001)
in> factorise(100000000000000000001)
73*137*1676321*5964848081

 

>> factorise(1000000000000000000001)
in> factorise(1000000000000000000001)
7*7*11*13*127*2689*459691*909091

 

10000000000000000000001 == 89*101*1056689261*1052788969

1000000000000000000000001 == 17*5882353*9999999900000001

 

>> factorise(10000000000000000000000001)
in> factorise(10000000000000000000000001)
11*251*5051*9091*78875943472201

 


1000000000000000000000000001 == 7*11*13*19*52579*70541929*14175966169


>> factorise(10000000000000000000000000000001)
in> factorise(10000000000000000000000000000001)
11*909090909090909090909090909091

 

>> factorise(1000000000000000000000009)
in> factorise(1000000000000000000000009)
53*193*5189*82633*189169*1205257


100000000000000000000000000000000001 == 11*9091*4147571*909091*265212793249617641

 

1000000000000000000000000000000000001 == 73*137*3169*98641*99990001*3199044596370769

 

10000000000000000000000000000000000001 == 11*7253*422650073734453*296557347313446299

 


13
1367
13367
13333333367
13333333333333367
133333333333333333367
13333333333333333333333367
133333333333333333333333333333333333367


in> factorise(1333333333333333367)
7*190476190476190481

 

4. [Def] Carmichael数 (卡米歇尔数)

Posted by haifeng on 2019-06-12 23:29:05 last update 2019-07-10 11:34:36 | Answers (0) | 收藏


一个数 $n$, 如果对所有的基 $a$ (满足 $(a,n)=1$), 都有

\[
a^{n-1}\equiv 1\pmod n
\]

则称 $n$ 为 Carmichael 数.

 

性质: Carmichael 数一定是伪素数, 伪素数不一定是 Carmichael 数.

比如 341 是伪素数, 但 341 不是 Carmichael 数. 事实上方程 $x^{341-1}\equiv 1\pmod{341}$ 有很多解. (参见问题2306)

相关条目:  伪素数


 

Thm. (Carmichael数的判别法) 设 $n$ 为合数, 则 $n$ 是 Carmichael 数当且仅当 $n$ 是奇数且对整除 $n$ 的每个素数 $p$, 满足

  • $p^2\not\mid n$
  • $p-1\mid n-1$
     

 

5. 伪素数

Posted by haifeng on 2019-06-12 23:16:46 last update 2019-06-19 14:01:19 | Answers (4) | 收藏


所谓的伪素数是指满足费马小定理的合数.

Fermat 小定理: 设 $p$ 是一个素数, 且 $0 < a < p$, 则有 $a^{p-1}\equiv 1\pmod p$.

 

举出10000以内的所有伪素数. 比如1000以内的伪素数只有三个: 341, 561, 645.

10000 以内的pseudo prime 有:

341
561
645
1105
1387
1729
1905
2047
2465
2701
2821
3277
4033
4371
4681
5461
6601
7957
8321
8481
8911

------------

Total: 21


 

[10000, 20000] 以内的伪素数

10261, 10585, 11305,12801,13741,13747,13981,14491,15709,15841,16705,18705,18721,19951


 

6. [欧拉-费马定理]

Posted by haifeng on 2019-04-06 20:02:47 last update 2019-04-06 20:02:47 | Answers (0) | 收藏


欧拉-费马定理

Thm. 若 $a$ 与 $m$ 互素, 则

\[
a^{\varphi(m)}\equiv 1\pmod m
\]

特殊情形

若 $p$ 是一素数, 且 $a$ 不能被 $p$ 除尽, 则因 $\varphi(p)=p-1$, 所以有

\[
a^{p-1}\equiv 1\pmod p
\]

 


Remark:

[俄] A. K. 苏什凯维奇 著, 叶乃膺 译《数论初等教程》 定理 58.

7. 求同余方程 $x^{205}\equiv 3\pmod {1024}$.

Posted by haifeng on 2019-04-06 19:42:31 last update 2019-04-06 20:19:01 | Answers (1) | 收藏


求同余方程 $x^{205}\equiv 3\pmod{1024}$.

 

[讨论]

这是模为 $2^k$ 的同余式情形. 并且由于 3 是奇数(模2余1), 所以 $x$ 也必是奇数.

Note: $2^k$ 当 $k > 2$ 时没有元根(primitive root).

8. 设 $a,b,c$ 是三个素数, 求方程 $a(a+b)=12768+c$ 的所有解.

Posted by haifeng on 2019-04-04 09:29:04 last update 2019-04-04 09:35:34 | Answers (1) | 收藏


设 $a,b,c$ 是三个素数, 求方程 $a(a+b)=12768+c$ 的所有解.

 

 


Remark:

题目来源: QQ群: 编程&数论&椭圆曲线

9. 找两个不同汉字 $A$ 与 $B$, 使得 $AB$ 与 $BA$ 都是有意义的词, 且意思不一样.

Posted by haifeng on 2019-03-25 10:04:18 last update 2019-03-25 10:13:19 | Answers (2) | 收藏


(1) 找两个不同汉字 $A$ 与 $B$, 使得 $AB$ 与 $BA$ 都是有意义的词, 且意思不一样.

比如: 工人、人工

 

(2) 找两个不同汉字 $A$ 与 $B$, 使得 $AB$ 与 $BA$ 都是有意义的数学词汇, 且意思不一样.

 

 


Remark:

题目来源: 孙智伟

10. 因子个数函数 $\tau(n)$

Posted by haifeng on 2019-03-22 09:42:26 last update 2019-03-22 09:42:26 | Answers (0) | 收藏


$\tau(n)$ 是计算正整数 $n$ 的因子个数的一个函数, 也就是所有能整除 $n$ 的数的个数.

定义为:

\[
\tau(n):=\sum_{d|n}1.
\]

<[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] >