ماشین‌حساب تجزیه به عوامل اول

چهارچوب فاکتوراسیون اولی

فاکتوراسیون اولی فرایند تجزیه یک عدد مرکب به مجموعه ی منحصر به فردی از فاکتورهای اول است. یک عدد اول یک عدد طبیعی بزرگتر از 1 است که فقط توسط 1 و خود آن قابل تقسیم است — برای مثال، 2، 3، 5، 7، 11، 13، 17، 19، 23. یک عدد مرکب هر عدد طبیعی بزرگتر از 1 است که نه اول است — یعنی حداقل یک فاکتور دیگر از 1 و خود آن دارد.

وقتی که ما فاکتوراسیون اولی یک عدد مانند 360 را انجام می‌دهیم، آن را به عنوان محصولی از اول‌ها بیان می‌کنیم: 360 = 2³ × 3² × 5. این نمایندگی برای هر عدد صحیح منحصر به فرد است — یک نتیجه‌ای که در theorem بنیادی حساب منعکس شده است، که هر عدد صحیح بزرگتر از 1 یا اول است یا می‌تواند به عنوان یک محصول منحصر به فرد از اعداد اول (از نظر ترتیب فاکتورها بی‌اهمیت) بیان شود.

این مفهوم بیش از 2,000 سال مورد مطالعه قرار گرفته است. Elements اقلید (حدود 300 قبل از میلاد) هر دو اثبات بی‌نهایت بودن اول‌ها و شکل اولیه‌ترین theorem بنیادی را شامل می‌شود، بنابراین فاکتوراسیون اولی یکی از قدیمی‌ترین مشکلات پیوسته مورد مطالعه در ریاضیات است.

theorem بنیادی حساب

theorem بنیادی حساب بنیان ریاضیات عدد است. دو بخش دارد: اول، هر عدد صحیح بزرگتر از 1 می‌تواند به عنوان محصولی از اول‌ها بیان شود؛ دوم، این نمایندگی منحصر به فرد است (تا حداکثر تا ترتیب فاکتورها). برای مثال، 12 = 2² × 3، و هر روش که انتخاب کنید، همیشه به فاکتورهای اول با همان توان‌های اول می‌رسید.

این منحصر به فردی است که فاکتوراسیون اولی را इतनا قدرتمند می‌کند. بدون آن، عملیات حساب مثل یافتن GCD و LCM، ساده‌سازی تقسیم، یا اثبات خواص تقسیم‌پذیری بسیار پیچیده‌تر بود. این theorem تقریباً تمام حساب و حساب میان‌رده را پایه‌گذاری می‌کند.

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

چگونگی یافتن فاکتورهای اول: روش‌های مرحله به مرحله

دو روش اصلی دستی برای فاکتوراسیون اولی وجود دارد: شاخه‌درخت و تقسیم تکراری.

روش شاخه‌درخت: عدد را در بالای درخت قرار دهید و آن را به دو فاکتور تقسیم کنید. هر فاکتور مرکب را ادامه دهید تا تمام شاخه‌ها در اعداد اول ختم شوند. برای 180: شاخه به 4 و 45 → شاخه 4 را به 2 و 2 → شاخه 45 را به 9 و 5 → شاخه 9 را به 3 و 3. تمام نوک‌های شاخه‌ها را جمع کنید: 2 × 2 × 3 × 3 × 5 = 2² × 3² × 5.

روش تقسیم تکراری: عدد را با کوچک‌ترین اولی که آن را به طور مساوی تقسیم می‌کند، تقسیم کنید، سپس تقسیم‌کننده را با کوچک‌ترین اولی که آن را تقسیم می‌کند، تقسیم کنید، و به این ترتیب ادامه دهید. برای 360: 360 ÷ 2 = 180 → 180 ÷ 2 = 90 → 90 ÷ 2 = 45 → 45 ÷ 3 = 15 → 15 ÷ 3 = 5 → 5 اول است. نتیجه: 2³ × 3² × 5.

راهنمای کوتاه: فقط باید فاکتورهای اول را تا ریشه دوم عدد تست کنید. اگر هیچ اولی تا √n آن را تقسیم نکند، آن عدد اول است. برای n = 97، √97 ≈ 9.85، بنابراین فقط باید 2، 3، 5، 7 را تست کنید. چون هیچکدام از آن‌ها 97 را تقسیم نمی‌کنند، اول است. این کار را برای اعداد بزرگ بسیار کاهش می‌دهد.

جدول ارجاع به عوامل اول

در زیر جدولی برای ارجاع به عوامل اول عددهای معمولی آورده شده است:

فرمول تعداد عوامل: اگر n = p₁^a × p₂^b × p₃^c…، تعداد کل عوامل به صورت (a+1)(b+1)(c+1)… است. برای 360 = 2³ × 3² × 5¹: عوامل = (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24.

کاربردهای ارجاع به عوامل اول

بزرگترین کسر مشترک (GCD): برای یافتن GCD(48, 180)، هر دو عدد را تجزیه کنید — 48 = 2⁴ × 3، 180 = 2² × 3² × 5 — سپس حداقل توان هر عدد اول مشترک را بگیرید: GCD = 2² × 3 = 12. GCD برای ساده‌سازی تقسیم استفاده می‌شود: 48/180 = 4/15 (هر دو را با 12 تقسیم کنید).

کمترین کسر مشترک (LCM): حداکثر توان هر عدد اول را در هر دو تجزیه بردار بگیرید. LCM(48, 180) = 2⁴ × 3² × 5 = 720. LCM برای اضافه کردن تقسیمات با تقسیم دهندگان مختلف استفاده می‌شود — شما نیاز به یک تقسیم دهنده مشترک دارید که LCM(تقسیم دهنده₁، تقسیم دهنده₂) است.

رمزنگاری (RSA): سختی تجزیه عددهای بزرگ — به ویژه حاصل چند عدد اول بزرگ — اساس ریاضی رمزنگاری RSA است. RSA-2048 از یک کلید عمومی استفاده می‌کند که حاصل دو عدد اول 1024 بیتی است. تجزیه آن طولانی‌تر از سن جهان با الگوریتم‌های فعلی است. این امنیت زیربنای HTTPS، رمزنگاری ایمیل و امضای دیجیتال را تشکیل می‌دهد.

ساده‌سازی تعاریف: در جبر، تجزیه مجدد چند جمله‌ای شباهت‌های مفهومیش را با تجزیه عددهای صحیح دارد. همان‌طور که 12 = 4 × 3 = 2² × 3، تعریفی از x² − 9 به صورت (x−3)(x+3) تجزیه می‌شود. تفکر تجزیه به عوامل اول به طور مستقیم به تحویل دادن تعریفی از جبر منتقل می‌شود.

عددهای اول و توزیع آنها

عددهای اول خودشان بسیار جالب هستند. عددهای اول اولی 2، 3، 5، 7، 11، 13، 17، 19، 23، 29، 31، 37، 41، 43، 47 ... با افزایش عددها، عددهای اول کمتر می‌شوند، اما هرگز متوقف نمی‌شوند. اقلیدس این موضوع را بیش از 2،300 سال پیش با یک برهان ساده و شگفت‌انگیز ثابت کرد.

نظریه عددهای اول (با اثبات مستقل هادامار و دو لا واله پوسین در سال 1896) می‌گوید که تعداد عددهای اول تا n تقریباً n / ln(n) است. این یعنی تقریباً 1 در هر ln(n) عددهای نزدیک به n عدد اول است — نزدیک به 1 میلیون، حدود 1 در 14 عدد اول است؛ نزدیک به 1 میلیارد، حدود 1 در 21 عدد اول است.

دسته‌بندی‌های خاصی از عددهای اول شامل: عددهای اول دوقلو (دو عدد اول با اختلاف 2: 11 & 13، 17 & 19)، عددهای اول مرسن (با شکل 2^p − 1؛ بزرگترین عدد اول شناخته شده تا سال 2024 یک عدد اول مرسن با بیش از 41 میلیون رقم است)، و عددهای اول ژرمن (p که 2p+1 نیز عدد اول است). آیا تعداد زیادی عدد اول دوقلو وجود دارد یا خیر، یک مسئله باز است — حدس عددهای اول دوقلو.

الگوریتم های فاکتوراسیون: از روش تقسیم آزمایشی تا روش های پیشرفته

برای اعداد کوچک (کمتر از یک میلیارد)، تقسیم آزمایشی سریع و مستقیم است: سعی کنید با 2 شروع کنید و سپس تمام اعداد فرد تا ریشه مربع n را امتحان کنید. این کالبکر از این روش استفاده می کند و اعداد تا ده‌ها میلیارد را در میلی ثانیه پردازش می کند.

برای اعداد بزرگتر، ریاضیدانان روش های پیچیده تری توسعه داده اند. روش فاکتوراسیون فرما توسط بیان کردن n به عنوان تفاضل دو مربع: n = a² − b² = (a+b)(a−b) کار می کند. الگوریتم rho پالارد (1975) یک روش احتمالی است که برای اعداد با عوامل کوچک کارآمد است؛ این روش در زمان O(n^(1/4)) اجرا می شود و در بسیاری از کاربردهای واقعی استفاده می شود.

الگوریتم فاکتوراسیون عمومی قدرتمندترین شناخته شده است که سیگما (GNFS) است که دارای زمان اجرا زیر اکسپونانسی است. GNFS برای فاکتور کردن RSA-768 (یک عدد چالش 768 بیتی RSA) در سال 2009 استفاده شد که نیاز به equivalent 2,000 سال زمان پردازش CPU تک هسته ای در سراسر بسیاری از کامپیوترها داشت. RSA-2048 به عنوان غیرممکن به نظر می رسد که با کامپیوترهای کلاسیک فاکتور شود.

کامپیوترهای کوانتومی نظریاً می توانند اعداد بزرگ را با استفاده از الگوریتم شور (1994) فاکتور کنند که در زمان چندجمله ای اجرا می شود. این دلیل است که رمزنگاری پس از کوانتوم — توسعه رمزنگاری که مقاوم در برابر حملات کوانتومی است — یک منطقه تحقیقاتی مهم در حال حاضر است.

فاکتوراسیون اولی در آموزش و ریاضیات رقابتی

فاکتوراسیون اولی یک مهارت اساسی در ریاضیات متوسط و دبیرستان است. این توانایی را به دانش آموزان می دهد تا تقسیمات را ساده کنند، GCD و LCM را پیدا کنند، با مربع های کامل و کوبه های کامل کار کنند و قوانین تقسیم پذیری را درک کنند. مهارت در فاکتوراسیون همچنین آگاهی را برای جبر ایجاد می کند، جایی که فاکتور کردن چند جمله ای یک مهارت مشابه است که به جملات جایگزین شده است.

در ریاضیات رقابتی (AMC، AIME، المپیادها)، مسائل فاکتوراسیون اولی thường ظاهر می شوند. یک مثال کلاسیک: "چندین عدد صحیح مثبت دارد که 1,000,000 را دارد؟" از آنجایی که 1,000,000 = 10⁶ = (2 × 5)⁶ = 2⁶ × 5⁶، پاسخ این است (6+1)(6+1) = 49. این نوع مسائل دانش آموزانی را که به طور چندگانه فکر می کنند، پاداش می دهند نه به طور جمعی.

درک توان ها در فاکتوراسیون های اولی همچنین مفاهیم مانند مربع های کامل (همه توان های زوج)، کوبه های کامل (همه توان های سه گانه) و کوچکترین مربع کامل که یک عدد خاص چندگانه است را باز می کند — همه اینها موضوعات آزمون هستند.

استفاده از فاکتوراسیون اول برای ساده‌سازی تقسیمات و ریشه‌های صفر

فاکتوراسیون اول روش سیستماتیک برای ساده‌سازی تقسیمات است. برای ساده‌سازی 84/126، فاکتوریزه کنید: 84 = 2² × 3 × 7 و 126 = 2 × 3² × 7. GCD = 2 × 3 × 7 = 42. بنابراین 84/126 = (84÷42)/(126÷42) = 2/3. هیچ پیش‌بینی ضروری نیست — فاکتوراسیون اول نشان‌دهنده GCD را مستقیماً نشان می‌دهد.

برای ساده‌سازی ریشه‌های صفر، فاکتوراسیون اول نیز قدرتمند است. برای ساده‌سازی √180: 180 = 2² × 3² × 5. زوج‌های اول از ریشه صفر خارج می‌شوند: √(2² × 3² × 5) = 2 × 3 × √5 = 6√5. برای ریشه‌های کوبه‌ای: ∛(108) = ∛(2² × 3³) = 3∛4. گروه‌های سه‌گانه از ریشه کوبه‌ای خارج می‌شوند.

در ریاضیات رقابتی، این تکنیک‌ها به طور فراگیر ظاهر می‌شوند. نوع مسأله رایج: "فIND کوچکترین عدد n که 360n یک مربع کامل باشد." از آنجایی که 360 = 2³ × 3² × 5، نیاز است که تمام توان‌ها حتی باشند. در حال حاضر 2 دارای توان 3 (نابرابر) و 5 دارای توان 1 (نابرابر) است. بنابراین n باید حداقل 2¹ × 5¹ = 10 را تأمین کند. پاسخ: n = 10. چک: 360 × 10 = 3600 = 60². ✓

تعداد عوامل، اعداد کامل و مجموع عوامل

فاکتوراسیون اول تحلیل کامل عوامل یک عدد را باز می‌کند. اگر n = p₁^a × p₂^b × p₃^c، سپس تعداد عوامل τ(n) = (a+1)(b+1)(c+1) است. مجموع عوامل σ(n) = ((p₁^(a+1)−1)/(p₁−1)) × ((p₂^(b+1)−1)/(p₂−1)) × ...

برای 12 = 2² × 3: τ(12) = (2+1)(1+1) = 6 (عوامل: 1،2،3،4،6،12). σ(12) = ((2³−1)/(2−1)) × ((3²−1)/(3−1)) = 7 × 4 = 28. یک عدد کامل برابر با مجموع عوامل خود (عوامل غیر خود را شامل نمی‌شود) است. σ(n) − n = n → σ(n) = 2n. برای 6 = 2 × 3: σ(6) = 12 = 2×6. ✓ 6 کامل است! برای 28 = 2² × 7: σ(28) = 56 = 2×28. ✓ 28 کامل است!

تا سال 2024، 51 عدد کامل شناخته شده است، همه آنها زوج هستند، همه از نوع 2^(p−1)(2^p−1) هستند جایی که 2^p−1 یک عدد میرسن است. آیا اعداد کامل ناقص وجود دارد یا خیر، یکی از مسائل باز در ریاضیات است — هیچ عدد کامل ناقصی پیدا نشده است، اما هیچ عدد کامل ناقصی ثابت نشده است.

مرجع سریع: قوانین تجزیه

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

مرور کردن این قوانین باعث می‌شود فاکتوریزه کردن به سرعت افزایش یابد. برای 2،520: زوج است (2)، مجموع رقم‌ها 9 (3)، آخر 0 (5) است. با شروع از 2: 2520÷2=1260÷2=630÷2=315÷3=105÷3=35÷5=7. بنابراین 2520 = 2³ × 3² × 5 × 7 — یک عدد بسیار مرکب با 48 عامل.