Svar Före-läsningsuppgift dag 3

Uppgiften gick ut på att utreda om \phi(p) = p-1 är ekvivalent med att p är ett primtal. 

Antag först att p är ett primtal. I så fall är alla talen 1,2,\ldots,p-1 relativa prima med p (dock är inte p relativt prima med p eftersom p > 1) och alltså är \phi(p) = p-1.

För att visa omvändningen, nämligen att \phi(p) = p-1 medför att p är ett primtal, gör vi ett motsägelsebevis. Antag att \phi(p) = p-1 och att p är sammansatt. Det betyder att vi kan skriva p som en produkt av två naturliga tal a och b, där a,b \geq 2. Det innebär att gcd(a,p) = a och gcd(b,p) = b. Alltså är a, b och p *inte* relativt prima med p. Det finns alltså högst p-3 element som är relativt prima med p och det följer att \phi(p) \leq p-3, vilket är en motsägelse. Alltså medför  \phi(p) = p-1 att p är ett primtal.

Senast modifierad: måndag, 11 november 2013, 18:17