ডিভিজিবিলিটি ও প্রাইম নাম্বার
এই পাঠে যা শিখবেন
- বিভাজ্যতার ($a \mid b$) আনুষ্ঠানিক সংজ্ঞা ও এর মৌলিক ধর্মসমূহ
- প্রাইম ও কম্পোজিট সংখ্যার পার্থক্য, এবং কেন ১ কোনোটিই নয়
- Fundamental Theorem of Arithmetic — unique prime factorization
- ইউক্লিডের ক্লাসিক প্রমাণ: প্রাইম সংখ্যা অসীম সংখ্যক আছে
- Python দিয়ে primality test ও prime factorization বাস্তবায়ন
১ · বিভাজ্যতা (Divisibility) কী?
নাম্বার থিওরির সবচেয়ে মৌলিক সম্পর্কটি হলো DivisibilityDivisibilityদুটি পূর্ণসংখ্যার মধ্যে একটি সম্পর্ক — $a$ যদি $b$-কে ভাগ করে (কোনো ভাগশেষ ছাড়াই), তাহলে লেখা হয় $a \mid b$।। আনুষ্ঠানিকভাবে —
$$a \mid b \iff \exists k \in \mathbb{Z} \text{ এমন যে } b = ak$$
অর্থাৎ $b$-কে $a$ দিয়ে ভাগ করলে ভাগশেষ ঠিক শূন্য হয়। যেমন $3 \mid 12$, কারণ $12 = 3 \times 4$। কিন্তু $3 \nmid 10$, কারণ এমন কোনো পূর্ণসংখ্যা $k$ নেই যেন $10 = 3k$।
দুটি ধর্ম বারবার ব্যবহার হবে পুরো মডিউলে —
- যোগের ধর্ম: যদি $a \mid b$ এবং $a \mid c$, তাহলে $a \mid (b + c)$। কারণ $b = ak_1$, $c = ak_2$ হলে $b+c = a(k_1+k_2)$ — যা $a$-এর গুণিতক।
- গুণের ধর্ম: যদি $a \mid b$, তাহলে যেকোনো পূর্ণসংখ্যা $c$-এর জন্য $a \mid bc$। কারণ $b=ak$ হলে $bc = a(kc)$।
২ · প্রাইম ও কম্পোজিট সংখ্যা
একটি প্রাইম সংখ্যাPrime Number১-এর চেয়ে বড় একটি পূর্ণসংখ্যা যার ঠিক দুটি পজিটিভ ডিভাইজর আছে — ১ এবং সংখ্যাটি নিজে। যেমন 2, 3, 5, 7, 11, ... হলো এমন একটি পূর্ণসংখ্যা $n>1$ যার পজিটিভ ডিভাইজর ঠিক দুটি — $1$ এবং $n$ নিজে। যে সংখ্যার $2$-এর বেশি ডিভাইজর আছে তাকে কম্পোজিট (Composite) বলা হয়।
লক্ষ করুন — ১ প্রাইমও নয়, কম্পোজিটও নয়। এটি নিছক একটি নিয়ম নয়; ১-কে প্রাইম ধরলে Fundamental Theorem of Arithmetic (নিচে দেখুন) ভেঙে পড়ত, কারণ তখন $12 = 2^2 \times 3 = 1 \times 2^2 \times 3 = 1^{100} \times 2^2 \times 3$ — অসীম সংখ্যক "ভিন্ন" ফ্যাক্টরাইজেশন তৈরি হতো। তাই সংজ্ঞাটি ইচ্ছাকৃতভাবে ১-কে বাদ রাখে যেন unique factorization সত্য থাকে।
import math
def is_prime(n):
if n < 2:
return False
for d in range(2, math.isqrt(n) + 1):
if n % d == 0:
return False
return True
def factorize(n):
factors = {}
d = 2
remaining = n
while d * d <= remaining:
while remaining % d == 0:
factors[d] = factors.get(d, 0) + 1
remaining //= d
d += 1
if remaining > 1:
factors[remaining] = factors.get(remaining, 0) + 1
return factors
print("is_prime(97):", is_prime(97))
print("is_prime(91):", is_prime(91), "(91 = 7 × 13)")
n = 360
f = factorize(n)
print(f"{n}-এর প্রাইম ফ্যাক্টরাইজেশন:", f)
# ফ্যাক্টরাইজেশন থেকে সংখ্যাটি আবার তৈরি করে যাচাই
rebuilt = 1
for base, exp in f.items():
rebuilt *= base ** exp
print("পুনর্গঠিত মান:", rebuilt, "== আসল মান?", rebuilt == n)math.isqrt(n) ব্যবহার করে ট্রায়াল ডিভিশন শুধু $\sqrt{n}$ পর্যন্ত চালানো হয় — কারণ যদি $n = a \times b$ হয়
এবং $a \le b$, তাহলে $a \le \sqrt{n}$ হতেই হবে। ফলে $\sqrt{n}$-এর বেশি কোনো ডিভাইজর চেক করার দরকার নেই।
$360 = 2^3 \times 3^2 \times 5$ — কোড আউটপুট এই ফ্যাক্টরাইজেশন নিশ্চিত করবে।
৩ · Fundamental Theorem of Arithmetic
এই উপপাদ্যটি নাম্বার থিওরির ভিত্তিপ্রস্তর —
$1$-এর চেয়ে বড় প্রতিটি পূর্ণসংখ্যাকে প্রাইম সংখ্যার গুণফল হিসেবে লেখা যায়, এবং এই লেখাটি (গুণনের ক্রম বাদ দিলে) একমাত্র (unique)।
অস্তিত্ব (existence) সহজেই বোঝা যায় স্ট্রং ইনডাকশন দিয়ে (L06-এ শেখা) — যদি $n$ প্রাইম হয়, তাহলে সেটাই তার ফ্যাক্টরাইজেশন। যদি $n$ কম্পোজিট হয়, তাহলে $n = a \times b$ যেখানে $1 < a, b < n$ — এবং ইনডাকশন হাইপোথিসিস অনুযায়ী $a$ ও $b$ উভয়েরই প্রাইম ফ্যাক্টরাইজেশন আছে, যা একসাথে করলে $n$-এর ফ্যাক্টরাইজেশন পাওয়া যায়।
একমাত্রতা (uniqueness) প্রমাণ করা বেশি গভীর — এর মূল হাতিয়ার হলো ইউক্লিডের লেমা (যদি একটি প্রাইম $p$ কোনো গুণফল $ab$-কে ভাগ করে, তাহলে $p$ অবশ্যই $a$ কে অথবা $b$ কে ভাগ করবে)। এই লেমার সম্পূর্ণ প্রমাণ এই পাঠের পরিসরের বাইরে, কিন্তু এটাই সেই টুল যা নিশ্চিত করে দুটি ভিন্ন প্রাইম ফ্যাক্টরাইজেশন কখনো একই সংখ্যা দিতে পারে না।
৪ · ইউক্লিডের প্রমাণ — প্রাইম সংখ্যা অসীম
প্রায় ২৩০০ বছর আগে, ইউক্লিড একটি অসাধারণ সংক্ষিপ্ত প্রমাণ দিয়েছিলেন যে প্রাইম সংখ্যা কখনো শেষ হয় না — এবং এটি proof by contradiction-এর (L05-এ শেখা) একটি নিখুঁত উদাহরণ।
ধরা যাক, বিপরীতে, প্রাইম সংখ্যা সসীম সংখ্যক — মোট $n$টি: $p_1, p_2, \ldots, p_n$। এখন এই সংখ্যাটি তৈরি করি —
$$N = p_1 \times p_2 \times \cdots \times p_n + 1$$
লক্ষ করুন, তালিকার প্রতিটি $p_i$ দিয়ে $N$-কে ভাগ করলে ভাগশেষ সবসময় $1$ হবে (কারণ $N$ হলো $p_i$-এর গুণিতকের সাথে শুধু $+1$)। তাই তালিকার কোনো প্রাইম $N$-কে ভাগ করে না।
কিন্তু $N > 1$ যেকোনো পূর্ণসংখ্যার হয় নিজেই একটি প্রাইম, নয়তো তার অন্তত একটি প্রাইম ফ্যাক্টর আছে (Fundamental Theorem of Arithmetic থেকে)। যেহেতু তালিকার কোনো প্রাইম $N$-কে ভাগ করে না, তাই $N$-এর প্রাইম ফ্যাক্টরটি অবশ্যই $p_1, \ldots, p_n$ তালিকার বাইরের একটি নতুন প্রাইম — যা আমাদের ধারণার সাথে সরাসরি বিরোধিতা করে যে তালিকাটি সব প্রাইম ধারণ করে।
এই বিরোধিতা প্রমাণ করে — আমাদের প্রাথমিক ধারণা ("প্রাইম সসীম") ভুল ছিল। সুতরাং প্রাইম সংখ্যা অসীম। $\blacksquare$
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ ইউক্লিডের প্রমাণে $N = p_1 p_2 \cdots p_n + 1$ কি নিজে সবসময় প্রাইম হয়? না হলে প্রমাণ কীভাবে তবুও কাজ করে?
না, $N$ সবসময় প্রাইম নয়। উদাহরণ: $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509$ — কম্পোজিট, প্রাইম নয়। কিন্তু প্রমাণটি এতে নির্ভর করে না যে $N$ প্রাইম হবে — এটি শুধু নির্ভর করে এই সত্যের উপর যে $N$-এর অন্তত একটি প্রাইম ফ্যাক্টর থাকবেই (Fundamental Theorem of Arithmetic থেকে), এবং সেই ফ্যাক্টরটি তালিকার $p_1,\ldots,p_n$-এর কোনোটিই হতে পারে না (কারণ প্রতিটি দিয়ে ভাগ করলে ভাগশেষ ১)। তাই সেটি অবশ্যই একটি নতুন প্রাইম — যা যথেষ্ট বিরোধিতা তৈরি করে।
প্র ০২ কেন $1$-কে প্রাইম হিসেবে গণ্য করা হয় না — এটি কি শুধু একটি নিয়ম, নাকি এর পেছনে গাণিতিক প্রয়োজনীয়তা আছে?
এটি নিছক প্রথা নয় — এটি Fundamental Theorem of Arithmetic-এর একমাত্রতা (uniqueness) রক্ষা করার জন্য প্রয়োজনীয়। যদি ১ প্রাইম হতো, তাহলে $12 = 2^2 \times 3$ একইসাথে $1 \times 2^2 \times 3$, $1^2 \times 2^2 \times 3$, $1^{1000} \times 2^2 \times 3$ ইত্যাদি অসীম সংখ্যক "ভিন্ন" ফ্যাক্টরাইজেশন হিসেবে লেখা যেত — কারণ ১-এর যেকোনো ঘাত গুণফলে কোনো পরিবর্তন আনে না। প্রাইম সংজ্ঞা থেকে ১-কে বাদ দিলে ফ্যাক্টরাইজেশন সত্যিকার অর্থে একমাত্র থাকে।
প্র ০৩ Trial division দিয়ে primality চেক করার সময় কেন শুধু $\sqrt{n}$ পর্যন্ত চেক করলেই যথেষ্ট — পুরো $n$ পর্যন্ত কেন নয়?
যদি $n = a \times b$ হয় এবং $a \le b$ হয়, তাহলে অবশ্যই $a \le \sqrt{n}$ হতে হবে — কারণ যদি $a$ ও $b$ উভয়েই $\sqrt{n}$-এর বেশি হতো, তাহলে $a \times b$ হতো $\sqrt{n} \times \sqrt{n} = n$-এর চেয়ে বড়, যা সম্ভব নয়। তাই যদি $n$-এর কোনো ফ্যাক্টর থাকে, তার অন্তত একটি ফ্যাক্টর অবশ্যই $\sqrt{n}$ বা তার কম হবে। ফলে $\sqrt{n}$ পর্যন্ত চেক করে কিছু না পেলে নিশ্চিত হওয়া যায় $n$ প্রাইম — বড় সংখ্যার জন্য এটি বিশাল সময় বাঁচায় (যেমন $n=10^{12}$ হলে $n$ পর্যন্ত নয়, মাত্র $10^6$ পর্যন্ত চেক করলেই চলবে)।
অনুশীলন
-
হাতে হিসাব করুন: $84$-এর প্রাইম ফ্যাক্টরাইজেশন বের করুন (হাতে, ছোট প্রাইম দিয়ে ভাগ করতে করতে) এবং তারপর উপরের কোড সেলের
factorize()ফাংশনে $n=84$ বসিয়ে মিলিয়ে দেখুন।$84 = 2 \times 42 = 2 \times 2 \times 21 = 2^2 \times 3 \times 7$। যাচাই: $4 \times 3 \times 7 = 84$ ✓। কোড আউটপুট
{2: 2, 3: 1, 7: 1}দেখাবে। -
যুক্তি দিন: ইউক্লিডের প্রমাণের কৌশল ব্যবহার করে প্রমাণ করুন — যদি $p_1=2,p_2=3,p_3=5,p_4=7$ শুধু চারটি প্রাইম থাকত, তাহলে $N=2\times3\times5\times7+1$ থেকে কীভাবে একটি নতুন প্রাইমের অস্তিত্ব প্রমাণিত হয়?
$N = 210+1=211$। এটিকে $2,3,5,7$ কোনোটি দিয়েই নিঃশেষে ভাগ করা যায় না (প্রতিটির ভাগশেষ $1$)। যাচাই করলে দেখা যায় $211$ নিজেই একটি প্রাইম — যা তালিকার বাইরের পঞ্চম প্রাইম। এটি নিশ্চিত করে তালিকা $\{2,3,5,7\}$ সম্পূর্ণ ছিল না, ঠিক যেমন প্রমাণ দাবি করে।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৪৪টি পাঠ M5-এর বাকি পাঠগুলো — GCD, মডুলার এরিথমেটিক, RSA — এই মডিউলেই আছে।
- পাঠ ২৫ · GCD, LCM ও ইউক্লিডিয়ান অ্যালগরিদম পরবর্তী পাঠ দুটি সংখ্যার গরিষ্ঠ সাধারণ গুণনীয়ক দ্রুততম উপায়ে বের করার অ্যালগরিদম।
- সব Courses দেখুন ABCL TECH C, C++, Python, Java, JavaScript, DSA, DBMS, HTML & CSS ও Discrete Mathematics — সব এক জায়গায়।