اعداد اول

[nafise sadeghi]

اعداد اول:

تعریف:
عدد طبیعی P>1 را عدد اول می گویند هرگاه تنها مقسوم علیه های مثبت آن 1 و P باشند. به عبارت دیگر یک عدد طبیعی اول است هرگاه جز یک و خودش بر هیچ عدد دیگری بخش پذیر نباشد.
هر عدد طبیعی مخالف یک که اول نباشد مرکب یا تجزیه پذیر می گوییم.

به عنوان مثال اعداد 2و3و5و7 اول و اعداد 12و18و325 مرکب می باشند.


لازم به ذکر است که عدد یک نه اول و نه مرکب است و تنها عدد اول زوج عدد 2 است.
اگر n عددی مرکب باشد می توان گفت: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/28ab17f250b52b7ed708a6f7d8fe0695.png


نتیجه: اگر P عددی اول . a و b اعدادی طبیعی باشند، در این صورت:

http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/77d3e9cbc901f924790524cfcb091c80.png


برهان:
چون P عددی اول است بنابراین تنها دو مقسوم علیه متمایز دارد. از اینکه P=ab و a<b نتیجه می شود a , b دو مقسوم علیه متمایز P می باشند چون: a|P ,b|P و بنابر تعریف a=1 , b=P خواهد بود.

[nafise sadeghi]

حال به بیان چند قضیه مهم در باره اعداد اول می پردازیم:
قضیه 1) هر عدد صحیح بجز یک و منفی یک دارای حداقل یک مقسوم علیه اول است.
برهان:
فرض می کنیم a عددی صحیح باشد که مخالف یک و منفی یک است. اگر a=0 باشد در این صورت تمامی اعداد صحیح از جمله اعداد اول a را می شمارند و حکم برقرار است. حال فرض می کنیم a مخالف صفر باشد و نشان می دهیم a دارای حداقل یک مقسوم علیه اول است. برای این منظور مجموعه مقسوم علیه های مثبت و بزرگتر از یک a را به این صورت تعریف میکنیم: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/e29d2db3d2acac84834e430512dceb19.png
مجموعه S ناتهی است چرا که: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/061a8e92dc274e6df2759198b3a6172f.png
پس:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/059eef47ad3e0353266c0225235bad04.png. از طرفی دیگر مجموعه S زیرمجموعه اعداد طبیعی است پس بنابر اصل خوشترتیبی S دارای عضو ابتدا(مینیمم) چون P است. http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/8e02517fc74b493e5535dfae4caa3cb5.png
نشان می دهیم که P عددی اول است. برای اثبات ادعا از برهان خلف استفاده می کنیم:
به برهان خلف فرض می کنیم P عددی اول نباشد، پس P عددی مرکب است لذا:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/db4cdd6e3a5d4d300afd512243ad38f9.png ,این نتیجه می دهد: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2a13c35055efbe4ea79211710d514b8a.png
از طرفی دیگر: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/5e5bc5e51b67f2280f6e70bf3345cdac.png که این نتیجه می دهد:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/7af4c1a08cdca57ed62b71ac31431820.png.
و این با مینیمم بودن P در تناقض است چون:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/e574d54bec13486a76901898ff7fb8d4.png و لذا فرض خلف باطل و چنین نیست که P اول نباشد پس P اول است. به این ترتیب نشان داده شد عدد a حد اقل یک مقسوم علیه اول دارد

[nafise sadeghi]

قضیه 2) بی نهایت عدد اول وجود دارد.
برهان:
برای اثبات این قضیه از برهان خلف استفاده می کنیم. به برهان خلف فرض می کنیم تعداد اعداد اول متناهی باشد و به فرض http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/b79a59db0a7700bb75585611bf0c6826.png تنها اعدد اول موجود باشند. قرار می دهیم:

http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/e2ec65f64d4641636e9f26864c96aaac.png

بوضوح M بزرگتر از یک و طبیعی است پس بر طبق قضیه قبل می توان گفت M دارای حداقل یک مقسوم علیه اول است و چون تعداد اعداد اول موجود محدود است آن مقسوم علیه اول یکی از اعداد http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/b79a59db0a7700bb75585611bf0c6826.png است به فرض عضوی چون: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/10d51ec71d0db5a91f87b303e219cea8.png داریم:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/54403c2e70f3671a9cf516e8caee84f8.png
که این با اول بودن http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/d8da76d10d638854cd56fef1fb7c0f76.png در تناقض است چون http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/aaf6b20b4edddf2e212db43db03f6ab3.png نه اول و نه مرکب است . و لذل فرض خلف باطل و حکم برقرار است و تعداد اعداد اول بی شمار است.



لازم به توضیح است که این قضیه نخستین بار توسط اقلیدس در حدود سال 300 قیل از میلاد اثبات گردیده است

[nafise sadeghi]

قضیه 3) هر عدد مرکب n دارای حداقل یک مقسوم علیه اول کوچکتر یا مساوی http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/5da03840a5e72e66c700a3f705fecb29.png است.
برهان
چون n مرکب است پس: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/4aa84505697bb9ab68d30c3163e15d4f.png
حال نشان می دهیم که: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/d376f60f9d230ea8dacd9fad920d2969.png
به برهان خلف اگر: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/205537125173d100a1625e2971a3a798.png آنگاه http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/a987a8d4447fafc89964c6a8fbc271ea.png و در نتیجه: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/5c33a5b7ca70938ca60feeabb8aec121.png که این تناقض است و لذا فرض خلف باطل و حکم برقرار است یعنی: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/d376f60f9d230ea8dacd9fad920d2969.pngحال چون a بزرگتر از یک است پس a دارای حداقل یک مقسوم علیه اول مانند p است. داریم:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/cea90c6964a11919c37bed95f620ef28.png
و از سوی دیگر: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/feece44f0f8cb130d0e1074ddc5d8c91.png
پس p عددی اول است که در شرایط قضیه صدق می کند و لذا حکم برقرار است.



لازم به توضیح است که قضیه فوق اساس روش غربال اراتستن است.



قضیه4) اگر n عددی طبیعی و بزرگتر از 2 باشد, حتما" بین n و 2n عدد اولی وجود دارد. (قضیه چپیشف)

[nafise sadeghi]

قضیه بنیادی حساب:
هر عدد طبیعی بزرگتر از یک را می توان به صورت یکتایی به صورت حاصل ضرب عوامل اول نوشت.
به عبارت دیگر اگر n عددی طبیعی و بزرگتر از 1 باشد:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/e6c8ac43284958f4557ac8858b02d702.png
که در آن http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/07e4342bbd06cea440709e470bdb9c35.png ها اعداد اول متمایر می باشند.
این نمایش را تجزیه عدد n به عوامل اول می گوییم.


همچنین اگر n<-1 باشد باز هم می توان n را به صورت یکتایی به صورت حاصل ضرب عوامل اول نوشت:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/c1ae45db121d8bdc8d8a2e34f25440ff.png


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/d8ce12a64cbb3028d19c85a84b629296.png

که در آن http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/07e4342bbd06cea440709e470bdb9c35.png ها اعداد اول متمایز می باشند.


توجه: اگر n=1 باشد آنگاه http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/36fb3f607fbce8608e82f2781095310c.png که در ان P هر عدد اولی است.
لازم به توضیح است که ممکن است در تجزیه یک عدد طبیعی به عوامل اول، تعدادی از عوامل یکسان باشند. به عنوان مثال:12=2×2×3
تجزیه استاندارد یک عدد:
اگر n>1 عددی طبیعی باشد آنگاه عدد n را می توان به شکل یکتایی به صورت:

http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/146205a267ef1848906e83c342602ac6.png

که در آن http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/c4ca51287b778d14b6686bbc2e348235.png ها اعداد اول متمایز و http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/b494b8adbcb43905ad57017c017b6cd4.png اعداد طبیعی اند.
این روش نمایش و تجزیه عدد را تجزیه متعارف، استاندارد، یا کانونیک عدد n می گویند.



توجه: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/b494b8adbcb43905ad57017c017b6cd4.png بزرگترین توان http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/c4ca51287b778d14b6686bbc2e348235.png که: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/775c8b2f291315393b4e0cf37696cc3b.png را به صورت http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/874f7b6abe9f19c7c6ceb0b4bd143a0c.png می دهند.
به عنوان مثال تجزیه استاندارد 12 به عوامل اول به صورت مقابل است:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/b75e754ba6931390f410506c821854a2.png