036 — Cyclic Remainder Pattern¶
"7-এর 222 তম power-এর শেষ অঙ্ক কত?" — এই প্রশ্নের উত্তর হাতে হাতে, কয়েক সেকেন্ডে দেওয়া যায়। গোপন রহস্য: power-এর remainder ঘড়ির ঘরে ঘুরে ঘুরে একটা চক্র তৈরি করে। চক্রটা ধরে ফেললে বিশাল exponent-ও তুচ্ছ। এটাই Fermat-এর হাতে-কলমে চেহারা।
Source¶
- Original source: Classic exercise (cyclicity of powers / last digit pattern)
- Platform: Classic exercise — math olympiad আর CP intro-তে সাধারণ
- Topic: Math-based programming fundamentals → Level 2: Modular Arithmetic
- Difficulty: Easy
- Pattern: cycle in powers (cyclicity)
- Basic idea inherited from: 026 — Remainder Basics (clock model)
1. Problem in simple words¶
একটা base b আর একটা বিশাল exponent e দেওয়া। বের করতে হবে b^e-এর শেষ অঙ্ক (last digit) — মানে b^e % 10। অথবা আরও সাধারণভাবে: b^e % m যখন e এত বড় যে সরাসরি power বের করা কঠিন।
মূল চাবি: power-এর remainder গুলো একসময় পুনরাবৃত্তি করে — একটা চক্র (cycle) তৈরি হয়। সেই চক্রের দৈর্ঘ্য জানলে, e-কে চক্র-দৈর্ঘ্য দিয়ে mod করে সরাসরি উত্তর পাওয়া যায়।
2. What is the math idea?¶
মূল idea — cyclicity of powers (modular periodicity)। mod m-এর ঘড়িতে ঘর মোটে m টা। তাই b, b², b³, ...-এর remainder-গুলো 0..m−1-এর মধ্যেই ঘোরে — pigeonhole-এ একসময় আগের কোনো remainder ফিরবেই, আর ফিরলেই পুরো ধারা সেখান থেকে চক্রাকারে পুনরাবৃত্তি।
তাই যদি cycle-এর দৈর্ঘ্য L হয়:
b^e % m = b^((e−1) % L + 1) % m (1-indexed চক্রে)
last digit-এ এটা mod 10; cycle সাধারণত 1, 2, বা 4 দৈর্ঘ্যের হয়। এটাই Fermat (033)-এর a^(p−1) ≡ 1-এর সাধারণ রূপ: prime mod-এ cycle (p−1)-কে ভাগ করে।
3. Which basic idea does this inherit from?¶
সরাসরি 026 — Remainder Basics থেকে — clock model। mod m-এ ঘর সসীম (m টা), তাই power-এর remainder ঘুরেফিরে ফিরবেই — cyclicity-র পুরো ভিত এই "সসীম ঘড়ি"।
আর এটা 033 — Fermat Little Theorem-এর যমজ: Fermat বলে prime mod-এ a^(p−1) ≡ 1 — মানে cycle ঠিক (p−1) (বা তার ভাগ)। 036 সেই ধারণাটাই last-digit-এর সহজ, হাতে-গোনা রূপে দেখায়। আর 029-এর fast power হলো এর "যেকোনো mod"-এর general সমাধান; cyclicity হলো বিশেষ অন্তর্দৃষ্টি।
4. Real-life analogy¶
ভাবো সপ্তাহের দিন। আজ যদি সোমবার হয়, 100 দিন পরে কী বার? তুমি 100 দিন এক এক করে গুনবে না — জানো সপ্তাহ 7 দিনে চক্র; তাই 100 % 7 = 2, সোমবার থেকে 2 দিন পরে = বুধবার। চক্রটা ধরেই লাফ দিলে।
power-এর last digit-ও তেমন: 7-এর power-এর শেষ অঙ্ক 7, 9, 3, 1, তারপর আবার 7, 9, 3, 1 — 4 দিনের "সপ্তাহ"। তাই 7^222-এর শেষ অঙ্ক জানতে 222 বার গুণতে হয় না; 222 % 4 দিয়ে চক্রের ঘর বের করলেই হলো। বিশাল exponent ছোট চক্রে নেমে আসে।
5. Visual explanation¶
7-এর power-এর last digit চক্র:
7¹ 7² 7³ 7⁴ 7⁵ 7⁶ 7⁷ 7⁸ ...
7 49 343 2401 ...
last digit: 7, 9, 3, 1, 7, 9, 3, 1, ...
└────────────┘ └────────────┘
চক্র (length 4) আবার একই চক্র
7^222-এর last digit: 222 % 4 = 2 -> চক্রের 2 নম্বর ঘর -> 9
remainder 0 হলে সাবধান — চক্রের শেষ ঘর:
7^8-এর last digit: 8 % 4 = 0 -> remainder 0 মানে চক্রের শেষ ঘর (4র্থ) -> 1
(0 কে "ঘর 0" ভেবো না; এটা পুরো এক চক্র শেষ — শেষ ঘরে দাঁড়ানো)
ভাষায়: index = (e-1) % 4, তারপর cycle[index]; e=8 -> (7)%4=3 -> cycle[3]=1 ✓
6. Example input and output¶
b e -> last digit (b^e % 10) চক্র
---------------------------------------------------------
7 222 -> 9 [7,9,3,1], 222%4=2 -> ঘর 2
2 10 -> 4 [2,4,8,6], 10%4=2 -> ঘর 2
3 4 -> 1 [3,9,7,1], 4%4=0 -> শেষ ঘর
5 100 -> 5 [5], cycle length 1
6 7 -> 6 [6], length 1
0 5 -> 0 0^e = 0 (e>0)
1 999 -> 1 [1], length 1
edge case: base-এর last digit 0,1,5,6 হলে cycle length 1 (সবসময় একই অঙ্ক)। b^0 = 1। আর remainder 0 হলে চক্রের শেষ ঘর — সবচেয়ে কমন ভুল এখানেই।
7. Brute force thinking¶
সরল: সরাসরি power বের করে last digit (Python big int-এ সম্ভব), অথবা প্রতি step-এ mod 10 নিয়ে e বার গুণ।
def last_digit_brute(b, e):
if e == 0:
return 1
d = 1
for _ in range(e):
d = d * b % 10 # e বার গুণ, প্রতি step mod 10
return d
ঠিক উত্তর দেয়। সমস্যা একটাই — loop চলে e বার।
8. Why brute force may be slow¶
loop ঘোরে e বার। e = 10^18 হলে কার্যত অসম্ভব। (pow(b, e, 10) দিয়েও O(log e)-তে হয়, কিন্তু cyclicity-র অন্তর্দৃষ্টি দেখায় কেন উত্তর এত সহজ — অনেক সময় হাতে-মুখে বের করা যায়।)
e = 10^18 হলে:
brute (O(e)): 10^18 বার গুণ -> অসম্ভব
cyclicity (O(L)): cycle length L (≤4 last digit-এ) বের, তারপর e % L
-> মুঠোয়, এমনকি হাতে-কলমে
মূল শিক্ষা: পুরো power বের না করে, ছোট চক্রটা ধরো — তারপর e % L দিয়ে সরাসরি ঘর।
9. Better thinking¶
চক্র বের করো (যতক্ষণ না remainder পুনরাবৃত্তি), তারপর e-কে cycle-দৈর্ঘ্য দিয়ে mod করে ঘর বেছে নাও:
def last_digit(b, e):
if e == 0:
return 1
cycle = []
d = b % 10
while d not in cycle: # চক্র বানাই যতক্ষণ নতুন
cycle.append(d)
d = d * b % 10
r = e % len(cycle)
return cycle[r - 1] # r=0 হলে cycle[-1] = শেষ ঘর (ঠিক কাজ করে)
cycle[r - 1]-এর সৌন্দর্য: r = 0 হলে Python-এ cycle[-1] = শেষ ঘর — remainder-0-এর edge case আপনিই সামলে যায়।
general mod-এ (last digit না, যেকোনো m) সরাসরি fast power সবচেয়ে নিরাপদ: pow(b, e, m) (029)।
10. Thinking tweak¶
আসল "আহা!": power-এর remainder সসীম ঘড়িতে ঘোরে, তাই একসময় পুনরাবৃত্তি করবেই — চক্রটা ধরো, তারপর exponent-কে চক্র-দৈর্ঘ্য দিয়ে mod করো। বিশাল exponent তখন ছোট চক্রের একটা ঘরে নেমে আসে।
দুটো সতর্কতা-tweak:
- remainder 0 = শেষ ঘর, প্রথম ঘর নয়।
cycle[r-1]দিয়ে এটা সহজে সামলাও (r=0 → cycle[-1])। - exponent-কে mod করো, base-কে নয়।
7^222-এ 222 % 4, কখনো 7 % 4 নয়।
11. Step-by-step dry run¶
last_digit(7, 222):
| step | d (আগে) | cycle এ আছে? | cycle append | পরের d = d×7 % 10 |
|---|---|---|---|---|
| 1 | 7 | না | [7] | 49 % 10 = 9 |
| 2 | 9 | না | [7, 9] | 63 % 10 = 3 |
| 3 | 3 | না | [7, 9, 3] | 21 % 10 = 1 |
| 4 | 1 | না | [7, 9, 3, 1] | 7 % 10 = 7 |
| 5 | 7 | হ্যাঁ (থামল) | — | — |
cycle = [7, 9, 3, 1], length 4। এবার:
উত্তর 9। Check: pow(7, 222, 10) = 9 ✓ (Python-এ মিলিয়ে দেখো)।
আর remainder-0 কেস last_digit(7, 8): 8 % 4 = 0 → cycle[-1] = 1। Check: pow(7, 8, 10) = 1 ✓।
12. Python solution¶
def last_digit(b, e):
"""b^e-এর শেষ অঙ্ক (b^e % 10), cyclicity দিয়ে।"""
if e == 0:
return 1 # b^0 = 1 (b ≠ 0 ধরে; 0^0 আলাদা গল্প)
cycle = []
d = b % 10
while d not in cycle:
cycle.append(d)
d = d * b % 10
r = e % len(cycle)
return cycle[r - 1] # r=0 -> cycle[-1] = শেষ ঘর
def power_mod_general(b, e, m):
"""যেকোনো mod-এ b^e % m — fast power, সবচেয়ে নিরাপদ general পথ।"""
return pow(b, e, m)
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert last_digit(7, 222) == 9
assert last_digit(2, 10) == 4
assert last_digit(3, 4) == 1 # remainder 0 -> শেষ ঘর
assert last_digit(5, 100) == 5 # cycle length 1
assert last_digit(6, 7) == 6
assert last_digit(1, 999) == 1
assert last_digit(7, 0) == 1 # b^0 = 1
# মূল যাচাই: Python-এর pow(b, e, 10) এর সাথে মিলিয়ে দেখা
for b in range(2, 30):
for e in range(1, 60):
assert last_digit(b, e) == pow(b, e, 10)
# বিশাল exponent-এও cyclicity ঠিক:
assert last_digit(7, 10**18 + 222) == pow(7, 10**18 + 222, 10)
assert last_digit(2, 10**15) == pow(2, 10**15, 10)
# general mod fast power মিল:
assert power_mod_general(3, 100, 97) == pow(3, 100, 97)
print(last_digit(7, 222)) # 9
print(last_digit(3, 4)) # 1
print(last_digit(2, 10**18)) # বিশাল exponent, ঝটপট
print("সব test pass!")
13. Line-by-line explanation¶
e = 0 হলে b^0 = 1। নাহলে চক্র বানাই: d শুরু b-এর last digit; যতক্ষণ d নতুন (cycle-এ নেই) ততক্ষণ যোগ করি আর পরের power-এর last digit বের করি (d * b % 10)। যখন পুরনো d ফিরে আসে — চক্র সম্পূর্ণ, loop থামে।
exponent-কে cycle-দৈর্ঘ্য দিয়ে mod করি — কোন ঘরে পড়ব। cycle[r-1] কারণ চক্র 1-indexed অর্থে (1ম power = cycle[0]); আর r = 0 হলে cycle[-1] = শেষ ঘর, যা remainder-0-এর সঠিক উত্তর।
এই double loop বহু base আর exponent-এ Python-এর সত্যিকার pow(b, e, 10)-এর সাথে মিলিয়ে দেখছে — এটাই সবচেয়ে শক্ত যাচাই। বিশাল exponent (10^18+222)-এও মেলানো হয়েছে। সব ঠিক থাকলে শেষে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম লাইন last_digit(7, 222) → 9 (চক্রের ঘর 2)। দ্বিতীয় last_digit(3, 4) → 1 (remainder 0, শেষ ঘর)। তৃতীয় last_digit(2, 10**18) → 6 (2-এর চক্র [2,4,8,6], 10^18 % 4 = 0 → শেষ ঘর 6)। আগের সব assert (pow-এর সাথে বিশাল exponent সহ মিল) চুপচাপ pass — তারপর সব test pass!।
15. Time complexity¶
O(L) চক্র বানাতে, যেখানে L = cycle length (last digit-এ সর্বোচ্চ 4)। তারপর e % L আর একটা lookup — O(1)। মোট কার্যত O(1) last digit-এর জন্য। pow(b, e, m) general পথ O(log e)। brute O(e)-এর তুলনায় বিশাল।
16. Space complexity¶
O(L) — শুধু cycle list (last digit-এ ≤4 element)। কার্যত O(1)। pow পথে O(1)।
17. Common mistakes¶
- remainder 0 কে প্রথম ঘর ভাবা —
e % L == 0মানে চক্রের শেষ ঘর, প্রথম নয়।cycle[r-1](r=0 → cycle[-1]) দিয়ে সামলাও; নাহলে এক ঘর ভুল। - base-কে mod করা — exponent-কে cycle-দৈর্ঘ্য দিয়ে mod করো (
222 % 4), base-কে নয় (7 % 4ভুল)। - cycle length অনুমান করা — সব base-এ cycle 4 নয়; 5,6,0,1-এর cycle 1, কারও 2। সবসময় বের করে নাও, ধরে নিও না।
b^0ভুলে যাওয়া —e = 0হলে উত্তর 1; আলাদা handle না করলে cycle/index ভুল।- general mod-এ last-digit cycle ব্যবহার — mod 10 ছাড়া অন্য m-এ cycle ভিন্ন; general হলে fast power (
pow(b, e, m)) নিরাপদ। - 0 বা negative base —
0^e = 0(e>0); negative base-এ last digit-এর ধারণা সাবধানে।
18. Harder problems that inherit this idea¶
- 033 (Fermat Little Theorem) (https://cp-algorithms.com/algebra/module-inverse.html) — cyclicity-র theorem-রূপ; prime mod-এ cycle (p−1)-কে ভাগ করে।
- CSES — Exponentiation II (https://cses.fi/problemset/task/1712) — tower power
a^(b^c); exponent-কে Fermat-এ mod (p−1) — cyclicity-র সরাসরি প্রয়োগ। - Last digit / unit digit olympiad problems —
2^222 + 3^333-এর শেষ অঙ্ক ধরনের; cycle ধরে হাতে সমাধান।
19. Pattern learned¶
Cyclicity of powers — power-এর remainder সসীম ঘড়িতে চক্রে ঘোরে; cycle length L বের করে e % L দিয়ে ঘর বেছে নাও (remainder 0 = শেষ ঘর)। exponent mod করো, base নয়। Fermat-এর হাতে-কলমে রূপ; general হলে fast power।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "power-এর last digit/remainder চক্রে ঘোরে — cycle বের করে e % L দিয়ে ঘর নাও (0 হলে শেষ ঘর)। exponent mod করি, base নয়। 'বিশাল exponent, ছোট mod (বিশেষত last digit)' দেখলেই cyclicity — নাহলে fast power।"
পরের ধাপ → 037 — Clock Arithmetic Problems (mod-এর ঘড়ি analogy-র সরাসরি প্রয়োগ)। সম্পর্কিত → 033 — Fermat Little Theorem, 029 — Modular Exponentiation।
ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "common interview pattern" / "CP-তে নিত্য দরকারি" লেখা।