费马小定理

蔡家雄

费马小定理1

设 p为素数，（2和5除外）
则 1/p的循环节长d是(p -1)的因子。


费马小定理2

设 p为素数，a与p互素，
则 a^p   mod   p = a.


费马小定理3

若 4x+1= p 为素数，
则 p^1 = a^2+b^2 （一组解）
则 p^2 = a^2+b^2 （一组解）
则 p^3 = a^2+b^2 = c^2+d^2（两组解）
则 p^4 = a^2+b^2 = c^2+d^2（两组解）
则 p^5 = a^2+b^2 = c^2+d^2 = e^2+f^2（三组解）
则 p^6 = a^2+b^2 = c^2+d^2 = e^2+f^2（三组解）

如此类推。

当年，费尔马发现小定理时，他激动的说：“我沐浴在阳光中！”

蔡家雄

论 1/n 具有最大循环节的充要条件：

设 n = 2^a0*p1^a1*p2^a2*p3^a3*......*ps^as + 1，（p 表示奇素数）

设 d 表示为 (n - 1) / 2 的因子，

则 1/n 具有最大循环节的充要条件：

(i)   n 是奇素数；

(ii)  对于任一小于 (n - 1) / 2 的因子d，(10^d+1) 都不能被 n 整除；

(iii) 当且仅当 d = (n - 1) / 2 时，(10^d+1) 能被 n 整除。

蔡家雄

论 1/p 具有最大循环节长的充要条件

设素数 p=2^k*u*v*w+1，

其中 u, v 是 p -1 的素因子，

若 10^[(p -1)/2]  mod  p ≠ 1，

且 10^[(p -1)/u]  mod  p ≠ 1，

且 10^[(p -1)/v]  mod  p ≠ 1，

则 1/p 具有最大循环节长度。

蔡家雄

费马小定理3

若 4x+1= p 为素数，
则 p^1 = a^2+b^2 （一组解）
则 p^2 = a^2+b^2 （一组解）
则 p^3 = a^2+b^2 = c^2+d^2（两组解）
则 p^4 = a^2+b^2 = c^2+d^2（两组解）
则 p^5 = a^2+b^2 = c^2+d^2 = e^2+f^2（三组解）
则 p^6 = a^2+b^2 = c^2+d^2 = e^2+f^2（三组解）

s = 0;
For[n = 1; x = 1, x <= 24, x++, If[PrimeQ[4 x + 1], s = s + 1;
  Print[s, "-----", 4 x + 1, "-----",
   PowersRepresentations[(4 x + 1)^n, 2, 2]]]]

1-----5-----{{1,2}}

2-----13-----{{2,3}}

3-----17-----{{1,4}}

4-----29-----{{2,5}}

5-----37-----{{1,6}}

6-----41-----{{4,5}}

7-----53-----{{2,7}}

8-----61-----{{5,6}}

9-----73-----{{3,8}}

10-----89-----{{5,8}}

11-----97-----{{4,9}}

蔡家雄

费马小定理3

若 4x+1= p 为素数，
则 p^1 = a^2+b^2 （一组解）
则 p^2 = a^2+b^2 （一组解）
则 p^3 = a^2+b^2 = c^2+d^2（两组解）
则 p^4 = a^2+b^2 = c^2+d^2（两组解）
则 p^5 = a^2+b^2 = c^2+d^2 = e^2+f^2（三组解）
则 p^6 = a^2+b^2 = c^2+d^2 = e^2+f^2（三组解）

s = 0;
For[n = 2; x = 1, x <= 24, x++, If[PrimeQ[4 x + 1], s = s + 1;
  Print[s, "-----", 4 x + 1, "-----",
   PowersRepresentations[(4 x + 1)^n, 2, 2]]]]

1-----5-----{{0,5},{3,4}}

2-----13-----{{0,13},{5,12}}

3-----17-----{{0,17},{8,15}}

4-----29-----{{0,29},{20,21}}

5-----37-----{{0,37},{12,35}}

6-----41-----{{0,41},{9,40}}

7-----53-----{{0,53},{28,45}}

8-----61-----{{0,61},{11,60}}

9-----73-----{{0,73},{48,55}}

10-----89-----{{0,89},{39,80}}

11-----97-----{{0,97},{65,72}}

蔡家雄

费马小定理3

若 4x+1= p 为素数，
则 p^1 = a^2+b^2 （一组解）
则 p^2 = a^2+b^2 （一组解）
则 p^3 = a^2+b^2 = c^2+d^2（两组解）
则 p^4 = a^2+b^2 = c^2+d^2（两组解）
则 p^5 = a^2+b^2 = c^2+d^2 = e^2+f^2（三组解）
则 p^6 = a^2+b^2 = c^2+d^2 = e^2+f^2（三组解）

s = 0;
For[n = 3; x = 1, x <= 24, x++, If[PrimeQ[4 x + 1], s = s + 1;
  Print[s, "-----", 4 x + 1, "-----",
   PowersRepresentations[(4 x + 1)^n, 2, 2]]]]

1-----5-----{{2,11},{5,10}}

2-----13-----{{9,46},{26,39}}

3-----17-----{{17,68},{47,52}}

4-----29-----{{58,145},{65,142}}

5-----37-----{{37,222},{107,198}}

6-----41-----{{115,236},{164,205}}

7-----53-----{{106,371},{259,286}}

8-----61-----{{234,415},{305,366}}

9-----73-----{{219,584},{296,549}}

10-----89-----{{88,835},{445,712}}

11-----97-----{{297,908},{388,873}}

蔡家雄

设 1/n 的循环节长度是偶数2d,

有 10^(2d) - 1 能被 n 整除,

则 (10^d - 1) * (10^d+1) 能被 n 整除,

显然，(10^d - 1) 不被 n 整除。

假若 (10^d - 1) 能被 n 整除，则 1/n 的循环节长度是d，不是2d，与题设矛盾。

推出：

若 1/n 的循环节长度是偶数2d,

且 (10^d +1) 能被 n 整除，

则 1/n 是 对折和 互补为 9 的循环小数。

蔡家雄

若素数 p>=5 ,
则 (4^p - 1)/3 一定是费尔马伪素.

费马伪素的定义：
若合数n满足：
2^n   mod   n = 2,
则合数n称为费马伪素。

2^[(4^p - 1)/3]  mod  [(4^p - 1)/3] = 2

若素数 p>=5 ,则 (4^p - 1)/3 一定是费尔马伪素.

(4^5 - 1)/3 = 341
(4^7 - 1)/3 = 5461
(4^11 - 1)/3 =1398101
(4^13 - 1)/3 =22369621

若素数 p>=5 ,则 (4^p - 1)/3 是 形式化的 费马伪素.

c1=1*6^1+1
c2=2*6^1+1
c3=3*6^1+1
c1*c2*c3是卡迈克尔数

c4=1*6^2+1
c5=2*6^2+1
c6=3*6^2+1
c4*c5*c6是卡迈克尔数
且 c1*c2*c3*c4*c5*c6 是卡迈克尔数

c7=1*6^4+1
c8=2*6^4+1
c9=3*6^4+1
c7*c8*c9是卡迈克尔数

问题：是否存在三个卡迈克尔数的乘积仍是卡迈克尔数 吗？

蔡家雄

费马小定理3

若 4x+1= p 为素数，
则 p^1 = a^2+b^2 （一组解）
则 p^2 = a^2+b^2 （一组解）
则 p^3 = a^2+b^2 = c^2+d^2（两组解）
则 p^4 = a^2+b^2 = c^2+d^2（两组解）
则 p^5 = a^2+b^2 = c^2+d^2 = e^2+f^2（三组解）
则 p^6 = a^2+b^2 = c^2+d^2 = e^2+f^2（三组解）

s = 0;
For[n = 4; x = 1, x <= 24, x++, If[PrimeQ[4 x + 1], s = s + 1;
  Print[s, "-----", 4 x + 1, "-----",
   PowersRepresentations[(4 x + 1)^n, 2, 2]]]]

1-----5-----{{0,25},{7,24},{15,20}}

2-----13-----{{0,169},{65,156},{119,120}}

3-----17-----{{0,289},{136,255},{161,240}}

4-----29-----{{0,841},{41,840},{580,609}}

5-----37-----{{0,1369},{444,1295},{840,1081}}

6-----41-----{{0,1681},{369,1640},{720,1519}}

7-----53-----{{0,2809},{1241,2520},{1484,2385}}

8-----61-----{{0,3721},{671,3660},{1320,3479}}

9-----73-----{{0,5329},{721,5280},{3504,4015}}

10-----89-----{{0,7921},{3471,7120},{4879,6240}}

11-----97-----{{0,9409},{959,9360},{6305,6984}}

蔡家雄

定义：模素数p的阶e

若 a^e   mod   p = 1，（e 为最小指数，p是奇素数）

则 称e为：已a为底，模素数p的阶。

当阶数 e = p - 1 时，

则 称a为模素数p的原根。


余数个数是 (p - 1) 的因子，余数之和是p的 d 倍。
当阶数 e 是偶数 时，d = e /2,
当阶数 e 是奇数 时，却没有 d 的统一计算公式，

若 a是素数p的原根，则 a+p*n 也是素数p的(广义)原根。
编程验证举例：（a=10,  p=29）
s = 0;
For[a = 10; p = 29; n = 1, n <= 30, n++,
If[MultiplicativeOrder[a + p*n, p] == p - 1, s = s + 1;
  Print[s, "-----", a + p*n, "-----",
   MultiplicativeOrder[a + p*n, p] == p - 1]]]

若 a是4k+1型素数p的原根，则 (p -a) 也是素数p的原根。（原根的互补性）

此贴 与 费马小定理1 相关。