可以用反證法證明質數是無窮多的！假設有最大的質數為p，則p!十1必為合數，必有質因子，但顯然p!十1不能被最大質數p整除，也不能被任何小於P的質數整除，故p!十1沒有質因子，即p!十1為質數，這與假設相矛盾！所以，質數是沒有最大的！！

這個問題（素數無窮多）在大約2300年前已經被歐幾里得證明，記錄在他的“幾何原本”下卷。

歐幾里得的證明和之前亞里士多德總結的√2為無理數的證明如出一轍，都是反證法。應該也是我們小學奧數的必學經典。

反證：假設素數有限，共n個，分別為 P₁，P₂，P₃，… Pₙ。則構造自然數 P=P₁*P₂*P₃*…*Pₙ+1，顯然P不能被已知的所有n個素數整除（都餘1），所以P也是素數，且＞所有已知素數。矛盾！

質數又叫素數，指的是在大於1的自然數中，只能被1和其自身整除的數。如2只能被1和2整除，2是質數；6能夠被1、2、3、6整除，故6不是質數。對質數的研究屬於數論中的工作，在至少兩千多年前就已經展開。直到現在，還有很多關於質數的問題沒有得到解決。

哥德巴赫猜想就是一個關於質數的很有名的問題，這個猜想的表述是：任何一個大於2的偶數都可以寫成兩個質數之和的形式。哥德巴赫猜想自提出到現在已將近300年，無人能證明或證偽。

尋找哪些數是質數，在2000多年前用的是篩法，相傳是那位測量出地球半徑的埃拉托色尼發明的。方法是在一堆自然數中，先將除了2之外的2的倍數劃掉，再將3的倍數劃掉，依次再將4、5、6等數的倍數劃掉，最後得到的就是質數。不論是在當時還是現在，很難確定一個很大的數到底是不是質數。假若質數是有限個，那麼哥德巴赫猜想就不會存在。不過在兩千多年前的時候，歐幾里得就證明了質數又無數個。

歐幾里得的證明方法很簡單也很巧妙，假設質數是有限個，那麼把所有的質數相乘再加上1，得到的數不會被任何質數整除，這樣得到的這個數必然也是質數。這就與前面的假設相矛盾，故假設的質數是有限個不成立，質數有無數個。

在網路通訊協定上有一種加密方法叫RSA演演算法，將兩個很大的質數相乘後給出結果。除非有人事先知道其中一個質數或兩個質數是什麼，否則透過暴力破解需要花費很長的時間才能給出答案。這就是質數在加密上的應用。這也促使人類去進一步發現更大的質數。每次新發現最大的質數都能夠是業界的重大事件。2017年發現的最大質數還被專門印成了一本書，整本書上印著的就是那個有2233多萬位的質數。就這樣一本書居然還賣得非常好，在大型購物網站上海一度售罄。