🍣 👩🏻 🌞 Teorema Proth 🙊 👈🏻 😢

Cerita

François Prot (1852-1879) adalah seorang petani otodidak yang tinggal di desa Prancis Vaudevan-Damloux dekat Verdun. Teorema yang dipertimbangkan di sini adalah satu dari empat hasil yang dia peroleh yang dapat digunakan untuk menguji kesederhanaan angka. Itu diterbitkan dalam jurnal ilmiah Prancis Comptes rendus de l'Académie des Sciences (Gbr. 1) pada tahun 1878. Protus mungkin memiliki bukti hasil, tapi dia tidak mempresentasikannya.

Definisi

– . , , , . , , – .

– $k \ cdot2 ^ n + 1$ , – . , 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 .

– , , Sebuah :

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

. Sebuah , $x ^ 2 \ equiv a ~ (\ text {mod} ~ m)$ . , , Sebuah .

, , . , .

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

, – sebelas , : $2 ^ 5 = 32 \ equiv-1 ~ (\ text {mod} ~ 11)$ . – sebelas $3 ^ 5 = 243 \ equiv1 ~ (\ text {mod} ~ 11)$ .

. , . , .

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

. n = 7 . , . n-1 , . , . q = 3 . $3> \ sqrt {7} -1 \ approx1.65$ . Sebuah , . a = 2 , $2 ^ {6} \ equiv1 ~ (\ text {mod} ~ 7)$ $2 ^ {(7-1) / 3} -1 = 3$ . , .

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

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

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

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

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

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

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

, :

$a ^ {n-1} = \ kiri (a ^ {(n-1) / 2} \ kanan) ^ 2 \ equiv1 ~ (\ text {mod} ~ n)$ –
$a ^ {(n-1) / q} -1$ –

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

. , , . , , , . .

, . Sebuah , $a \ bukan \ equiv1 ~ (\ text {mod} ~ N)$ . $b = a ^ {(n-1) / 2}$ .

$b \ equiv-1 ~ (\ text {mod} ~ N)$ . , – .
$b \ bukan \ equiv \ pm1 ~ (\ text {mod} ~ N)$ $b ^ 2 \ equiv1 ~ (\ text {mod} ~ N)$ . , , – , ( $b \ pm1, N$ ) .
$b ^ 2 \ bukan \ equiv1 ~ (\ text {mod} ~ N)$ . – .
$b \ equiv1 ~ (\ text {mod} ~ N)$ . .

, . , 1/2 .

, . , Sebuah . , 1,2, ..., N-1 (N-1) / 2 . Sebuah , 1/2 . , – .

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

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

, – , Sebuah , . , . «» . .

N = 9 , . Sebuah . b = 16 . N = 9 . , $16 \ equiv7 \ neq \ pm1 ~ (\ text {mod} ~ 9)$ . . , N = 9 .

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

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

N = r ^ et + 1 , – , – , $e, t \ geq1$ . r ^ e> t . , $a ^ {N-1} \ equiv1 ~ (\ text {mod} ~ N)$ $a ^ {(N-1) / r} \ bukan \ equiv1 ~ (\ text {mod} ~ N)$ Sebuah , – .

. , N = 17 . $N = 17 = 2 ^ 4 \ cdot1 + 1$ . r = 2, ~ e = 4, ~ t = 1 . , . Sebuah . a = 3 . :

$3 ^ {16} \ equiv1 ~ (\ text {mod} ~ 17)$ –
$3 ^ {8} \ bukan \ equiv1 ~ (\ teks {mod} ~ 17)$ –

, , N = 17 .

Tentu saja, teorema umum Proth berlaku untuk sejumlah besar kelompok bilangan, tetapi pemilihan variabel yang diperlukan terlalu memakan waktu. Oleh karena itu, dalam praktiknya, teorema klasik lebih sering digunakan.

Teorema Proth

Cerita

Definisi

More articles: