প্রিমিটিভ রুট: মৌলিক সংখ্যার একচ্ছত্র অধিপতি

মডুলার এরথমেটিকে বিভিন্ন সংখ্যার অর্ডারের ধারণা বেশ গুরুত্বপূর্ণ। মডুলো 7-এর ক্ষেত্রে 2-এর হিসাব দেখা যাক। এখানে 2¹= 2, 2²= 4 এবং 2³= 8 ≡ 1 (mod 7)। দেখা যাচ্ছে, মাত্র তিন ধাপেই ভাগশেষ 1 চলে আসছে, অর্থাৎ ord₇(2) = 3। এই ধারণার সঙ্গেই জড়িয়ে রয়েছে ফার্মার লিটল থিওরেম (Fermat’s Little Theorem)। এই নিয়ম অনুযায়ী, p যদি একটি মৌলিক সংখ্যা হয় এবং gcd(a, p) = 1 হয়, তবে a^{p – 1}≡ 1 (mod p) হবে। এর অর্থ হলো, মডুলোটি মৌলিক হলে যেকোনো সংখ্যার সর্বোচ্চ সম্ভাব্য অর্ডার হতে পারে (p – 1)। উদাহরণস্বরূপ, 7 একটি মৌলিক সংখ্যা হওয়ায় এর জন্য যেকোনো সংখ্যার অর্ডারের সর্বোচ্চ সীমা 7 – 1 = 6 হতে পারে। রাতুল জিজ্ঞেস করল, ‘কোন সংখ্যার জন্য কাজ করবে না ভাইয়া?’।

যে সংখ্যাটি তার অর্ডারের এই সর্বোচ্চ সীমা স্পর্শ করতে পারে, তাকেই প্রিমিটিভ রুট (Primitive Root) বলা হয়। অর্থাৎ, g যদি p মডুলোতে এমন একটি চক্র তৈরি করে যেন তার অর্ডার ঠিক সর্বোচ্চ সম্ভাব্য সীমা (p – 1)-এর সমান হয়, তবে g-কে p-এর একটি প্রিমিটিভ রুট বলা হয়। তবে প্রিমিটিভ রুট সব সংখ্যার জন্য বিদ্যমান থাকে না। উদাহরণ হিসেবে n = 8 ধরা যাক। 8-এর চেয়ে ছোট ও সহমৌলিক সংখ্যাগুলো হলো 1, 3, 5 ও 7—যার মোট সংখ্যা 4টি। অয়লারের টোটেন্ট ফাংশন অনুযায়ী φ(8) = 4। যদি 8-এর কোনো প্রিমিটিভ রুট থাকত, তবে তার অর্ডার হওয়া উচিত ছিল 4। কিন্তু বাস্তব হিসাব অনুযায়ী কিন্তু তুই যদি ​3, 5, 7​-এর পাওয়ার করিস, দেখবি চমৎকার এক কাণ্ড:’।

• 3²= 9 ≡ 1 (mod 8) ⇒ ord₈(3) = 2
• 5²= 25 ≡ 1 (mod 8) ⇒ ord₈(5) = 2
• 7²= 49 ≡ 1 (mod 8) ⇒ ord₈(7) = 2

দেখা যাচ্ছে, কোনো সংখ্যার অর্ডারই 4 পর্যন্ত পৌঁছায় না, বরং ঘাত 2-তেই সবাই 1 হয়ে যায়। ফলে কোনো পূর্ণ চক্র গঠিত হয় না এবং যৌগিক সংখ্যা 8-এর কোনো প্রিমিটিভ রুট থাকে না। গাণিতিকভাবে প্রমাণিত যে, প্রিমিটিভ রুট কেবল তখনই বিদ্যমান থাকে যখন n-এর মান 2, 4, p^kঅথবা 2 p^kহয় (যেখানে p একটি বিজোড় মৌলিক সংখ্যা)।

প্রিমিটিভ রুট ব্যবহার করে গাণিতিক প্রমাণ

প্রিমিটিভ রুটের সাহায্যে গুরুত্বপূর্ণ গাণিতিক সমস্যা সমাধান করা যায়। যেমন: p একটি মৌলিক সংখ্যা হলে প্রমাণ করা সম্ভব যে 1²⋅ 2²⋅ 3²⋯(p – 1)²≡ 1 (mod p)। এর অংশ হিসেবে উইলসনস থিওরেম (Wilson’s Theorem) প্রমাণ করা যায়, যা হলো (p – 1)! ≡ -1 (mod p)।

ধরা যাক p একটি বিজোড় মৌলিক সংখ্যা এবং g তার একটি প্রিমিটিভ রুট। g-এর অর্ডার (p – 1) হওয়ায় g¹g²g³…, g^{p – 1}এর ভাগশেষগুলো আলাদা এবং ঘুরিয়ে-ফিরিয়ে এরা 1, 2, 3, …, p – 1 সংখ্যাগুলোকেই নির্দেশ করে। সুতরাং 1 থেকে (p – 1) পর্যন্ত সংখ্যাগুলোর গুণফল মূলত g-এর সূচক বা পাওয়ারগুলোর গুণফলের সমান। তাহলে আমরা যদি ​1​ থেকে ​p – 1​ পর্যন্ত সব কটি সংখ্যা গুণ করি, তা আসলে ​g​-এর পাওয়ারগুলো গুণ করার সমান!’।

সূচকের নিয়মে গুণের সময় পাওয়ারগুলো যোগ হয়

• (p – 1)! = 1 ⋅ 2 ⋅ 3⋯(p – 1) ≡ g¹⋅ g²⋅ g³⋯g^p-1(mod p)
• g¹⋅ g²⋅ g³⋯g^{p – 1}= g^{1+2+3+⋯+(p – 1)}= g^p(p-1)/2

এখন ফার্মার লিটল থিওরেম অনুযায়ী (g^{(p – 1)/2})²≡ 1 (mod p)। चूंकि p একটি মৌলিক সংখ্যা, তাই কোনো সংখ্যার বর্গ 1 হলে সংখ্যাটি নিজে 1 অথবা -1 হতে পারে। কিন্তু g একটি প্রিমিটিভ রুট হওয়ায় power (p – 1)-এর আগে ভাগশেষ 1 হতে পারে না। তাই g^{(p – 1)/2}≡ -1 (mod p)।

এই মানটি মূল সমীকরণে বসালে পাওয়া যায়: (p – 1)! ≡ (g^{(p – 1)/2})^p≡ (-1)^p(mod p)। যেহেতু p বিজোড়, তাই (-1)^p= -1 হয়। ফলে পুরো সমীকরণটি বর্গ করলে দাঁড়ায়: 1²⋅ 2²⋅ 3²⋯(p – 1)²= ((p – 1)!)²≡ (-1)²= 1 (mod p)। এভাবে প্রিমিটিভ রুটের ঘাতের ধারা ব্যবহার করে এক লাইনেই জটিল সমস্যার সহজ সমাধান মেলে।

সহযোগিতায়: বাংলাদেশ গণিত অলিম্পিয়াড কমিটি

গুরুত্বপূর্ণ তথ্য

• রাতুলের চোখ চকচক করে উঠল, ‘ওহ! তার মানে:’।
• তাহলে আমাদের মূল সমীকরণে মানটি বসিয়ে পাই।
• রাতুল খাতার দিকে তাকিয়ে তাজ্জব বনে গেল, ‘উফ ভাইয়া! এত বড় একটা প্রমাণ, প্রিমিটিভ রুটের এই পাওয়ারের ধারা দিয়ে এক লাইনে।
• অঙ্ক ভাইয়া হেসে রাতুলের পিঠ চাপড়ে দিলেন, ‘এটাই প্রিমিটিভ রুটের আসল ক্ষমতা। সে হলো মৌলিক সংখ্যার দুনিয়ার সেই চাবিকাঠি, যা একাই পুরো সিস্টেমের সব ভাগশেষের তালা খুলে দিতে পারে!’।