!قضیه
هر عدد صحیح n>1 را می‌توان (صرفنظر از ترتیب عوامل) فقط به یک طریق بصورت حاصل‌ ضربی از عوامل اول نمایش داد. برای اثبات صحت ادعای فوق از ((استقرای ریاضی|استقرا)) روی n استفاده می‌کنیم. قضیه برای n=2 درست است. پس فرض کنیم برای هر عدد صحیح بزرگتر از 1 و کوچکتر از n درست باشد. ثابت می کنیم قضیه برای n نیز درست است اگر n اول باشد، چیزی برای اثبات وجود ندارد. پس فرض کنیم n مرکب بوده و n دو تجزیه ، مثلا (*) {TEX()} {n=p_1 p_2... p_5=q_1 q_2...q_t} {TEX} داشته باشد، می‌خواهیم نشان دهیم S=t و هر p مساوی qای است.

چون {TEX()} {p_1} {TEX} حاصل‌ضرب {TEX()} {q_1 q_2 ...q_t} {TEX} را عاد می‌کند. باید دست کم یکی از عامل‌ها را عاد کند. {TEX()} {q_1 q_2 ...q_t} {TEX} را طوری اندیس‌گذاری می‌کنیم که {TEX()} {p_1|q_1} {TEX}. در اینصورت {TEX()} {p_1=q_1} {TEX} ، زیرا {TEX()} ‌{p_1} {TEX} و {TEX()} ‌{q_1} {TEX} هر دو اولند. در عبارت (*) می‌توان با حذف {TEX()} ‌{p_1} {TEX} از طرفین بدست آورد. {TEX()} {\frac{n}{p_1}=p_2... p_5=q_2...q_t} {TEX}
هرگاه S>1 یا t>1 ، آنگاه {TEX()} {1< \frac{n}{p_1} !!تذکر
در تجزیه عدد صحیح n ، عدد اول خاصی p ممکن است بیش از یک بار بیاید هرگاه عوامل اول متمایز n ، {TEX()} {p_1 ,...,p_r} {TEX} بوده و {TEX()} {p_i} {TEX} به عنوان یک عامل ، {TEX()} {a_i} {TEX} بار بیاید. می‌توانی بنویسیم:


{TEX()} {n=p_1 ^a_1 ... p_r ^a_r} {TEX} یا مختصرتر {TEX()} {n=\prod_{i=1}^r p_i ^a_i} {TEX}. این تجزیه n به ((عوامل اول)) می‌نامند. همچنین ، می‌توان 1 را با اختصار هر نمای {TEX()} {a_i} {TEX} مساوی 0 به اینصورت بیان کرد:
!!قضیه
هرگاه {TEX()} {n=\prod_{i=1}^r p_i ^a_i} {TEX} ، که در آن به ازای i=1,2,...,r ، {TEX()} {0 \le c_i \le a_i} {TEX}


*هرگاه دو عدد صحیح و مثبت b,a دارای تجزیه‌های {TEX()} {b=\prod_{i=1}^\infty p_i ^b_i} {TEX} {TEX()} {a=\prod_{i=1}^\infty p_i ^a_i} {TEX}
باشند، آنگاه بمعم آنها تجزیه{TEX()} {(a,b)=\prod_{i=1}^\infty p_i ^c_i} {TEX} را دارد که در آن هر {TEX()} {c_i} {TEX} مساوی {TEX()} {min { a_i,b_i }} {TEX} ، یعنی کوچکترین {TEX()} {b_i , a_i} {TEX} است.
!الگوریتم اقلیدس
طبق نکته فوق اگر تجزیه به عوامل اول b,a معلوم باشند. یک روش عملی برای محاسبه {TEX()} {(a,b)} {TEX} بمعم بدست می‌دهد. اما ممکن است در تجزیه به عوامل اول محاسبات زیادی لازم باشد. فرآیند مفیدی وجود دارد بنام ((الگوریتم اقلیدس)) ، که محتاج به تجزیه b,a نیست. این فرآیند بر تقسیمات متوالی استوار است و در آن از مطلب زیر استفاده می‌شود:
!!الگوریتم تقسیم
به ازای اعداد صحیح b,a که b>0 جفت منحصر به فردی از اعداد صحیح مانند r,q وجود دارد که بطوری که a=bq+r که در آن {TEX()} {0 \le r \le b} {TEX} بعلاوه r=0 اگر و فقط اگر b|a.
!!تذکر
می‌گوئیم q خارح قسمت و r باقی‌مانده در تقسیم a به b می‌باشند.
!!الگوریتم اقلیدسی
فرض کنیم اعداد صحیح و مثبت b,a داده شده باشند که b عاد نمی‌کند a را. همچنین {TEX()} {r_1=b} {TEX} {TEX()} {r_0=a} {TEX} ، و الگوریتم تقسیم را متوالیا بکار بریم تا مجموعه باقی‌مانده‌های {TEX()} {r_2,r_3,...,r_n,r_n+1} {TEX} بدست آید که بترتیب با روابط زیر تعریف می‌شوند:



::{TEX()} {r_0 = r_1 q_1 + r_2 0 ::{TEX()} {r_1 = r_2 q_2 + r_3 0 ::...::
::...::
::...::
::{TEX()} {r_n-2 = r_n-1 q_n-1 + r_n 0 ::{TEX()} {r_n - 1 = r_n q_n + r_n+1 r_n + 1=0} {TEX}::

در اینصورت ، آخرین باقی‌مانده ناصفر در این فرآیند {TEX()} {( a,b )} {TEX} است یعنی b,a.
!مباحث مرتبط با عنوان
*((اعداد اول))
*((استقرای ریاضی))
*((الگوریتم اقلیدس))
*((الگوریتم تقسیم))
*((قضایای نظریه اعداد))
*((نظریه اعداد))
*((نظریه همنهشتی))