🎁 👆🏾 🌷 Teorema de Proth 🚘 ✈️ 👂🏻

História

François Prot (1852-1879) era um fazendeiro autodidata que vivia na aldeia francesa de Vaudevan-Damloux, perto de Verdun. O teorema considerado aqui é um dos quatro resultados que obteve que podem ser usados para testar a simplicidade dos números. Foi publicado no jornal científico francês Comptes rendus de l'Académie des Sciences (Fig. 1) em 1878. Protus provavelmente tinha provas de seus resultados, mas não as apresentou.

Definição

– . , , , . , , – .

– $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 .

– , , uma :

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

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

, , . , .

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

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

. , . , .

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

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

, . , , 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)$ .

– . uma $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)$ uma .

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

, :

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

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

. , , . , , , . .

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

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

, . , 1/2 .

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

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

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

, – , uma , . , . «» . .

N = 9 , . uma . 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} \ não \ equiv1 ~ (\ text {mod} ~ N)$ uma , – .

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

$3 ^ {16} \ equiv1 ~ (\ text {mod} ~ 17)$ –
$3 ^ {8} \ não \ equiv1 ~ (\ text {mod} ~ 17)$ –

, , N = 17 .

Obviamente, o teorema generalizado de Proth é aplicável a um grande número de grupos de números, mas a seleção das variáveis necessárias consome muito tempo. Portanto, na prática, o teorema clássico é usado com muito mais frequência.

Teorema de Proth

História

Definição

More articles: