Wat is de rest van p 12 ^ (p-1), wanneer p prime is?

Antwoord:

De rest is gelijk aan #0# wanneer # P # is een van beide #2# of #3#en het is gelijk aan #1# voor alle andere priemgetallen.

Uitleg:

Allereerst kan dit probleem worden herwerkt als het vinden van de waarde van # 12 ^ (p-1) mod p # waar # P # is een priemgetal.

Om dit probleem op te lossen, moet u de stelling van Euler kennen. Euler's stelling stelt dat #a ^ { varphi (n)} - = 1 mod n # voor alle gehele getallen #een# en # N # dat zijn coprime (ze delen geen factoren). Je vraagt je misschien af wat # varphi (n) # is. Dit is eigenlijk een functie die bekend staat als de totiënt-functie. Het is gedefinieerd als gelijk aan het aantal gehele getallen # <= N # zodanig dat die gehele getallen coprime zijn # N #. Houd er rekening mee dat het nummer #1# wordt beschouwd als coprime voor alle gehele getallen.

Nu we de stelling van Euler kennen, kunnen we dit probleem oplossen.

Merk op dat alle prime-lenzen anders dan #2# en #3# zijn coprime met #12#. Laten we 2 en 3 opzij zetten voor later en ons concentreren op de rest van de prime-lenzen. Aangezien die andere prime-lenzen coprime tot 12 zijn, kunnen we de stelling van Euler op hen toepassen:

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

Sinds # P # is een priemgetal, # Varphi (p) = p-1 #. Dit is logisch omdat elk getal kleiner dan een priemgetal daarmee in overeenstemming is.

Daarom hebben we nu # 12 ^ {p-1} - = 1 mod p #

De bovenstaande uitdrukking kan worden vertaald naar # 12 ^ {p-1} # gedeeld door # P # heeft een restant van #1#.

Nu moeten we alleen rekenschap afleggen #2# en #3#, zoals jullie eerder zeiden, beide hadden restanten van #0#.

Daarom hebben we dat allemaal bewezen # 12 ^ {p-1} # gedeeld door # P # waar # P # is een priemgetal heeft een rest van #0# wanneer p een van beide is #2# of #3# en heeft een rest van #1# anders.