بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 5: یادآوری عددهای اول Primes Revisited

عدد اول، عدد طبیعی بزرگ‌تر از ۱ است که فقط دو شمارنده دارد: ۱ و خودش. عدد مرکب را می‌شود ضرب دو عدد طبیعی بزرگ‌تر از ۱ نوشت و ۱ نه اول است نه مرکب. هر عدد مرکب را با نمودار درختی به ضرب عددهای اول تجزیه می‌کنیم؛ دو عددی که ب.م.م آن‌ها ۱ است، نسبت به هم اول‌اند.

در این جلسه یاد می‌گیری

درس

درخت شمارنده. روی ۵۴۰ بزن و یکی از ضرب‌هایش را انتخاب کن، مثلاً ⁦۲ × ۲۷۰⁩. هر برگی را که اول نیست دوباره بشکن تا همه‌ی برگ‌ها اول شوند. یک بار دیگر از راه دیگری شروع کن: آخرش همان عددهای اول، به همان تعداد، به دست می‌آیند؟

مستطیل‌های مربعی. با ۱۲ مربع کوچک سه مستطیل مختلف می‌شود ساخت: ⁦۱ × ۱۲⁩، ⁦۲ × ۶⁩ و ⁦۳ × ۴⁩. ولی ۷ مربع فقط یک ردیف می‌شوند: ⁦۱ × ۷⁩. عددی مثل ۷ اول است: عدد طبیعی بزرگ‌تر از ۱ که فقط دو شمارنده دارد، ۱ و خودش. عددی مثل ۱۲ که می‌شود آن را ضرب دو عدد طبیعی بزرگ‌تر از ۱ نوشت، مرکب است.

سه دسته. عدد ۱ فقط یک شمارنده دارد؛ نه اول است نه مرکب. پس عددهای طبیعی سه دسته‌اند: ۱، عددهای اول و عددهای مرکب. هر مضرب یک عدد بزرگ‌تر از ۱ (غیر از خودش) مرکب است: ۱۴، ۲۱، ۲۸، … همه ۷ × چیزی‌اند. برای همین ۲ تنها عدد اول زوج است.
اشتباه رایج: «۵۱ اول است، چون شبیه اول‌هاست!» ولی ⁦۵۱ = ۳ × ۱۷⁩. یا «۱ اول است»؛ نه، ۱ دو شمارنده ندارد.

تجزیه با درخت. ۱۲۶ را بشکن: ⁦۲ × ۶۳⁩، بعد ⁦۶۳ = ۷ × ۹⁩ و ⁦۹ = ۳ × ۳⁩. پس ⁦۱۲۶ = ۲ × ۳ × ۳ × ۷ = ۲ × ۳² × ۷⁩. عامل‌های تکراری را با توان می‌نویسیم؛ مثلاً ⁦۵۴۰ = ۲² × ۳³ × ۵⁩. از هر راهی که شروع کنی، همین عددهای اول به دست می‌آیند.

نسبت به هم اول. ب.م.م ۱۲ و ۳۵ را ⁦(۱۲ , ۳۵)⁩ می‌نویسیم. ⁦۱۲ = ۲² × ۳⁩ و ⁦۳۵ = ۵ × ۷⁩ هیچ عامل اول مشترکی ندارند، پس ⁦(۱۲ , ۳۵) = ۱⁩ و می‌گوییم ۱۲ و ۳۵ نسبت به هم اول‌اند؛ با این‌که هر دو مرکب‌اند! دو عدد پشت سر هم (مثل ۲۰ و ۲۱) و دو عدد اول مختلف همیشه نسبت به هم اول‌اند. ک.م.م دو عدد نسبت به هم اول، ضرب خودشان است: ک.م.م ۸ و ۹ برابر ۷۲ است.

با پایتون (اختیاری): همه‌ی مستطیل‌های یک عدد: هر شمارنده با جفتش. بعد math.gcd ب.م.م را می‌دهد؛ اگر ۱ شد، دو عدد نسبت به هم اول‌اند.

import math
n = 36
for a in range(1, n + 1):
    if n % a == 0 and a * a <= n:
        print(a, "x", n // a)
print(math.gcd(12, 35))

مثال‌های این جلسه

چالش‌ها

  1. Three Boxes (آسان)
  2. Rectangles of 24 (آسان)
  3. The Tree of 252 (متوسط)
  4. Coprime Pairs (متوسط)
  5. 42 and 70 (سخت)
  6. Two Primes Make 35 (سخت)

بیشتر بخوان

← جلسه‌ی 4: ضرب و تقسیم عددهای گویا جلسه‌ی 6: تعیین عددهای اول →