Care este restul p12 ^ (p-1), atunci când p este prime?

Răspuns:

Restul este egal cu #0# cand # P # este fie #2# sau #3#, și este egal cu #1# pentru toate celelalte prime numere.

Explicaţie:

În primul rând, această problemă poate fi reluată ca fiind necesară găsirea valorii # 12 ^ (p-1) mod p # Unde # P # este un număr prime.

Pentru a rezolva această problemă trebuie să cunoașteți teorema lui Euler. Teorema lui Euler afirmă asta #a ^ {varphi (n)} - = 1 mod n # pentru orice număr întreg #A# și # N # care sunt coprime (Ei nu împărtășesc nici un factor). S-ar putea să te întrebi ce # varphi (n) # este. Aceasta este de fapt o funcție cunoscută sub numele de funcția totient. Este definit ca fiind egal cu numărul de numere întregi # <= N # astfel încât acei întregi sunt coprime # N #. Rețineți că numărul #1# este considerat coprim la toate numerele întregi.

Acum, când cunoaștem Teorema lui Euler, putem rezolva această problemă.

Rețineți că toate primele, altele decât #2# și #3# sunt coprime cu #12#. Să lăsăm la o parte 2 și 3 pentru mai târziu și să ne concentrăm asupra restului primelor. Deoarece celelalte prime sunt coprime la 12, putem aplica teorema lui Euler pentru ei:

# 12 ^ {varphi (p)} - = 1 mod p #

De cand # P # este un număr prime, # Varphi (p) = p-1 #. Acest lucru are sens deoarece fiecare număr mai mic decât un număr prime va fi coprim cu el.

Deci, acum avem # 12 ^ {p-1} - = 1 mod p #

Expresia de mai sus poate fi tradusă la # 12 ^ {p-1} # impartit de # P # are un rest de #1#.

Acum trebuie doar să ținem cont #2# și #3#, care, după cum ați spus mai devreme, amândoi aveau resturi #0#.

Prin urmare, cu toții am dovedit acest lucru # 12 ^ {p-1} # impartit de # P # Unde # P # este un număr prime are un rest de #0# când p este fie #2# sau #3# și are un rest de #1# in caz contrar.