Hva er resten av p12 ^ (p-1), når p er prime?

Svar:

Resten er lik #0# når # P # er enten #2# eller #3#, og det er lik #1# for alle andre primære tall.

Forklaring:

Først av alt kan dette problemet omdannes til å finne verdien av # 12 ^ (p-1) mod p # hvor # P # er et førsteklasses nummer.

For å løse dette problemet må du kjenne Eulers teoremåte. Euler's Theorem sier det #a ^ { varphi (n)} - = 1 mod n # for alle heltall #en# og # N # Det er coprime (de deler ikke noen faktorer). Du lurer kanskje på hva # varphi (n) # er. Dette er faktisk en funksjon kjent som totient funksjonen. Det er definert til å være lik antall heltall # <= N # slik at de heltallene er kopierte til # N #. Husk at nummeret #1# regnes som coprime til alle heltall.

Nå som vi kjenner Euler's Theorem, kan vi gå om å løse dette problemet.

Legg merke til at alle primater annet enn #2# og #3# er coprime med #12#. La oss legge til side 2 og 3 for senere og fokusere på resten av primene. Siden de andre primene er coprime til 12, kan vi bruke Euler's Theorem til dem:

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

Siden # P # er et førsteklasses nummer, # Varphi (p) = p-1 #. Dette gir mening fordi hvert nummer mindre enn et hovednummer vil være coprime med det.

Derfor har vi nå # 12 ^ {p-1} - = 1 mod p #

Ovennevnte uttrykk kan oversettes til # 12 ^ {p-1} # delt med # P # har en gjenværende del av #1#.

Nå må vi bare regne med #2# og #3#, som som du sa tidligere, hadde begge remainders av #0#.

Derfor har vi helt klart bevist det # 12 ^ {p-1} # delt med # P # hvor # P # er et primært tall har en gjenværende del av #0# når p er heller #2# eller #3# og har en gjenværende del av #1# ellers.