نه منظورش این نبوده‌است که فرض کنید $M$ اول باشد. فرض خلف را روی همان تعداد عددهای اول به شکل $4k+3$ می‌گیریم. در واقع از ایدهٔ اثبات اقلیدس برای نامتناهی بودن اعداد اول باید استفاده کنید. اثبات اقلیدس به این شکل بود که فرض کنید تعداد عددهای اول متناهی باشند پس می‌توانم تمام آنها را داشته‌باشم به شکل ${p_1,\cdots,p_n}$. آنگاه بیاییم عدد $M=p_1p_2\cdots p_n+1$ را نگاه کنیم. فرضی روی اول یا مرکب بودن آن نمی‌کنیم، صرفا یک ابزار است و معرفی‌اش کرده‌ایم. چون یک عدد اول، بزرگتر یا مساوی ۲ است پس بزرگتر اکید از یک است. پس $p_1\cdots p_n+1>p_i+1>p_i$ به ازای هر $1\leq i\leq n$. در نتیجه $M$ هیچ یک از عددهای اول نیست پس اگر اول نباشد باید مرکب باشد. یک عدد مرکب را می‌توان به حاصلضرب دو عدد کوچکتر نوشت و این عددها را نیز در صورت اول نبودن می‌توان خُردتر کرد و چون هر دفعه اکیدا کوچکتر از عددهای پیشین می‌شوند و مجموعهٔ اعداد طبیعی خوش‌ترتیب است (یعنی هر زیرمجموعهٔ ناتهی‌اش دارای کوچکترین عضو است) پس باید پس از متناهی مرتبه تکرار تجزیه، سرانجام به یک عدد اول که عدد اصلی‌مان را بشمارد برسیم. پس باید یک $p_i$ای باشد که $M$ را بشمارد اما در اینصورت چون $p_i$ هم $M$ و هم $p_1\cdots p_i\cdots p_n$ را می‌شمارد پس ترکیب‌های خطی‌شان، از جمله تفاضلشان را نیز می‌شمارد ولی تفاضل این دو عدد یک است! تنها عدد طبیعی که یک را می‌شمارد خود یک است و عددهای اول بزرگتر یا مساوی دو هستند پس تناقض رسیدیم. یعنی اگر فرض کنیم عددهای اول متناهی هستند آنگاه یک عدد بوجود می‌آید که نه اول است و نه مرکب! که چنین چیزی در منطق دو ارزشی نمی‌تواند روی دهد پس فرض خلفمان باطل و از آنجا تعداد عددهای اول نمی‌تواند متناهی باشد.
در نظریهٔ اعداد عددها یا تابع‌های کمکی زیادی که در انگلیسی اصطلاح auxiliary number یا auxiliary function گفته می‌شوند (همان عدد کمکی یا تابع کمکی) معرفی و استفاده می‌شوند. به ویژه اگر وارد نظریهٔ اعداد متعالی شوید.
اکنون همان مسیر اقلیدس را پیش می‌گیریم. فرض کنید تعداد عددهای اول که به شکل $4k+3$ هستند متناهی باشد پس اگر بزرگترین آنها را $n$اُمین عدد اول باشد آنگاه همهٔ عددهای اول به شکل $4k+3$ در میان اعضای مجموعهٔ ${p_1,\cdots,p_n}$ قرار خواهند گرفت. توجه کنید که نمی‌گوئيم همهٔ اعضای این مجموعه به شکل $4k+3$ نوشته می‌شوند بلکه می‌گوئیم همهٔ اول‌های به آن شکل در این مجموعه قرار دارند و اینکه هر عدد اول بیرون این مجموعه به این شکل نخواهد بود، چون ۷ یکی از اعضای این مجموعه است و ۲ کوچکتر از ۷ است پس تنها شکلی که برای عددهای اول بیرون این مجموعه نسبت به باقیمانده‌اش بر ۴ ممکن است، شکل $4k+1$ است.
اینک فرصت معرفی موجود عجیب و غریب کمکی‌مان است. عدد کمکی روبرو را زیر نظر می‌گیریم $M=4p_1\cdots p_n-1$. چون عددهای اول بزرگتر اکید از یک هستند، برای هر $1\leq i\leq n$ داریم $M>4p_i-1>3p_i>p_i$. پس $M$ هیچ عدد اولی در مجموعه‌مان نیست و بعلاوه هیچ عدد اولی بیرون آن مجموعه به شکل $4k+3$ نمی‌تواند باشد! پس تا اینجا $M$ عددی اول نیست.
اگر $M$ مرکب باشد. تجزیهٔ $M$ به عددهای اول را بنویسید، بفرض $M=q_1^{a_1}\cdots q_m^{a_m}$. اگر عدد اولی از مجموعهٔ بالایمان در تجزیهٔ $M$ ظاهر شود آنگاه یعنی $M$ را می‌شمارد ولی از طرف دیگر آن عدد $4p_1\cdots p_n$ را نیز می‌شمارد و در نتیجه تفاضل آن دو یعنی $-1$ را می‌شمارد که تنها عدد طبیعی ممکن شمارندهٔ $-1$، عدد یک است و تناقض می‌شود. پس همهٔ $q_i$ها به شکل $4k+1$ هستند. پس $M$ حاصلضرب تعداد متناهی عدد به شکل $4k+1$ است (توان نیز ضرب عدد در خودش است) و می‌دانیم که حاصلضرب دو عدد به این شکل (و در نتیجه حاصلضرب متناهی)، دوباره عددی به همین شکل می‌شود و نه به شکل $4k+3$ که باز تناقض می‌شود. چون دو حالت برای این $q_i$ بیشتر نیست و هر دو تناقض می‌دهند پس اصلا این تجزیه مشکل دارد و در نتیجه مرکب بودن $M$ مشکل دارد و چون تنها دو حالت اول و یا مرکب بودن را برای $M$ داریم ($M$ یک نیست چون از چند عدد اول برای نمونه ۷ بزرگتر است)، پس با فرض متناهی بودن عددهای اول به شکل $4k+3$ با عدد طبیعی بزرگتر از یک روبرو می‌شویم که نه اول و نه مرکب است! پس فرض خلف باطل و از آنجا تعداد این عدد اول‌ها نمی‌تواند متناهی باشد.
توجه کنید که همه چیز استفاده شده‌است و دور-ریزی نداشته‌ایم! حتی نحوهٔ تعریف $M$ پر از نکته بوده‌است، برای نمونه اگر عدد $4p_1\cdots p_n+3$ را هم در نظر می‌گرفتیم به شکل $4k+3$ بود ولی هنگامی که تجزیه $M$ را در حالت مرکب بودن بررسی می‌کردیم، بخشی که احتمال بودن $p_i$ ها در بین $q_j$ ها نگاه می‌کردیم، به اینجا می‌رسیدیم که $p_i$ باید ۳ را بشمارد که در حقیقت ۳ عضو مجموعهٔ متناهی $p_i$ها است و نمی‌توانستیم نتیجهٔ مطلوب را بگیریم.
