به نام خدا
می‌دانیم که قضیهٔ اساسی حساب نقش مهمی در نظریهٔ اعداد دارد و مربوط به تجزیهٔ اعداد صحیح به عوامل اول است. اثبات‌های مختلفی برای این قضیه وجود دارد، اما تقریباً همهٔ آن‌ها حداقل در بخشی از خود، از استقرای ریاضی استفاده می‌کنند. اما این قضیه بدون استفاده از استقرا نیز قابل اثبات است. قبل از اثبات این قضیه، لازم است که ابتدا قضیهٔ زیر را اثبات کنیم:
هر عدد طبیعی بزرگ‌تر از ۱، حداقل یک مقسوم‌علیه اول دارد.
اثبات:
آن عدد طبیعی بزرگ‌تر از ۱ را $n$ می‌نامیم و کوچک‌ترین مقسوم‌علیه $n$ را $a$ می‌نامیم (که $a>1$). اگر ثابت کنیم که $a$ عددی اول است، اثبات به پایان می‌رسد. از برهان خلف استفاده می‌کنیم و فرض می‌کنیم که $a$ عددی مرکب باشد. اگر $a$ عددی مرکب باشد، آنگاه بر یک عدد طبیعی بزرگ‌تر از ۱ و کوچک‌تر از خودش بخش‌پذیر است. آن عدد را $\alpha$ می‌نامیم. پس $\alpha\mid a$ (که $1< \alpha< a$). در نتیجه $\alpha\mid n$. که این با فرض کوچک‌ترین مقسوم‌علیه بودن $a$، در تناقض است؛ بنابراین فرض خلف باطل بوده و در نتیجه $a$ عددی اول است. $\blacksquare$
حالا می‌رویم سراغ اثبات قضیهٔ اساسی حساب. در واقع قضیهٔ اساسی حساب، بیان می‌کند که:
هر عدد طبیعی بزرگ‌تر از ۱، به‌شکل ضرب اعداد اول قابل نوشتن است.
اثبات:
آن عدد طبیعی بزرگ‌تر از ۱ را $n$ می‌نامیم و چون اثبات کردیم که هر عدد طبیعی بزرگ‌تر از ۱، حداقل یک مقسوم‌علیه اول دارد، پس $n$ نیز باید یک مقسوم‌علیه داشته باشد. آن را $p_1$ می‌نامیم. اگر $n=p_1$، آنگاه یعنی $n$ عددی اول است و حکم اثبات می‌شود. اما اگر $n$ عددی مرکب باشد، آنگاه $n>p_1$. در نتیجه یک عدد $r_1$-ی وجود دارد به‌طوری که $n=p_1r_1$. اگر $r_1$ عددی اول باشد، حکم اثبات می‌شود. اما اگر مرکب باشد، یک مقسوم‌علیه اول $p_2$ کوچک‌تر از خودش دارد. به‌طوری که $r_1=p_2r_2$. پس: $n=p_1p_2r_2$. اگر $r_2$ اول باشد، حکم اثبات می‌شود. اما اگر مرکب باشد، آنگاه یک مقسوم‌علیه اول $p_3$ کوچک‌تر از خودش دارد. به‌طوری که $r_2=p_3r_3$. پس: $n=p_1p_2p_3r_3$. اگر $r_3$ اول باشد، حکم اثبات می‌شود و اگر مرکب باشد، آنقدر الگوریتم فوق را ادامه می‌دهیم که یک دنباله از اعداد صحیح به‌صورت زیر به‌دست آید:
$$r_1>r_2>r_3>... \geq 1$$
پس از انجام چند مرحلهٔ متناهی به $r_{k+1}=1$ خواهیم رسید و $n=p_1p_2\cdots p_k$. $\blacksquare$
