Testul Fermat

Testul lui Fermat este un test de primărie bazat pe mica teoremă a lui Fermat . Este unul dintre primele teste de primalitate găsite și, ca și celelalte teste utilizate în mod normal, își propune să testeze nu dacă un număr întreg pozitiv este prim, ci dacă un număr dat nu este prim. De fapt, din teoremă știm asta

de sine

\exists ~a\in \mathbb {Z}

{\ displaystyle \ există ~ a \ in \ mathbb {Z}}

{\ displaystyle \ există ~ a \ in \ mathbb {Z}}

, astfel încât să nu fie valid

a^{n}\equiv a\mod n

{\ displaystyle a ^ {n} \ equiv a \ mod n}

{\ displaystyle a ^ {n} \ equiv a \ mod n}

, atunci n nu este prim.

Nimic nu se poate spune, totuși, în cazul în care această proprietate este verificată pentru unele a , și chiar dacă este verificată de fiecare a : n, în orice caz, nu poate fi primă. Numerele care, pe baza lor, trec testul Fermat se numesc pseudoprime Fermat , în timp ce cei care trec pentru fiecare sunt numite numere Carmichael : cel mai mic dintre ele este 561.

Exemple

Exemplul 1

O primă $p$ ${\ displaystyle p}$ $p$ trece testul pentru fiecare bază: de exemplu, luat p = 7

2^{7}

{\ displaystyle 2 ^ {7}}

{\ displaystyle 2 ^ {7}}

=

2^{1}

{\ displaystyle 2 ^ {1}}

{\ displaystyle 2 ^ {1}}

( după teorema lui Euler ) ≡ 2 (mod 7),

sau, echivalent, $2^{6}$ ${\ displaystyle 2 ^ {6}}$ ${\ displaystyle 2 ^ {6}}$ = $2^{0}$ ${\ displaystyle 2 ^ {0}}$ ${\ displaystyle 2 ^ {0}}$ (pentru Euler) ≡ 1 (mod 7) -

3^{7}

{\ displaystyle 3 ^ {7}}

{\ displaystyle 3 ^ {7}}

=

3^{1}

{\ displaystyle 3 ^ {1}}

{\ displaystyle 3 ^ {1}}

(pentru Euler) ≡ 3 (mod 7),

4^{7}

{\ displaystyle 4 ^ {7}}

{\ displaystyle 4 ^ {7}}

=

4^{1}

{\ displaystyle 4 ^ {1}}

{\ displaystyle 4 ^ {1}}

(pentru Euler) ≡ 4 (mod 7),

5^{7}

{\ displaystyle 5 ^ {7}}

{\ displaystyle 5 ^ {7}}

=

5^{1}

{\ displaystyle 5 ^ {1}}

{\ displaystyle 5 ^ {1}}

(pentru Euler) ≡ 5 (mod 7),

6^{7}

{\ displaystyle 6 ^ {7}}

{\ displaystyle 6 ^ {7}}

=

6^{1}

{\ displaystyle 6 ^ {1}}

{\ displaystyle 6 ^ {1}}

(pentru Euler) ≡ 6 (mod 7).

Exemplul 2

De sine $n$ ${\ displaystyle n}$ $n$ nu este un număr prim, atunci vor exista multe baze (cel puțin jumătate) în care testul dă un rezultat pozitiv: să spunem că $n$ ${\ displaystyle n}$ $n$ este un pseudoprimo în bază $la$ ${\ displaystyle a}$ $la$ . De exemplu, pentru n = 91 avem 91 = 13 * 7 (adică $n$ ${\ displaystyle n}$ $n$ nu este prim). Cu a = 3, totuși, susține că:

3^{90}

{\ displaystyle 3 ^ {90}}

{\ displaystyle 3 ^ {90}}

=

(3^{6})^{15}

{\ displaystyle (3 ^ {6}) ^ {15}}

{\ displaystyle (3 ^ {6}) ^ {15}}

≡ 1 (pentru Euler) (mod 7)

3^{90}

{\ displaystyle 3 ^ {90}}

{\ displaystyle 3 ^ {90}}

=

3^{12*7+6}

{\ displaystyle 3 ^ {12 * 7 + 6}}

{\ displaystyle 3 ^ {12 * 7 + 6}}

≡

3^{6}

{\ displaystyle 3 ^ {6}}

{\ displaystyle 3 ^ {6}}

(pentru Euler) ≡ 27 * 27 ≡ 1 * 1 = 1 (mod 13)

Prin urmare, $3^{90}$ ${\ displaystyle 3 ^ {90}}$ ${\ displaystyle 3 ^ {90}}$ ≡ 1 (formularul 91). Acest lucru nu este adevărat, totuși, cu a = 2. De fapt, vedem că:

2^{90}

{\ displaystyle 2 ^ {90}}

{\ displaystyle 2 ^ {90}}

=

2^{12*7+6}

{\ displaystyle 2 ^ {12 * 7 + 6}}

{\ displaystyle 2 ^ {12 * 7 + 6}}

≡

2^{6}

{\ displaystyle 2 ^ {6}}

{\ displaystyle 2 ^ {6}}

(pentru Euler) ≡

2^{4+2}

{\ displaystyle 2 ^ {4 + 2}}

{\ displaystyle 2 ^ {4 + 2}}

≡ 16 * 4 ≡ 3 * 4 = -1 (mod 13).

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică