سرفصل‌های این مبحث

نظریه اعداد

اعداد اول (تعریف)

آخرین ویرایش: 23 آبان 1403

دسته‌بندی: نظریه اعداد

امتیاز:

نظر کاربران: برای نظر دادن اولین باش!

مقدمه‌ای بر اعداد اول

می‌خواهیم درباره دسته‌ای از اعداد طبیعی، مطالبی را بیان کنیم که شاید بحث‌انگیزترین و به‌نوعی جالب‌ترین اعداد طبیعی هستند.

اعدادی که تعدادشان بی‌نهایت است ولی تاکنون هیچ قاعده خاصی برای تولید آنها به‌دست نیامده است و حتی چگونگی توزیع آنها بین اعداد طبیعی، مشخص نشده است.

می‌دانیم هر عدد صحیح $a \neq \pm 1$ حداقل دارای چهار شمارنده $(\pm 1)$ و $(\pm a)$ است.

برای سهولت بی‌آن‌که به کلیت لطمه‌ای وارد شود، اعداد اول را فقط برای اعداد صحیح مثبت تعریف می‌کنند.

در این‌جا می‌خواهیم تا یکی از اساسی‌ترین قضایای تئوری اعداد یعنی قضیه‌ای به‌نام قضیه بنیادی حساب را ثابت کنیم.

یادآوری

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

در واقع برطبق این قضیه، نقش بنیادی اعداد اول آشکار می‌شود، چنان‌چه همه اعداد، از اعداد اول به‌وجود آمده‌اند.

در اصطلاح ریاضیدانان، اعداد اول بلوک‌های ساختمانی اعداد می‌باشند و به همین دلیل این اعداد، آنان را شیفته خود کرده است.

تعریف اعداد اول

عدد طبیعی $p > 1$ را اول گویند، هرگاه شمارنده های مثبت آن $1$ و $p$ باشند.

نکته

1- هر عدد طبیعی بزرگ‌تر از یک را که اول نباشد، تجزیه پذیر یا مرکب می‌گوییم.

به‌عنوان نمونه $11, 7, 5, 3, 2$ اعداد اول هستند و $50, 24, 9$ اعداد مرکب هستند.

2- عدد $1$ نه اول است و نه مرکب.

بعدها خواهیم دید که پذیرفتن عدد $1$ در زمره اعداد اول نه تنها فایده‌ای ندارد حتی اختلالی د‌ر یکتایی تجزیه هر عدد صحیح به عوامل اول هم ایجاد می‌کند.

3- اگر $p$ عدد اول و $m > 0$ و $m | p$ آن‌گاه $m = 1$ یا $m = p$ است.

4- اگر $p$ عدد اول باشد، طبق تعریف فقط تجزیه بدیهی دارد یعنی $(p = 1 \times p)$ و فاقد تجزیه نابدیهی است.

هر عددی مانند $a$ دارای یک تجزیه بدیهی $(a \times 1)$ می‌باشد.

به‌عنوان نمونه عدد $12$ یک تجزیه بدیهی به‌صورت $(12 \times 1)$ دارد و تجزیه های غیر بدیهی و جدی آن عبارتند از :

$\begin{array}{l} 6 \times 2 \\ 2 \times 6 \\ 3 \times 4 \\ 4 \times 3 \end{array}$

5- گزاره زیر را در نظر بگیرید:

$i f p = a b \Rightarrow (a = 1) \land (b = p)$

این گزاه نشان می‌دهد که عدد اولیه جز تجزیه بدیهی $1 \times p$ تجزیه نابدیهی ندارد و این بیان‌گر آن است که اعداد اول، اعدادی ساده و بسیط هستند.

6- اگر اعداد اولی مانند $p_{k}, ..., p_{2}, p_{1}$ بتوان یافت به‌طوری‌که $n = p_{1} . p_{2} ... p_{k}$ در این‌صورت می‌گویند $n$ به عوامل اول تجزیه شده است.

به‌عنوان نمونه هیچ یک از حاصل ضرب های $\{\begin{cases} 12 \times 1 \\ 3 \times 4 \\ 6 \times 2 \end{cases}$ یک تجزیه عدد $12$ به عوامل اول نیست، اما $2 \times 2 \times 3$ تجزیه $12$ به عوامل اول است.

7-گاهی عددی را عدد اول مطلق گویند وقتی که لازم باشد، آن‌را بین سایر عددهای اول مشخص کنند.

تمرین

اگر داشته باشیم:

$\forall x, y \in N; 4 x^{2} - 9 y^{2} = 7$

مقدار $x$ و $y$ را بیابید.

$\begin{array}{l} 4 x^{2} - 9 y^{2} = 7 \\ \Rightarrow (2 x - 3 y) (2 x + 3 y) = 1 \times 7 \\ \Rightarrow \{\begin{cases} 2 x - 3 y = 1 \\ 2 x + 3 y = 7 \end{cases}〉 \{\begin{cases} x = 2 \\ y = 1 \end{cases} \end{array}$

تمرین

اگر داشته باشیم:

$\forall m, n \in N; 9 m^{2} - 4 n^{2} = 17$

مقدار $m$ و $n$ را بیابید.

$\begin{array}{l} 9 m^{2} - 4 n^{2} = 17 \end{array}$

$\begin{array}{l} \Rightarrow (3 m - 2 n) (3 m + 2 n) = 1 \times 17 \end{array}$

$\begin{array}{l} \Rightarrow \{\begin{cases} 3 m - 2 m = 1 \\ 3 m + 2 n = 17 \end{cases} \\ \Rightarrow \{\begin{cases} m = 3 \\ n = 4 \end{cases} \end{array}$

دریافت مثال

دریافت فایل PDF

قضایای اعداد اول

قضیه

اگر $p$ و $q$ دو عدد اول باشند:

$i f p |q \lor q |p \Rightarrow p = q$

اثبات

$p | q \Rightarrow \{\begin{cases} p = 1 \\ p = q \end{cases}〉 i f p \neq 1 \Rightarrow p = q$

قضیه

لم

اگر $p$ عددی اول و $a$ یک عدد صحیح دل‌خواه باشد، در این‌صورت:

$(a, p) = p \lor (a, p) = 1$

اثبات

فرض کنیم $d = (a, p)$ بنابراین خواهیم داشت:

$d = (a, p) \Rightarrow (d | p) \Rightarrow \{\begin{cases} d = 1 \\ d = p \end{cases}〉 \{\begin{cases} (a, p) = 1 \\ (a, p) = p \end{cases}$

نکته

از قضیه فوق، نتایج زیر حاصل می‌شود:

1- اگر $p$ عددی اول باشد در این‌صورت:

$p 1 a \Leftrightarrow (p, a) = 1$

با توجه به لم فوق معلوم است که برای یافتن ب‌م‌م عدد اول $p$ و یک عدد صحیح دل‌خواه مانند $a$ فقط به‌یک بار تقسیم کردن نیاز داریم، اگر باقیمانده تقسیم $a$ بر $p$ مساوی صفر شود، ب‌م‌م همان $p$ است و اگر باقیمانده صفر نشود، ب‌م‌م مساوی $1$ است.

2- اگر $p$ عددی اول باشد، هر یک از اعداد $p - 1, ....., 3, 2, 1$ و در نتیجه حاصل ضرب آنها یعنی:

$1 \times 2 \times 3 \times ... \times (p - 1)$

نسبت به $p$ اول می‌باشد.

$\{\begin{cases} (p, 1) = 1 \\ (p, 2) = 1 \\ (p, 3) = 1 \\ ⋮ \\ (p, p - 1) = 1 \end{cases}$

$(p, 1 \times 2 \times 3 \times ... \times (p - 1)) = 1$

3- اگر $p$ و $q$ دو عدد اول متمایز باشند، در این‌صورت دو عدد نسبت به هم اولند یعنی:

$(p, q) = 1$

قضیه

اگر $p$ عددی اول باشد، آن‌گاه:

$i f p | a b \Rightarrow p | a \lor p | b$

اثبات

اگر $p | a$ حکم ثابت است در غیر این‌صورت فرض می‌کنیم $p | a$ بنابراین $(p, a) = 1$ لذا بنابر لم اقلیدس:

$p | a b, (p, a) = 1 \Rightarrow p | b$

نکته

از قضیه فوق، نتایج زیر حاصل می‌شود:

1- اگر $p$ عددی اول باشد، آن‌گاه:

$p | a_{1} a_{2} ... a_{n} \Rightarrow p | a_{1} \lor p | a_{2} \lor ..... \lor p | a_{n}$

تمرین

اگر $q_{n}, ..., q_{2}, q_{1}, p$ اعداد اولی باشند به طوری‌كه داشته باشیم:

$p | q_{1} q_{2} ... q_{n}$

ثابت كنيد به ازای $k$ داریم $p = q_{k}$ .

چون $p | q_{1} q_{2} ... q_{n}$ پس $p$ حداقل یکی از $q_{i}$ ها را مثلا $q_{k}$ را می‌شمارد، لذا:

$p | q_{k} \Rightarrow \{\begin{cases} p = 1 \\ p = q_{k} \end{cases}〉 \overset{p i s p r i m e}{\to} p = q_{k}$

دریافت مثال

دریافت فایل PDF

نکته

2- اگر $p$ عددی اول باشد، آن‌گاه:

$p | a^{n} \Rightarrow p | a$

تمرین

اگر $p$ عدد اولی باشد به طوری‌كه:

$p | 3^{n}$

نشان دهید $p = 3$ است.

$\begin{array}{l} i f p | a^{n} \Rightarrow p | a \end{array}$

$\begin{matrix} i f p | 3^{n} \Rightarrow P | 3 \Rightarrow P = 1 \lor P = 3 \overset{p i s p r i m e}{\to} P = 3 \end{matrix}$

دریافت مثال

دریافت فایل PDF

قضیه

هر عدد طبیعی $n > 1$ حداقل دارای یک شمارنده اول است.

اثبات

هر عدد طبیعی $n > 1$ را در نظر می‌گیریم، مجموعه تمام شمارنده های بزرگ‌تر از $1$ این عدد را با $S$ نشان می‌دهیم، یعنی:

$S = \{a | a > 1, a | n\}$

چون $n \in Z$ می‌باشد پس $S$ تهی نیست، در نتیجه بنابر اصل خوش ترتیبی دارای عضو ابتدا است که آن‌را $p$ می‌نامیم و ثابت می‌کنیم $p$ اول است.

از آن‌جا که هر شمارنده $p$ یک شمارنده $n$ نیز می‌باشد، اگر $p$ اول نباشد در این‌صورت $S$ عضوی کوچک‌تر از $p$ خواهد داشت که این تناقض است، بنابراین $p$ اول است.

مجددا یادآوری می‌کنیم که اگر $p$ اول باشد، خود $p$ تجزیه عدد اول $p$ به عوامل اول است.

قضیه

قضیه بنیادی حساب

هر عدد طبیعی $n > 1$ را می‌توان به عوامل اول تجزیه کرد و این تجزیه بدون درنظر گرفتن ترتیب قرار گرفتن عوامل، منحصربه‌فرد است.

اثبات

عدد $n$ یا اول است یا مرکب است.

اگر $n$ اول باشد، چیزی برای اثبات نمی‌ماند.

اگر $n$ مرکب باشد، در این‌صورت بنا به قضیه‌ای که قبلا بیان شده، $n$ حداقل دارای یک شمارنده اول مانند $p_{1}$ است، بنابراین می‌توان نوشت:

$n = p_{1} n_{1}; 1 < n_{1} < n$

به‌همین ترتیب در مورد $n_{2}$ عمل می‌کنیم.

چون $n > n_{1} > n_{2} > ... > 1$ پس این روند نمی‌تواند بی‌نهایت بار تکرار شود و بالاخره یکی از $n_{k}$ ها عدد اولی مانند $p_{k}$ است و لذا خواهیم داشت:

$n = p_{1} p_{2} ... p_{k}$

در این قسمت از اثبات یکتایی تجزیه صرف نظر می‌کنیم.

نکته

1- هر عدد طبیعی $n > 1$ را به‌طور منحصر به‌فردی می‌توان به‌صورت زیر نمایش داد:

$n = {p_{1}}^{α_{1}} . {p_{2}}^{α_{2}} ... {p_{t}}^{α_{t}}$

که در آن $α_{i}$ ها اعداد طبیعی و $p_{i}$ ها اعداد اول متمایزی می‌باشند به‌طوری‌که $p_{1} < p_{2} < ... < p_{t}$ .

2- تجزیه استاندارد یا کانونیک عدد $n$ به‌صورت زیر است:

$n = {p_{1}}^{α_{1}} . {p_{2}}^{α_{2}} ... {p_{t}}^{α_{t}} = \prod_{i = 1}^{t} {p_{i}}^{α_{i}}$

توجه کنید در تجزیه یک عدد طبیعی به اعداد اول، از هر عدد اولی چون $p_{i}$ به‌صورت $p_{i}^{0}$ می‌توانیم استفاده کنیم، به‌عنوان نمونه داریم:

$18 = 2^{1} \times 3^{2} \times 5^{0} \times 7^{0} \times ...$

ممکن است تعدادی از عوامل اول تجزیه، با هم مساوی باشند، به‌عنوان نمونه داریم:

$360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^{3} \times 3^{2} \times 5$

یادآوری

اگر $a$ و $b$ دو عدد طبیعی بوده و پس از تجزیه به عوامل اول به‌صورت تجزیه می‌شود:

$\{\begin{cases} a = p_{1}^{α_{1}} \times p_{2}^{α_{2}} ... \times p_{k}^{α_{k}} \\ b = p_{1}^{β_{1}} \times p_{2}^{β_{2}} ... \times p_{k}^{β_{k}} \end{cases}$

حالت اول- ب‌م‌م به‌صورت زیر محاسبه می‌شود:

$d = (a, b) = p_{1}^{θ_{1}} p_{2}^{θ_{2}} ... p_{k}^{θ_{k}}; θ_{i} = \min \{α_{i}, β_{i}\}$

منظور آن است که ب‌م‌م دو عدد همان عامل های مشترک دو عدد با توان کوچک‌تر است.

به‌عنوان نمونه داریم:

$\{\begin{array}{l} 36 = 2^{2} \times 3^{2} \\ 84 = 2^{2} \times 3 \times 7 \end{array}〉 (36, 84) = 2^{2} \times 3 = 12$

حالت دوم- ک‌م‌م به‌صورت زیر محاسبه می‌شود:

$C = [a, b] = p_{1}^{θ_{1}} p_{2}^{θ_{2}} ... p_{k}^{θ_{k}}; θ_{i} = \max \{α_{i}, β_{i}\}$

منظور آن است که ک‌م‌م دو عدد همان عامل های مشترک دو عدد با توان بزرگ‌تر ضرب در عامل های غیر مشترک می‌باشد.

به‌عنوان نمونه داریم:

$\{\begin{array}{l} 36 = 2^{2} \times 3^{2} \\ 84 = 2^{2} \times 3 \times 7 \end{array}〉 [36, 84] = 2^{2} \times 3^{2} \times 7$

تمرین

(ب.م.م) و (ک.م.م) اعداد زیر را به‌دست آورید.

$\{\begin{cases} a = 18 \times 63 \times 49 \\ b = 81 \times 39 \end{cases}$

$\{\begin{cases} a = 18 \times 63 \times 7 = 2 \times 3^{4} \times 7^{2} \\ b = 81 \times 39 = 3^{5} \times 13 \end{cases}$

$\begin{matrix} \{\begin{cases} d = (a, b) = 3^{4} = 81 \\ c = [a, b] = 2 \times 3^{5} \times 7^{2} \times 13 \end{cases} \end{matrix}$

دریافت مثال

دریافت فایل PDF

قضیه

عدد اول زوجی به‌جز عدد $2$ وجود ندارد.

اثبات

اگر $n \neq 2$ عددی زوج باشد، در این‌صورت $2 | n$ در نتیجه عاملی به‌جز $1$ و خودش دارد، پس اول نیست.

قضیه

هیچ دو عدد اول و متوالی به‌جز $2$ و $3$ وجود ندارد.

اثبات

اگر فرض کنیم $p$ عددی اول و $p \geq 3$ باشد، در این‌صورت بنا به قضایای مطرح شده $p$ زوج نیست و فرد می‌باشد در نتیجه $(p + 1)$ باید زوج باشد، که در این‌صورت اول نیست.

قضیه

اگر $p$ عددی اول باشد و $a$ عددی صحیح به‌طوری‌که $p | a$ که در این‌صورت همواره $(p, a) = 1$ .

به‌عبارت دیگر عدد اول $p$ نسبت به هر عددی که مضرب $p$ نباشد، اول است.

اثبات

فرض است که:

$\{\begin{cases} 1 | p, p | p \\ \forall a \in z, p | a \end{cases}$

فرض کنیم $(p, a) = d$ پس ثابت می‌کنیم که $d = 1$ .

$\begin{array}{l} d = (a, p) \Rightarrow (d | p) \Rightarrow \{\begin{cases} d = 1 \\ d = p \end{cases} \\ i f d = p \Rightarrow d | a \Rightarrow p | a \end{array}$

که با فرض $p | a$ تناقض دارد پس $d = 1$ است.

تمرین

ثابت كنيد هرگاه $m^{2} - n^{2}$ عددی اول باشد، آن‌گاه $m$ و $n$ دو عدد متوالی طبیعی هستند.

$\begin{array}{l} m^{2} - n^{2} = p \\ \Rightarrow (m - n) (m + n) = 1 \times p \\ \Rightarrow \{\begin{cases} m - n = 1 \Rightarrow m = n + 1 \\ m + n = p \end{cases} \end{array}$

هرگاه $p > 5$ عددی اول باشد، عدد $5 p + 1$ را چنان بيابيد كه مكعب كامل باشد.

$\begin{array}{l} 5 p + 1 = n^{3} \\ \Rightarrow 5 p = n^{3} - 1 \\ \Rightarrow 5 p = (n - 1) (n^{2} + n + 1) \\ \Rightarrow 5 \times p = (n - 1) (n^{2} + n + 1) \end{array}$

$\begin{array}{l} \Rightarrow \{\begin{cases} n - 1 = 5 \Rightarrow n = 6 \\ (n^{2} + n + 1) = p \Rightarrow p = {(6)}^{2} + (6) + 1 \Rightarrow p = 43 \end{cases} \end{array}$

$\begin{array}{l} \Rightarrow 5 p + 1 = 5 (43) + 1 = 216 = 6^{3} \end{array}$

تمرین

به ازای چه مقاديری از $x$ عبارت زیر مربع کامل است.

$x^{2} - 14 x + 26$

$\begin{array}{l} x^{2} - 14 x + 26 = k^{2} \\ \Rightarrow {(x - 7)}^{2} - 23 = k^{2} \\ \Rightarrow {(x - 7)}^{2} - k^{2} = 23 \end{array}$

$\begin{array}{l} \Rightarrow (x - 7 - k) (x - 7 + k) = 23 \end{array}$

$\begin{array}{l} \Rightarrow (x - 7 - k) (x - 7 + k) = 1 \times 23 \end{array}$

$\begin{array}{l} \Rightarrow \{\begin{cases} x - 7 - k = 1 \\ x - 7 + k = 23 \end{cases}〉 x = 19 \end{array}$

دریافت مثال

دریافت فایل PDF

تشخیص اول بودن یک عدد طبیعی

چگونه می‌توان تشخیص داد یک عدد مفروض، اول یا مرکب است؟

اگر مرکب است چگونه می‌توان یک شمارنده غیر بدیهی آن‌را یافت؟

واضح‌ترین شیوه، تقسیم کردن پی‌در‌پی آن عدد بر اعداد طبیعی قبل از آن است، اگر بر هیچ یک از آنها قابل قسمت نبود، اول است.

اگر چه این روش بسیار ابتدایی و ساده است،اما یک راه حل عملی و مفید نیست زیرا برای اعداد نه‌چندان بزرگ هم مستلزم صرف وقت بسیاری هستیم.

اعداد مرکب دارای خاصیتی هستند که به‌طور محسوسی باعث کاهش محاسبات می‌شود هر چند حتی با این روش، فرآیند تشخیص اول بودن هم چنان خسته‌کننده و طاقت فرساست.

قضیه

اگر $n$ یک عدد طبیعی مرکب باشد، در این‌صورت $n$ شمارنده اولی مانند $p$ دارد به‌طوریه‌که:

$p \leq \sqrt{n}$

اثبات

چون $n$ مرکب است، بنابراین $n$ را می‌توان به‌صورت حاصل ضرب زیر نوشت:

$n = b c; 1 < b < n, 1 < c < n$

$\begin{array}{l} i f b \leq c \\ \Rightarrow b^{2} \leq b c; b c = n \\ \Rightarrow b^{2} \leq n \\ \Rightarrow b \leq \sqrt{n} \end{array}$

از طرفی $b > 1$ لذا دارای یک شمارنده اول مانند $p$ است، بنابراین:

$\begin{array}{l} p \leq b \leq \sqrt{n} \\ p | b, b | n \Rightarrow p | n \end{array}$

نکته

برای آزمودن اول بودن یک عدد معین مانند $n > 1$ کافی است $n$ را بر تمام اعداد اول کوچک‌تر یا مساوی $\sqrt{n}$ تقسیم کنیم، اگر $n$ بر هیچ یک از این اعداد اول بخش پذیر نبود، $n$ اول است.

تمرین

آیا $509$ عددی اول است؟

$22 < \sqrt{509} < 23$

بنابراين بايد اعداد اول كوچک‌تر از $22$ را امتحان كرد، اين اعداد عبارتند از:

$2, 3, 5, 7, 11, 13, 17, 19$

با تقسيم $509$ بر اين اعداد در می‌يابيم كه این عدد بر هيچ يک از اين اعداد بخش پذير نيست، بنابراين $509$ عدد اول است.

دریافت مثال

دریافت فایل PDF

قضیه

قضیه اقلیدسی

بی‌نهایت عدد اول وجود دارد، به‌عبارت دیگر مجموعه اعداد اول نامتناهی است.

اثبات

اساس کار در اثبات قضیه این است که هیچ فهرستی متناهی از اعداد اول وجود ندارد

در واقع اگر در مجموعه $..., p_{4} = 7, p_{3} = 5, p_{2} = 3, p_{1} = 2$ یک عنصر انتها مانند $p_{k}$ وجود داشته باشد، عدد زیر را در نظر می‌گیریم:

$N = (p_{1} p_{2} ... p_{k}) + 1$

چون $N > 1$ لذا دارای یک شمارنده اول مانند $p$ است.

چون $p_{k}, ..., p_{2}, p_{1}$ را تمام اعداد اول فرض کرده‌ایم لذا $p$ که از $p_{k}$ هاست، بنابراین:

$p | p_{1} p_{2} ... p_{k} \Rightarrow p | N - p_{1} p_{2} ... p_{k} \Rightarrow p | 1 \Rightarrow p = 1$

که این ناممکن است بنابراین مجموعه اعداد اول نامتناهی است.

دریافت مثال

دریافت فایل PDF

توزیع اعداد اولی

با این‌که بی‌نهایت عدد اول وجود دارد، توزیع اعداداول در مجموعه اعداد طبیعی پر رمز و راز است.

در مورد توزیع اعداد اول دو واقعیت وجود دارد.

واقعیت اول- این‌که اعداد اول علیرغم تعریف ساده و نقش خود به‌عنوان مصالح ساختمانی، خودسرترین و بی‌نظم‌ترین مقوله‌هایی هستند که مورد مطالعه ریاضیدانان قرار گرفته‌اند و مانند علف‌های هرز در میان اعداد طبیعی رشد می‌کنند و به نظر می‌رسد از هیچ قاعده‌ای جز قاعده تصادف پیروی نمی‌کنند و هیچ کس نمی‌تواند پیش‌بینی کند عدد اول بعدی در کجا سبز خواهد شد.

واقعیت دوم- واقعیت دوم شگفت‌انگیزتر است، عکس واقعیت اول را بیان می‌کند، قوانینی بر چگونگی رفتار آنها حکم‌فرماست و این اعداد تقریبا با انضباطی از این قوانین تبعیت می‌کنند.

تعریف

دو عدد اول را دوقلو گویند هرگاه اختلاف آن دو مساوی $2$ باشد.

به‌عنوان نمونه $(5, 7)$ و $(11, 13)$ نمونه‌هایی از زوج اعداد دوقلو هستند.

هنوز در مورد نامتناهی یا متناهی بودن زوج‌های اعداد دوقلو به نتیجه‌ای دست نیافته‌اند.

وجود اعداد دوقلو در میان اعداد اول، نشان‌گر آن است که اعداد اول تا چه حد می‌توانند نزدیک هم باشند.

از طرف دیگر در زیر نشان می‌دهیم که در میان اعداد اول شکاف‌های عظیمی وجود دارد.

نکته

شکاف‌هایی به‌اندازه دل‌خواه بزرگ در مجموعه اعداد اول وجود دارد.

به‌عبارت دیگر، برای هر عدد طبیعی $n$ ، $n$ عدد متوالی وجود دارند که همگی مرکب هستند.

به‌عنوان نمونه:

$n$ عدد متوالی زیر را در نظر می‌گیریم:

$(n + 1)! + 2, ..., (n + 1)! + 3, (n + 1)! + n$

نشان می‌دهیم همه این اعداد مرکب‌اند:

$(n + 1)! + 2 = (1 \times 2 \times ... \times (n + 1)) + 2 = 2 k + 2$

یعنی $(n + 1)! + 2$ بر $2$ بخش پذیر است.

$(n + 1)! + 3 = [1 \times 2 \times 3 \times ... \times (n + 1)] + 3 = 3 k + 3$

یعنی $(n + 1)! + 3$ بر $3$ بخش پذیر است.

به‌همین ترتیب می‌توان نشان داد که عدد زیر بر $k$ بخش پذیر است:

$(n + 1)! + k; 2 \leq k \leq n + 1$

به‌عنوان نمونه اگر بخواهیم چهار عدد متوالی نشان دهیم که در میان آنها هیچ عدد اولی وجود ندارد، خواهیم داشت:

$\begin{array}{l} 5! + 2 = 122 = 2 \times 61 \\ 5! + 3 = 123 = 3 \times 41 \\ 5! + 4 = 124 = 4 \times 31 \\ 5! + 5 = 125 = 5 \times 25 \end{array}$

توابع مولد اعداد اول

توابع مولد اعداد اول توابعی هستند که به ازای هر $n \in N$ عدد اول تولید می‌کند.

تابع زیر را در نظر بگیرید:

$f (n) = n^{2} + n + 11$

این تابع به‌ازای $9$ عدد متوالی، اعداد اول و به ازای $n = 10$ و $n = 11$ عدد مرکب تولید می‌کند، یعنی این تابع، یک تابع مولد اعداد اول نیست.

سال‌های بسیاری در قرون وسطی تصور می‌کردند که که سه‌جمله‌ای درجه دوم $f (n) = n^{2} + n + 41$ فقط عدد اول تولید می‌کند، در صورتی‌که معلوم شد تابع درجه دوم فوق به ازای $n = 0, \dots, 39$ عدد اول تولید می‌کند اما به‌ازای $n = 40$ اول نیست.

نکته

دانشمندی به‌نام دیریکله ثابت کرد اگر $a$ و $b$ نسبت به‌هم اول باشند، $a + k b$ بی‌نهایت عدد اول تولید می‌کند، با این همه، هیچ عبارتی به‌صورت $a + k b$ وجود ندارد که فقط اعداد اول تولید کند.

اعداد مرسن

در ریاضی سنت شده است که اعداد به‌صورت $M_{n} = 2^{n} - 1$ را به‌مناسبت نام کشیش فرانسوی مارین مرسن اعداد مرسن نامیده می‌شود، چرا که مرسن در زمینه اول بودن این نوع اعداد اظهار نظری نادرست اما محرک کرده بود.

در سال $1644$ مرسن اظهار داشت که $M_{p} = 2^{p} - 1$ به‌ازای اعداد زیر اول هستند:

$p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257$

به‌ازای سایر اعداد $p < 257$ مرکب است.

ریاضیدانان معتقدند که به‌طور قطع مرسن تمامی اعدادی را که اول بودن آنها را ادعا کرده آزمایش نکرده است.

تمرین

اگر $2^{n} - 1$ اول باشد، نشان ‌دهید که $n$ اول است.

اثبات با عکس نقیض:

فرض کنید $n$ اول نباشد، بنابراین $n$ دارای تجزیه غیربدیهی $n = r s$ است و $S < n$ و $r > 1$ است، حال می‌توان نوشت:

$2^{n} - 1 = 2^{r s} - 1 = {(2^{r})}^{s} - 1 = (2^{r} - 1) [{(2^{r})}^{s - 1} + \dots + 1]$

واضح است که هر یک از عوامل فوق از $1$ بزرگ‌تر هستند.

یعنی $2^{r} - 1$ دارای تجزیه غیربدیهی است که این خلاف اول بودن $2^{n} - 1$ است.

اعداد فرما

قرار است یک نوع از اعداد را بررسی کنیم که منبعی غنی از حدس‌ها در ریاضیات است.

این اعداد، حالت خاصی از اعداد به‌صورت $2^{m} + 1$ می‌باشند.

هر عدد فرما عددی است به‌صورت عدد زیر:

$F_{n} = 2^{2^{n}} + 1; n \geq 0$

اگر $F_{n}$ اول باشد، آن را عدد اول فرما گویند.

فرما که اغلب حدس‌هایش برای ریاضیدانان درخور توجه و قابل اعتماد بود، مشاهده کرد که:

$\begin{array}{l} F_{0} = 2^{2^{0}} + 1 = 3 \end{array}$

$\begin{array}{l} F_{1} = 2^{2^{1}} + 1 = 5 \end{array}$

$\begin{array}{l} F_{2} = 2^{2^{2}} + 1 = 17 \end{array}$

$\begin{array}{l} F_{3} = 2^{2^{3}} + 1 = 257 \end{array}$

$F_{4} = 2^{2^{4}} + 1 = 65 / 537$

همگی اول هستند، لذا تصور کرد که همه $F_{n}$ اولند، در نامه‌ای که به مرسن نوشت اعلام کرد من اعدادی به‌صورت $2^{2^{n}} + 1$ یافته‌ام که همیشه اولند و ریاضیدانان سال‌ها بعد درستی آن‌را خواهند فهمید.

اما در سال $1732$ اولر نشان داد که:

$F_{5} = 2^{2^{5}} + 1 = 4, 294, 967, 297$

بر $641$ بخش پذیر است، بدین ترتیب خط بطلانی بر ادعای فرما کشید.

تست‌های این مبحث

تست شماره 1

در تساوی زیر اگر $n \in ℤ$ و $P$ عدد اول باشد، $n + P$ کدام گزینه است؟

$n^{4} + 4 = P$

مشاهده پاسخ تست

تست شماره 2

معادله زیر را در نظر بگیرید:

$p q r s + 1 = 4^{p + q}$

اگر مجهولات فوق با شرط $p < q < r < s$ همگی اعداد اول باشند، مجموع مجهولات کدام گزینه است؟

$280$
$281$
$282$
$283$

مشاهده پاسخ تست

خرید پاسخ‌ها

اعداد اول (تعریف)

6,000تومان

برای ارسال نظر وارد سایت شوید

نظریه اعداد

اعداد اول (تعریف)

مقدمه‌ای بر اعداد اول

تعریف اعداد اول

قضایای اعداد اول

تشخیص اول بودن یک عدد طبیعی

توزیع اعداد اولی

تعریف

توابع مولد اعداد اول

اعداد مرسن

اعداد فرما

تست‌های این مبحث

nenomatica

مجموعه قوانین

دسترسی سریع

آیا می‌خواهید فیلم معرفی را مشاهده نمایید؟