021 — Coprime Check

018-এ GCD শিখেছ — এবার তার একটা ছোট্ট কিন্তু খুব দরকারি প্রয়োগ: দুটো সংখ্যা coprime কি না বলা। এক লাইনের problem, কিন্তু এর ধারণাটা Level 2-তে modular inverse-এর শর্ত হয়ে ফিরবে। তাই ছোট বলে উড়িও না — gcd = 1 মানে কী, সেটা ভালো করে গেঁথে নাও।

Source

• Original source: Classic exercise
• Platform: Classic exercise / — (judge-free)
• Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
• Difficulty: Easy
• Pattern: gcd(a, b) == 1
• Basic idea inherited from: 018 — GCD using Euclidean Algorithm

1. Problem in simple words

দুটো ধনাত্মক integer a আর b দেওয়া আছে। বলতে হবে এরা coprime (পরস্পর মৌলিক / relatively prime) কি না। coprime মানে — এদের মধ্যে 1 ছাড়া আর কোনো common factor নেই।

উদাহরণ: 8 আর 15 coprime, কারণ 8 = 2×2×2 আর 15 = 3×5 — কোনো prime মেলে না, তাই একমাত্র common factor 1। আবার 12 আর 18 coprime নয়, কারণ দুজনকেই 6 (এবং 2, 3) ভাগ করে।

মজার ব্যাপার: 8 আর 15 — দুটোর কেউই নিজে prime নয়, তবু এরা coprime! coprime হওয়াটা নিজে prime হওয়ার সাথে এক জিনিস নয়।

2. What is the math idea?

মূল idea একদম সরল, আর সম্পূর্ণভাবে GCD-র উপর:

a আর b coprime  <=>  gcd(a, b) == 1

কেন? gcd হলো দুজনের সবচেয়ে বড় common divisor। যদি সেই সবচেয়ে বড়টাই 1 হয়, তার মানে 1-এর বড় কোনো common divisor নেই — অর্থাৎ কোনো common factor নেই (1 ছাড়া)। সেটাই তো coprime-এর সংজ্ঞা।

তাই আলাদা করে কিছু আবিষ্কার করার নেই — gcd বের করো (018-এর Euclid), আর সেটা 1 কি না দেখো।

3. Which basic idea does this inherit from?

এটা সরাসরি 018 (GCD using Euclidean Algorithm)-এর একটা এক-লাইনের প্রয়োগ। gcd function থাকলে coprime check প্রায় কিছুই না — শুধু gcd(a, b) == 1 লেখা।

তাই এটা আলাদা একটা বড় algorithm নয়, বরং GCD-র একটা গুরুত্বপূর্ণ "use case"। আটকে গেলে 018-এ ফিরে যাও; gcd ঠিক থাকলে এটা আপনাআপনি ঠিক। আর এই problem নিজে এগিয়ে দেয় 022 (Count Coprime Pairs) আর 023 (Euler Phi)-এর দিকে — দুটোতেই "gcd == 1" বারবার লাগবে।

4. Real-life analogy

ভাবো দুটো cogwheel (দাঁতওয়ালা চাকা) একসাথে ঘুরছে — একটায় 8টা দাঁত, আরেকটায় 15টা। প্রথম চাকার একটা নির্দিষ্ট দাঁত আবার ঠিক সেই জায়গায় দ্বিতীয় চাকার একই দাঁতের সাথে কখন মিলবে?

8 আর 15 coprime বলে — সব দাঁত একে অপরের সাথে অন্তত একবার মিলবে, তারপর পুরো cycle (8×15 = 120 ধাপ) শেষে আবার শুরুর জায়গায় ফিরবে। দাঁত সমানভাবে "মিশে" যায়, কোনো দাঁত বারবার একই দাঁতের সাথে আটকে থাকে না।

কিন্তু 12 আর 18 হলে (common factor 6) — কিছু দাঁত বারবার একই কয়েকটা দাঁতের সাথেই মেলে, পুরো মিশ্রণ হয় না। সেই "পুরোপুরি মিশে যাওয়া বনাম আটকে থাকা"-র পার্থক্যই coprime বনাম not-coprime।

5. Visual explanation

প্রথমে factorization দিয়ে দেখো — common prime আছে কি নেই:

coprime উদাহরণ:
   8 = 2 · 2 · 2
  15 = 3 · 5
       কোনো prime মেলে না  ->  gcd = 1  ->  coprime ✓

not-coprime উদাহরণ:
  12 = 2 · 2 · 3
  18 = 2 · 3 · 3
       2 আর 3 মেলে        ->  gcd = 2·3 = 6  ->  coprime নয় ✗

এবার gcd-এর সিদ্ধান্তটা ছবিতে:

gcd(a, b) বের করো:
   == 1  -> coprime         (1 ছাড়া কোনো common divisor নেই)
    > 1  -> coprime নয়       (gcd নিজেই একটা common factor)

6. Example input and output

   a  ,   b   ->  coprime?   (gcd)
-----------------------------------
   8  ,  15   ->  True       (gcd 1)
  12  ,  18   ->  False      (gcd 6)
  17  ,   5   ->  True       (gcd 1, দুটোই prime)
   9  ,  28   ->  True       (gcd 1, কেউই prime নয় তবু coprime)
  14  ,  21   ->  False      (gcd 7)
   1  ,   1   ->  True       (gcd 1)
   1  ,  10   ->  True       (1 সবার সাথে coprime)
   6  ,   6   ->  False      (gcd 6, একই সংখ্যা)

দুটো জিনিস খেয়াল করো: 1 প্রত্যেকের সাথে coprime (gcd(1, যেকোনো) = 1)। আর coprime হতে দুজনের কাউকে prime হতে হয় না — 9 আর 28 দুজনেই composite, তবু coprime।

7. Brute force thinking

GCD-সূত্র মাথায় না এলে, সবচেয়ে সরল চিন্তা — 2 থেকে শুরু করে min(a, b) পর্যন্ত প্রতিটা সংখ্যা দিয়ে দেখি, কেউ দুজনকেই ভাগ করে কি না। একটাও পেলে coprime নয়:

def is_coprime_brute(a, b):
    a, b = abs(a), abs(b)
    for d in range(2, min(a, b) + 1):
        if a % d == 0 and b % d == 0:
            return False          # common factor পাওয়া গেছে
    return True                   # 1 ছাড়া কেউ মেলেনি

এটা প্রতিটা সম্ভাব্য common factor (2, 3, 4, ... min) ঘুরে দেখে; একটাও দুজনকে ভাগ করলেই coprime নয়। কেউ না মিললে coprime। সরল, ঠিক উত্তর দেয়।

8. Why brute force may be slow

সমস্যা হলো এই loop min(a, b) − 1 বার পর্যন্ত ঘোরে। ছোট সংখ্যায় টের পাবে না, কিন্তু a, b দুটোই বড় আর coprime হলে (যেমন দুটো বড় prime ~10⁹) loop প্রায় পুরো min(a, b) বার চলবে — কারণ কোনো common factor কখনো পাবে না, তাই শেষ পর্যন্ত ঘুরবে।

a, b দুটো ~10^9 আর coprime হলে:
  brute force : ~10^9 বার loop   (ধীর, O(min(a, b)))
  gcd দিয়ে    : ~30 ধাপের কম      (O(log min(a, b)))

মূল কথা: প্রতিটা divisor হাতড়ে দেখা অপচয়, যখন gcd একবারেই সবচেয়ে বড় common divisor বলে দেয়। সেটা 1 কি না — এক তুলনায় শেষ।

9. Better thinking

মূল insight — coprime হওয়া মানে gcd ঠিক 1; তাই প্রতিটা factor খোঁজার দরকার নেই, শুধু gcd 1 কি না দেখলেই হলো।

GCD আমরা 018-এ Euclid দিয়ে O(log) সময়ে বের করতে শিখেছি। তাই:

def is_coprime(a, b):
    return gcd(a, b) == 1

ব্যস। gcd সবচেয়ে বড় common divisor; সেটা 1 মানে 1-এর বড় কোনো common divisor নেই — তাই coprime। brute force-এর min(a, b) ধাপ এক লাইনে নেমে এল।

10. Thinking tweak

আসল "আহা!" মুহূর্ত: "কোনো common factor আছে কি না" — এই প্রশ্নটা আসলে "gcd 1 কি না" প্রশ্নেরই অন্য চেহারা।

মূল মোচড়টা এই উপলব্ধি — সবচেয়ে বড় common divisor যদি 1 হয়, তাহলে স্বয়ংক্রিয়ভাবে 1-এর বড় আর কোনো common divisor নেই (কারণ থাকলে gcd সেটাই হতো, 1 নয়)। তাই সব factor আলাদা করে দেখার দরকারই নেই — gcd একটাই সংখ্যায় পুরো উত্তর ধরে রাখে। এই "একটা সংখ্যা পুরো প্রশ্নের জবাব দেয়" চিন্তাটা মনে রাখো।

11. Step-by-step dry run

চলো is_coprime(8, 15) ধীরে চালাই। আগে gcd(8, 15) বের করি (Euclid), তারপর 1-এর সাথে তুলনা:

step	a	b	a % b
1	8	15	8
2	15	8	7
3	8	7	1
4	7	1	0 → থামো, gcd = 1

gcd = 1, তাই 1 == 1 → True → coprime। মিলিয়ে দেখো: 8 = 2³, 15 = 3×5 — সত্যিই কোনো prime মেলে না।

তুলনায় is_coprime(12, 18): gcd(12, 18) = 6 (018-এর dry run-এর মতো), আর 6 == 1 মিথ্যা → False → coprime নয়।

12. Python solution

def gcd(a, b):
    """018-এর Euclid — coprime check-এর ভিত্তি।"""
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a


def is_coprime(a, b):
    """a আর b coprime (gcd == 1) হলে True, নাহলে False।"""
    return gcd(a, b) == 1


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert is_coprime(8, 15) is True        # gcd 1
assert is_coprime(12, 18) is False      # gcd 6
assert is_coprime(17, 5) is True        # দুটোই prime
assert is_coprime(9, 28) is True        # কেউই prime নয়, তবু coprime
assert is_coprime(14, 21) is False      # gcd 7
assert is_coprime(1, 1) is True         # gcd 1
assert is_coprime(1, 10) is True        # 1 সবার সাথে coprime
assert is_coprime(6, 6) is False        # gcd 6
assert is_coprime(35, 64) is True       # 5·7 আর 2^6 -> coprime

print(is_coprime(8, 15))    # True
print(is_coprime(12, 18))   # False
print(is_coprime(9, 28))    # True
print("সব test pass!")

13. Line-by-line explanation

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

এটা 018-এর Euclid — coprime check-এর পুরো ভিত্তি। বড় জোড়াকে ছোট জোড়ায় নামিয়ে b = 0 হলে a-ই gcd।

def is_coprime(a, b):
    return gcd(a, b) == 1

এটাই হৃদয়, এক লাইন। gcd(a, b) দেয় সবচেয়ে বড় common divisor; সেটা ঠিক 1 হলে == 1 দেয় True (coprime), নাহলে False। কোনো loop নেই — gcd-ই সব কাজ করে দিয়েছে।

লক্ষ করো assert-গুলোতে is True / is False ব্যবহার করেছি — কারণ function ঠিক boolean ফেরত দেয় (truthy কিছু নয়), তাই identity check-ও নিরাপদ আর পরিষ্কার।

বাকি assert লাইনগুলো নিজেদের চেক করছে; সব ঠিক থাকলে শেষে সব test pass! ছাপে।

14. Output walkthrough

চালালে যা ছাপবে:

True
False
True
সব test pass!

প্রথম তিন লাইন তিনটা print(is_coprime(...)) থেকে: (8,15) → True (gcd 1), (12,18) → False (gcd 6), (9,28) → True (gcd 1, যদিও দুটোই composite)। তার আগের সব assert চুপচাপ pass করেছে। সবশেষে সব test pass!।

15. Time complexity

O(log min(a, b)) — পুরো খরচটাই gcd বের করায় (Euclid, O(log))। তারপর একটাই তুলনা (== 1) — constant। তাই 018-এর GCD যত দ্রুত, coprime check-ও ঠিক তত দ্রুত। brute force-এর O(min(a, b))-এর তুলনায় বিশাল উন্নতি।

16. Space complexity

O(1) — gcd iterative হওয়ায় শুধু গুটিকয় variable লাগে, কোনো বাড়তি list বা array নেই। input ছাড়া আলাদা জায়গা প্রায় শূন্য।

17. Common mistakes

1. coprime আর prime গুলিয়ে ফেলা — coprime হতে দুজনের কাউকে prime হতে হয় না (9 আর 28 coprime, দুটোই composite)। coprime দুটো সংখ্যার সম্পর্ক, prime একটা সংখ্যার গুণ।
2. 1-কে বাদ দেওয়া — 1 প্রত্যেকের সাথে coprime (gcd সবসময় 1)। অনেকে ভুলে যায়।
3. gcd == 0 আর gcd == 1 গুলিয়ে ফেলা — gcd(0, 0) = 0; এটা coprime নয়। সবসময় ঠিক 1-এর সাথে তুলনা করো।
4. নিজে নিজে factor খোঁজা — gcd জানা থাকতে প্রতিটা divisor হাতড়ানো অপচয়; এক লাইনের gcd check-ই যথেষ্ট।
5. truthy চেক করা — if gcd(a, b) লিখলে সেটা "gcd শূন্য নয়" বোঝায়, "coprime" নয়। সবসময় স্পষ্ট করে == 1।

18. Harder problems that inherit this idea

• CP-Algorithms — Euler's totient function (https://cp-algorithms.com/algebra/phi-function.html) — φ(n) মানে 1..n-এর মধ্যে কয়টা n-এর সাথে coprime; এই check-এর সরাসরি সম্প্রসারণ, আমাদের problem 023।
• LeetCode — Largest Coprime Divisor / GCD-ভিত্তিক problems (https://leetcode.com/tag/number-theory/) — coprime/gcd চিন্তা নানা রূপে ফেরে; common interview pattern।
• 022 (Count Coprime Pairs) — এই repo-রই পরের ধাপ, যেখানে এই check প্রতিটা জোড়ায় চালিয়ে coprime জোড়া গোনা হবে।

19. Pattern learned

Coprimality via GCD — coprime <=> gcd(a, b) == 1। মূল শিক্ষা: "1 ছাড়া common factor নেই" — এই পুরো প্রশ্নটা একটা সংখ্যায় (gcd) ধরা যায়, প্রতিটা factor আলাদা খোঁজার দরকার নেই। Level 2-তে modular inverse থাকা-না-থাকার শর্ত হিসেবে এই pattern ফিরবে।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "coprime = gcd(a, b) == 1; দুজনের মধ্যে common factor আছে কি না জানতে চাইলেই এক লাইনে gcd দেখব। coprime ≠ prime — composite দুটো সংখ্যাও coprime হতে পারে, আর 1 সবার সাথে coprime।"

পরের ধাপ → 022 — Count Coprime Pairs Basic (এই check প্রতিটা জোড়ায় চালাব)। শিকড় → 018 — GCD using Euclidean Algorithm।

ফিরে দেখা: এই 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" লেখা হয়েছে।