Side 1 av 1

Euklids bevis

Lagt inn: 03/12-2018 19:35
av Gjest
Heisann! Jeg jobber med Euklids bevis for at det finnes uendelig mange primtall, men sliter litt med å forstå beviset. Spesifikt så sliter jeg med å forstå n-2*3*5*...*p=1, for hvordan kan man egentlig forvente at en primfaktor q skal være faktor i 1? Tusen takk for svar :) Jeg har forresten matematikk X.

Re: Euklids bevis

Lagt inn: 03/12-2018 21:06
av DennisChristensen
Gjest skrev:Heisann! Jeg jobber med Euklids bevis for at det finnes uendelig mange primtall, men sliter litt med å forstå beviset. Spesifikt så sliter jeg med å forstå n-2*3*5*...*p=1, for hvordan kan man egentlig forvente at en primfaktor q skal være faktor i 1? Tusen takk for svar :) Jeg har forresten matematikk X.
Anta i jakt på en selvmotsigelse at det kun finnes endelig mange primtall, si $p_1, \dots, p_n$. Altså antar vi at alle heltall kan primtallfaktoriseres med disse primtallene. Så definerer vi tallet $N = p_1\times\dots\times p_n + 1$. Da har vi at
$$\begin{align*}N & \equiv 1 \mod p_1 \\ N & \equiv 1 \mod p_2 \\ & \vdots \\ N & \equiv 1 \mod p_n,\end{align*}$$ så $N$ kan ikke faktoriseres med primtallene fra listen vår, hvilket gir den ønskede selvmotsigelsen.