إذن الإفتراض خاطئ وحسب البرهان بالخلف فإن مجموعة الأعداد الأولية غير منتهية. البرهان الثاني: ليكن $\displaystyle{\displaylines{n}}$ عدد صحيح طبيعي غير منعدم. لدينا $\displaystyle{\displaylines{n \wedge n+1 = 1}}$ ومنه العدد $\displaystyle{\displaylines{n (n+1)}}$ يقبل على الاقل عددين اوليين مختلفين كقواسم. لدينا $\displaystyle{\displaylines{n (n+1) \wedge n (n+1)+1 = 1}}$ إذن العدد $\displaystyle{\displaylines{n (n+1) (n (n+1)+1)}}$ يقبل على الأقل 3 أعداد أولية مختلفة كقواسم. وهكذا... سوف نحصل على عدد لا نهائي من الأعداد الأولية. البرهان الثالث: نضع $\displaystyle{\displaylines{\forall n \in \mathbb{N} \quad u_n = F_n - 2}}$. حل درس الأعداد الأولية والغير أولية رياضيات صف رابع فصل ثاني - سراج. بحيث $\displaystyle{\displaylines{F_n}}$ عدد فيرما: $\displaystyle{\displaylines{F_n = 2^{2^{n}} + 1}}$ ( راجع أعداد فيرما Nombres de Fermat) لدينا $\displaystyle{\displaylines{u_n = F_0 F_1... F_{n-1}}}$. لدينا $\displaystyle{\displaylines{u_n}}$ يقبل على الاقل $\displaystyle{\displaylines{n}}$ قاسم أولي مختلف, لان الاعداد $\displaystyle{\displaylines{F_i}}$ اولية في ما بينها.
بين بأكثر من طريقة أن مجموعة الأعداد الأولية غير منتهية البرهان الأول: وهو معروف منذ عهد العالم أقليدس اليوناني (350 سنة قبل الميلاد). نرمز للعدد الأولي من الرتبة $\displaystyle{\displaylines{i}}$ بــ $\displaystyle{\displaylines{p_i}}$. لدينا: $\displaystyle{\displaylines{p_1=2, p_2=3, p_3=5, p_4=7...... }}$. طريقة برهان أقليدس تستند إلى أن العدد $\displaystyle{\displaylines{n = p_1 p_2 p_3.... p_r + 1}}$ لا يقبل أي قاسم أولي أصغر من $\displaystyle{\displaylines{p_r}}$. إذا افترضنا ان مجموعة الأعداد الأولية منتهية وليكن $\displaystyle{\displaylines{p_r}}$ أكبر عدد أولي. لدينا: $\displaystyle{\displaylines{n = p_1 p_2 p_3.... p_r + 1}}$ إذا كان $\displaystyle{\displaylines{i \in \{1,..., r\}}}$ لدينا $\displaystyle{\displaylines{n - p_1 p_2... p_i.... p_r = 1}}$. إذن $\displaystyle{\displaylines{n - k p_i = 1}}$ ومنه وحسب مبرهنة Bézout $\displaystyle{\displaylines{\forall i \in \{1,..., r\} \quad n \wedge p_i = 1}}$ إذن $\displaystyle{\displaylines{n}}$ عدد أولي لأنه أولي مع جميع الاعداد الاولية الاصغر منه وهذا تناقض على اعتبار ان $\displaystyle{\displaylines{p_r}}$ هو اكبر عدد اولي ووجدنا $\displaystyle{\displaylines{p_r << n}}$.
إذا" تبدأ الأعداد الأولية بالرقم 2 القابل للقسمة على 1 و على نفسه (2) فقط لا غير. تمييز و تحديد الأعداد الأولية تقوم الاختبارات الأولى التي تحدد ما إذا كان الرقم أوليًا بمحاولة تقسيمه على جميع الأرقام التي لا تتجاوز جذره التربيعي: مثلا" نجرّب قسمة العدد 64 على كل الأرقام دون جذره التربيعي أي دون 8 إذا كان قابلاً للقسمة على واحد منهم ، فهو غير أولي، وإذا لم يكن كذلك، يكون عددا" أوليا". ومع ذلك ، يمكن جعل هذه الطريقة أكثر كفاءة و سهولة: فهي تقترح الكثير من الأقسام غير الضرورية، على سبيل المثال، إذا كان العدد غير قابل للقسمة على 2، فلا فائدة من اختبار ما إذا كان قابلاً للقسمة على 4. في الواقع ، يكفي اختبار قابليتها للقسمة على جميع الأعداد الأولية التي لا تتجاوز جذرها التربيعي. وتكون الطريقة الأكثر كفاءة في بعض الأحيان تتمثل في اختبار قابلية قسمة العدد فقط على أعداد أولية صغيرة في قائمة ثابتة مسبقًا (على سبيل المثال 2 و 3 و 5) ، ثم بكل الأعداد الصحيحة الأقل من الجذر التربيعي للعدد التي لا تقبل القسمة على الأعداد الأولية الصغيرة المختارة. إذا" للتعرف على الأعداد الأولية يجب أن تعرف أولاً معاييرك للقسمة.