اعداد اول اعداد طبیعی بزرگتر از یک هستند که به غیر از یک و خودش هیچ مقسوم‌علیه دیگری ندارند. ۲ و ۳ و ۵ و ۷ و … نمونه‌ای از این اعداد هستند. اعداد طبیعی بزرگتر از یک که اول نیستند را مرکب می‌نامند. یک نه اول است نه مرکب.

قضیه ۱: تعداد اعداد اول بی‌نهایت است.

فرض خلف : اعداد اول متناهی است. اعداد اول را در هم ضرب می‌کنیم. حاصل را به علاوه ۱ می‌کنیم. عدد حاصل نسبت به تمام اعداد اول، اول است در نتیجه عامل اول دیگری در آن وجود دارد که خلاف فرض خلف است پس اعداد اول نامتناهی است.

قضیه ۲ (قضیه اساسی حساب): هر عدد طبیعی بزرگ‌تر از ۱ را می‌توان به شکل حاصل‌ضرب اعدادی اول نوشت.

قضیه ۳ (قضیه چبیشف):اگر n عددی طبیعی و بزرگ‌تر از ۳ باشد، حتماً بین n و ۲n عدد اولی وجود دارد.

قضیه ۴ (قضیه اردوش (تعمیم قضیه چبیشف)): برای هر عدد طبیعی k، وجود دارد یک عدد طبیعی مثل N، که برای هر n>N، بین n و 2n حداقل k عدد اول وجود دارد.