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

প্রতিনিধির নাম

আপডেট সময় : ০৩:০৬:৩৭ অপরাহ্ন, বুধবার, ২১ অক্টোবর ২০২৬ ০ বার পড়া হয়েছে

আমাদের সর্বশেষ নিউজ পেতে ক্লিক করুন গুগল নিউজ (Google News) ফিডটি

‘অর্ডারের আইডিয়াটা দারুণ লেগেছিল ভাইয়া, কিন্তু সব সংখ্যার অর্ডার কি একই মডুলোর জন্য সব সময় একই হবে? যেমন 7 মডুলোতে 2-এর অর্ডার কত?’ রাতুল বলল।

অঙ্ক ভাইয়া মুচকি হাসলেন। তিনি রাতুলের খাতায় লিখলেন:

2 1=2≡2 (mod 7), 2 2=4≡4 (mod 7), 2 3=8≡1 (mod 7)। ‘দেখেছিস? 2-এর ক্ষেত্রে কিন্তু মাত্র 3 নম্বর ধাপেই ভাগশেষ 1 চলে এসেছে! অর্থাৎ ord 7(2) = 3’, অঙ্ক ভাইয়া ব্যাখ্যা করলেন। ‘এখান থেকে আসে Fermat’s Little Theorem। এই থিওরেম বলে যে যদি p একটি মৌলিক সংখ্যা হয়, তবে যেকোনো সংখ্যা a-এর জন্য, যদি gcd(a, p) = 1 হয়, a p–1 ≡ 1 (mod p) হবেই। অর্থাৎ মডুলোটি মৌলিক সংখ্যা হলে কোনো সংখ্যার অর্ডার সর্বোচ্চ (p–1) হতে পারে।’

‘তার মানে 7 যেহেতু একটি মৌলিক সংখ্যা, এর জন্য যেকোনো সংখ্যার সর্বোচ্চ সম্ভাব্য অর্ডার হতে পারে 7-1 = 6’, রাতুল বলল।

‘একদম তা–ই! আর যে সংখ্যার অর্ডার ঠিক এই সর্বোচ্চ সীমা স্পর্শ করতে পারে, তাকেই বলা হয় প্রিমিটিভ রুট (Primitive Root)।

অর্থাৎ কোনো সংখ্যা g যদি একটি মৌলিক সংখ্যা p-এর মডুলোতে এমনভাবে চক্র তৈরি করে, যেন তার অর্ডার ঠিক সর্বোচ্চ সম্ভাব্য অর্ডারের সমান হয়, অর্থাৎ p–1 হয়, তবে g-কে p-এর একটি Primitive Root বলা হয়।

ord p(g) = p–1.

‘তবে এখানে একটা বিশাল ‘কিন্তু’ আছে রাতুল! এই প্রিমিটিভ রুট কিন্তু সব সংখ্যার জন্য কাজ করে না। কিছু বিশেষ সংখ্যার জন্য কাজ করে।’ রাতুল জিজ্ঞেস করল, ‘কোন সংখ্যার জন্য কাজ করবে না ভাইয়া?’

‘চল একটা উদাহরণ দেখি,’ অঙ্ক ভাইয়া খাতায় n = 8 লিখলেন। ‘মডুলো 8-এর দুনিয়ায় 8-এর চেয়ে ছোট ও এর সঙ্গে সহমৌলিক সংখ্যা কোনগুলো?’

‘1, 3, 5, আর 7,’ রাতুল ঝটপট বলল। ‘তার মানে মোট 4টি সংখ্যা। অয়লারের Totient ফাংশন অনুযায়ী φ(8) = 4।’

‘ঠিক। তাহলে নিয়ম অনুযায়ী, যদি 8-এর কোনো প্রিমিটিভ রুট থাকত, তবে তার অর্ডার হওয়া উচিত ছিল সর্বোচ্চ সম্ভাব্য, অর্থাৎ ঠিক φ(8)=4। কিন্তু তুই যদি 3, 5, 7-এর পাওয়ার করিস, দেখবি চমৎকার এক কাণ্ড:’

3 2 = 9 ≡ 1 (mod 8) ⇒ ord 8(3) = 2

5 2 = 25 ≡ 1 (mod 8) ⇒ ord 8(5) = 2

7 2 = 49 ≡ 1 (mod 8) ⇒ ord 8(7) = 2

‘দেখেছিস? কোনো সংখ্যার অর্ডারই কিন্তু 4 পর্যন্ত পৌঁছাতে পারল না! সবাই মাঝপথেই, পাওয়ার 2–এ, 1 হয়ে বসে আছে। কোনো পূর্ণ চক্র তৈরি হলো না। তাই যৌগিক সংখ্যা 8-এর কোনো প্রিমিটিভ রুট থাকা সম্ভব নয়। এটা প্রমাণ করা হয়েছে যে প্রিমিটিভ রুট থাকবে যদি এবং কেবল যদি n–এর মান 2, 4, p k অথবা 2 p k হয়, যেখানে p একটি বিজোড় মৌলিক সংখ্যা।’

‘ভাইয়া, প্রিমিটিভ রুট দিয়ে একটা সমস্যা সমাধান করে দেখাও না!’ রাতুল চোখ বড় বড় করল।

‘আচ্ছা, একটা দারুণ প্রবলেম দেখ,’ অঙ্ক ভাইয়া হাসলেন। ‘ধর তোকে প্রমাণ করতে দিল: যদি p একটি মৌলিক সংখ্যা হয়, তবে

1 2 ⋅ 2 2 ⋅ 3 2⋯(p–1 ) 2 ≡ 1 (mod p)

হবে কি না? আমরা আজ প্রিমিটিভ রুট ব্যবহার করে উইলসনস থিওরেম (Wilson’s Theorem) প্রমাণ করব, যা বলে:

(p–1) ! ≡ - 1 (mod p).

ধরলাম p একটি বিজোড় মৌলিক সংখ্যা (p=2 হলে 1!=1 ≡ -1 (mod 2) এমনিতেই সত্য) এবং g তার একটি প্রিমিটিভ রুট। g এর অর্ডার p–1 বলে g 1, g 2, g 3, … , g p–1–এর ভাগশেষগুলো সব আলাদা, তাই এরা আসলে ঘুরিয়ে-ফিরিয়ে 1, 2, 3, … , p–1 সংখ্যাগুলোই।

তাহলে আমরা যদি 1 থেকে p–1 পর্যন্ত সব কটি সংখ্যা গুণ করি, তা আসলে g-এর পাওয়ারগুলো গুণ করার সমান!’

রাতুলের চোখ চকচক করে উঠল, ‘ওহ! তার মানে:’

(p–1) != 1 ⋅ 2 ⋅ 3⋯(p–1) ≡ g 1 ⋅ g 2 ⋅ g 3⋯g p-1 (mod p).

‘একদম ঠিক!’ অঙ্ক ভাইয়া সূচকের নিয়ম বসালেন। ‘গুণের সময় পাওয়ারগুলো যোগ হয়ে যায়, তা–ই:’

g 1 ⋅ g 2 ⋅ g 3⋯g p–1 = g 1+2+3+⋯+(p–1) = g p(p-1) _ 2 .

এখন, আমাদের হিসাব করতে হবে g p(p–1) _ 2  (mod p)।

আমরা জানি ফার্মার লিটল থিওরেম অনুযায়ী,

g p–1 ≡ 1 (mod p).

তাহলে বীজগণিতের নিয়ম অনুযায়ী,

(g (p–1) _ 2 ) 2 ≡ 1 (mod p).

যেহেতু p মৌলিক, তাই কোনো সংখ্যার বর্গ 1 হলে সংখ্যাটি নিজে 1 অথবা -1 হতে পারে, এবং g একটি প্রিমিটিভ রুট হওয়ায় তার পাওয়ার

(p–1)-এর আগে কখনো 1 হওয়া সম্ভব নয়, কারণ তার অর্ডারই তো

p–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).

রাতুল খাতার দিকে তাকিয়ে তাজ্জব বনে গেল, ‘উফ ভাইয়া! এত বড় একটা প্রমাণ, প্রিমিটিভ রুটের এই পাওয়ারের ধারা দিয়ে এক লাইনে

হয়ে গেল!’

অঙ্ক ভাইয়া হেসে রাতুলের পিঠ চাপড়ে দিলেন, ‘এটাই প্রিমিটিভ রুটের আসল ক্ষমতা। সে হলো মৌলিক সংখ্যার দুনিয়ার সেই চাবিকাঠি, যা একাই পুরো সিস্টেমের সব ভাগশেষের তালা খুলে দিতে পারে!’

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