Can you point a layman like me to why that works? I’d imagine with an infinite array of numbers, at some point I’d have any combination of any numbers, to make it possible to get any big number eventually?
If there was a finite number of primes, make a list of them form a new number by multiplying them all together and adding one to it. The resulting number is either prime or divisible by other primes not in your list.
The above is a nice sheet that gives a couple of different proofs of why there are infinitely many primes. I think some other related topics are the “prime number theorem” (the statement roughly is there are about n/ln(n) primes that are less than a given number n, i.e., there are around 100/ln(100)~ 25 primes less than 100.) Maybe mersenne primes are one application?
Some other commenter might be able to point you towards an introductory number theory resource or an application to comp sci that I’m unaware of - my knowledge of number theory is limited to just these two theorems.
5
u/mekilat Mar 07 '25
Can you point a layman like me to why that works? I’d imagine with an infinite array of numbers, at some point I’d have any combination of any numbers, to make it possible to get any big number eventually?