プロスの定理

物語

FrançoisProt(1852-1879)は、ヴェルダン近くのフランスの村Vaudevan-Damlouxに住んでいた独学の農民でした。ここで検討した定理は、彼が得た4つの結果の1つであり、数値の単純さをテストするために使用できます。1878年にフランスの科学雑誌Comptesrendusdel'AcadémiedesSciences(図1)に掲載されました。プロトゥスはおそらく彼の結果の証拠を持っていたが、彼はそれらを提示しなかった。





写真1
写真1

定義

– . , , ,   . , , – .





k \ cdot2 ^ n + 1, k n– . , k <2 ^ n, . , 448 , 7 \ cdot2 ^ 6 + 1, 2 ^ 6> 7.





: 3, 5, 9,13,17, 25, 33… -  A080075.





, , : 3, 5, 13, 17, 41, 97, 113… - A080076.





10223 \ cdot2 ^ {31172165} +1, 9,383,761 . , , 2 ^ n-1. 31 2016    Seventeen or Bust k \ cdot2 ^ n + 1.





, . , (n \ cdot2 ^ n + 1) k = n, (2 ^ {2 ^ n} +1)  –   k = 1.





p – , , a :





a ^ {\ frac {p-1} {2}} \ equiv-1〜(\ text {mod} 〜p)

. a m, x ^ 2 \相当a〜(\ text {mod} 〜m) . , , a m.





, , . , .





m> 2 – . a, m m , a ^ {(p-1)/ 2} \ equiv1〜(\ text {mod} 〜p)     , a ^ {(p-1)/ 2} \ equiv-1〜(\ text {mod} 〜p).





, 2十一, : 2 ^ 5 = 32 \ equiv-1〜(\ text {mod} 〜11). 3十一 3 ^ 5 = 243 \ equiv1〜(\ text {mod} 〜11).





. , . , .





nn-1 q, q> \ sqrt {n} -1. a, a ^ {n-1} \ equiv1〜(\ text {mod} 〜n)   n a ^ {(n-1)/ q} -1 , n – .





. n = 7. , . n-1, 6. , . q = 3. 3> \ sqrt {7} -1 \約1.65 . n a, . a = 2, 2 ^ {6} \ equiv1〜(\ text {mod} 〜7) 7 2 ^ {(7-1)/ 3} -1 = 3 .  , 7





, q 1. , , q  k> 1. : q ^ k> \ sqrt {n} -1.





, n = 17. n-1 = 16  q = 2. , 2> \ sqrt {17} -1 \約3,12 . q = 2 n-1 = 16 k = 4. : 2 ^ 4> \ sqrt {17} -1 \約3,12. , , , , : n = 17 – .





. , a ^ {(p-1)/ 2} \ equiv-1〜(\ text {mod} 〜p).





p – . a a ^ {(p-1)/ 2} \ equiv-1〜(\ text {mod} 〜p). .





, p , a ^ {(p-1)/ 2} \ equiv-1〜(\ text {mod} 〜p).





a ^ {(p-1)/ 2} \ equiv-1〜(\ text {mod} 〜p) a.





n = p = 2 ^ k + 1. q = 2 n-1.





, :





  1. a ^ {n-1} = \左(a ^ {(n-1)/ 2} \右)^ 2 \ equiv1〜(\ text {mod} 〜n)





  2. n a ^ {(n-1)/ q} -1





2 ^ k> \ sqrt {n} -1. n = p . .





. , , . , , , . .





, N . a, a \ not \ equiv1〜(\ text {mod} 〜N). b = a ^ {(n-1)/ 2} N.





:





  1. b \ equiv-1〜(\ text {mod} 〜N). , – .





  2. b \ not \ equiv \ pm1〜(\ text {mod} 〜N) b ^ 2 \ equiv1〜(\ text {mod} 〜N). , , N – , ( b \ pm1、N ) N.





  3. b ^ 2 \ not \ equiv1〜(\ text {mod} 〜N). N –   .





  4. b \ equiv1〜(\ text {mod} 〜N). .





, .  N , 1/2.





, . , a N. , 1,2、...、N-1 N (N-1)/ 2 . a, 1/2. , N – .





. N = 17. a. , a = 2, b = 256. b N. , 256 \ equiv1〜(\ text {mod} 〜17). . , a.





a = 3. b = 6561 6561 \ equiv-1〜(\ text {mod} 〜17). , , N = 17 .





, N – , a, . , . «» . .





N = 9 , . a 2. b = 16. 16 N = 9 7. ,16 \ equiv7 \ neq \ pm1〜(\ text {mod} 〜9). . , N = 9 .





-.   ,    . ,     « », « ».  , , .    .





2008 , , O((k \ log k + \ log N)(\ log N)^ 2).   "Proth.exe", .





.





N N = r ^ et + 1, r – , e t – , e、t \ geq1. r ^ e> t. , a ^ {N-1} \ equiv1〜(\ text {mod} 〜N) a ^ {(N-1)/ r} \ not \ equiv1〜(\ text {mod} 〜N) a, N – .





. , N = 17. N = 17 = 2 ^ 4 \ cdot1 + 1. r = 2、〜e = 4、〜t = 1. , . a. a = 3. :





  1. 3 ^ {16} \ equiv1〜(\ text {mod} 〜17)





  2. 3 ^ {8} \ not \ equiv1〜(\ text {mod} 〜17)





, , N = 17 .





もちろん、プロスの一般化された定理は多数の数のグループに適用できますが、必要な変数の選択には時間がかかりすぎます。したがって、実際には、古典的な定理がはるかに頻繁に使用されます。








All Articles