Multiplicative Cycles b, b², b³, ... (mod N) and Order

হ্যালো! :D

আচ্ছা, প্রথমে এই আর্টিকেলটার উদ্দেশ্যটা বলি,

এই আর্টিকেলে আমরা দেখাব যে, "দুটি সহমৌলিক স্বাভাবিক সঙ্খ্যা $n ,a$ এর জন্য সবসময়ই $n \mid ϕ(a^n - 1)$"

খেয়াল করলে দেখবে যে, আমরা সাধারণত যেসব নিয়মে বিভাজ্যতার প্রব্লেমগুলো সল্ভ করি, এটি তার কোনোটির মধ্যেই পড়ে না। এক্ষেত্রে যে পদ্ধতিটি আমরা ব্যবহার করব, তা হলো "অর্ডার"।

তো চল, প্রথমে একটু অর্ডার সম্পর্কে ধারণা নেওয়ার চেষ্টা করি।

কিন্তু দেখ, একটু চিন্তা করলেই বুঝতে পারবে যে, $ф(m)$ এর থেকেও ছোট কোনো সংখ্যা $d$ থাকতে পারে যেন, $a^d ≡ 1\pmod{m}$ হয়। যেমন দেখ, $7$ একটা স্বাভাবিক সংখ্যা এবং $ф(7) = 6.$ কিন্তু $2^3 ≡ 1\pmod{7}$

এখন ধরে নিই যে, $d$ হল সবচেয়ে ছোট সংখ্যা যার জন্য $a^d ≡ 1\pmod{m}$ হয়। এক্ষেত্রে আমরা $d$ কে বলব $m$ এর সাপেক্ষে $a$ এর অর্ডার এবং এটাকে লিখব এভাবে : $ord_m (a) = d.$

অর্থাৎ, $ord_m (a) = d$ এর অর্থ হলো : $a^d ≡ 1\pmod{⁡m}$ হবে এবং $d$ এর থেকে ছোট কোনো স্বাভাবিক সংখ্যা $n$ থাকবে না যেন $a^n ≡ 1\pmod{⁡m}$ হয়।

এবারে অর্ডার সম্পর্কে আমরা খুব গুরুত্বপূর্ণ একটি বৈশিষ্ট্য জানব।

$*$ মনে করি, স্বাভাবিক সংখ্যা $m$ এর জন্য $ord_m (a) = d$ এবং $a ,m$ পরস্পর সহমৌলিক। যদি কোনো স্বাভাবিক সংখ্যা $n$ এর জন্য $a^n\equiv 1\pmod{m}$ হয়, তাহলে, $d | n.$ $*$

চল, এটা প্রমাণ করার চেষ্টা করি :D

এখানে আমরা $n$ কে $d$ এর সাপেক্ষে এভাবে লিখতে পারি, $n = du + x$ ,যেখানে $0 ≤ x ˂ d.$

এখন,

$a^n ≡ 1\pmod{⁡m}$

বা, $a^{(du+x)} ≡ 1\pmod{m}$

বা, $(a^d )^u⋅a^x ≡ 1\pmod{m}$

বা, $(1)^u⋅a^x ≡ 1\pmod{m}$

বা, $a^x ≡ 1\pmod{⁡m}$

কিন্তু $x$ অবশ্যই $d$ এর থেকে ছোট , $x ˃ 0$ হলে $d$ আর অর্ডার থাকতে পারবে না। কাজেই এটা সম্ভব কেবলমাত্র যদি $x = 0$ হয়, সেক্ষেত্রে $n = du.$ সুতরাং, $d | n_{(proved)}$

অকা, এখন মোটামোটি আমরা প্রস্তুত আমাদের কাঙ্ক্ষিত প্রব্লেমটি সল্ভ করার জন্য।

প্রবেল্মটি আরেকবার রিডিং পড়ে নাও।

আচ্ছা, তোমরা নিশ্চয় এখন ধরতে পেরেছ যে আমরা $(*)$ চিহ্নিত বৈশিষ্ট্যটি কেন প্রমাণ করেছি! এটিই এখানে আমরা ব্যবহার করব। তোমরা এখন এটা ব্যবহার করে প্রব্লেমটা নিজে সল্ভ করা চেষ্টা কর, সল্ভ করতে না নিচে সলুশ্যান দেখে নাও।

আচ্ছা লক্ষ কর, এখানে ভাজ্য হলো $ϕ(a^n - 1).$ তার মানে নিশ্চয় আন্দাজ করতে পারছ যে আমাদেরকে $(a^n - 1)$ এর $mod$ নিতে হবে। এখন আমাদেরকে যেটা করতে হবে তা হলো $(a^n - 1)$ এর সাথে সহমৌলিক হয় এমন একটি সংখ্যা বেছে নিতে হবে। আমাদের চোখের সামনে যা আছে তা থেকেই আমরা একটি বেছে নিই। আশা করি কারো বুঝতে সমস্যা হবে না যে, $a$ এবং $(a^n - 1)$ এর গ.সা.গু. $1.$

এখন খেলা শুরু :D

আমরা লিখতে পারি যে, $a^n ≡ 1\pmod{a^n -1}$

আবার অয়লার এর উপপাদ্য থেকে বলতে পারি যে, $a^{ϕ(a^n-1)} ≡ 1\pmod{a^n - 1}.$

খেলা শেষ। অনেক জোস না? :D গুড বাই :D

Modulo Arithmetic : Last digit analysis (Part $2$)

Previous Part

In the last part, we talked about last digit analysis. We'll continue this topic by investigating its application on some problems.

Firstly, an easy exercise :

So, since $2009$ is odd, the answer is $9$.

If you still didn't get the hang of it, here's another problem :

Great job if you get this problem! This problem is slightly harder than the previous one, as it involve two powers. But, as we shall see, this problem is not as hard as it seems.

Great job if you still remember, or if you derive it. In any case, the pattern is $7, 9, 3, 1, 7, 9, 3, 1, ...$.

How do we get $3$? We'll make use of negative numbers :

$7^7 \equiv (-1)^7 \equiv -1 \equiv 3 \pmod{4}$. So indeed the remainder is $3$.

That's right. Since the remainder of the exponent is $3$ when divided by $4$, the last digit of the original is the $3$rd in the cycle of last digits for powers of $7$.

So, the answer we've been looking for is $3$.

Next part

Multiplicative Order

What is order? In number theory, we call a number $k$ the order of $a$ modulo $n$ if $n \nmid a^m - 1$ for all $m < k$ but $n \mid a^k - 1$. $k$ is often denoted as $o_n(a)$.

That's right, $d \mid k$.

So $d \mid k$.

Prove that $n$ divides $\varphi(a^n-1)$ for all integer $a$.