Euklids bevis

[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.

[DennisChristensen]

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.