Greatest Common Divisor

Greatest common divisor:
       দুটি সংখ্যা a ও b যদি non-zero হয় তাহলে তাদের gcd হল largest common divisor a ও b হয়।যদি a এবং b non-zero হয় তাহলে,
                      1 ≤ gcd(a, b) ≤ min(|a|)


Gcd function এর কিছু elementary property:

gcd(a, 0)= |a|

gcd(a, ka)=|a|

gcd(0, 0)=0

gcd(an, bn)=n*gcd(a, b) where n ≥ 0

যদি n|ab এবং gcd(a, n)= 1 তাহলে n|b

যদি gcd(a, p) = 1 এবং gcd(b, p) = 1 হয় তাহলে gcd(ab, p) = 1

Euclidian algorithm:
    Euclid algorithm এর যে principal এর উপর কাজ করে তাহলো

       Gcd(a, b) = gcd (b, a%b)

         Base case হল: gcd(a, 0) = a

Algorithm implementation:

আমরা এটি প্রমান করতে পারি। কিন্তু এটি প্রমান করার আগে প্রথমে division theorem সম্পর্কে idea নিতে হবে।

Division theorem:
          যদি a একটি পূর্ণ সংখ্যা ও b একটি ধনাতম্ক পূর্ণ সংখ্যা হয় তাহলে আমরা এমন ২টি unique পূর্ণ সংখ্যা পাব k এবং r যেখানে,
                    a = k*b+r
            যেখানে k = a/b = ভাগফল
                       r = a mod b
     আমরা b|a লিখতে পারি যদি এবং কেবল যদি a mod b = 0 হয়।

Euclid algorithm এর প্রমানঃ

   ধরি, g = gcd(a, b)

         a = k*b+r [k হল k=a/b অধনাত্মক সংখ্যা ও r হল ভাগশেষ।]
যেহেতু g, a কে ভাগ করতে পারে তার মানে g, k*b+r নিঃশেষে ভাগ করতে পারে।

যেহেতু g, b কে নিঃশেষে ভাগ করতে পারে g, k*b কেও নিঃশেষে ভাগ করতে পারে।তার ফলে g r কেও ভাগ করতে পারে, তা না হলে k*b+r, b দ্বারা ভাগ করা যাবে না।

তাহলে আমরা প্রমান করলাম যে, g, b এবং r কে নিঃশেষে ভাগ করতে পারে।

          এখন ধরি,
             g’ = gcd(b, r)

     যেহেতু g’, b ও r উভয় কে নিঃশেষে ভাগ করতে পারে ত্রার মানে এটি k*b+r কে নিঃশেষে ভাগ করতে পারবে।

    তার মানে, g’,a কে নিঃশেষে ভাগ করতে পারবে।

আমরা contradiction এর মাধ্যমে প্রমান করতে 
             পারি যে, g = g’

অর্থাৎ gcd(a, b)= gcd(b, r) = gcd(b, a%b)


 কিছু Property of GCD function:


1) Communicative Law : GCD(a,b) = GCD(b,a)

2) Associative Law : GCD(a,GCD(b,c)) = GCD(GCD(a,b),c) 

3)  GCD(a,b,c) = GCD(GCD(a,b),c) 


Things to remember:

1) GCD(4,-2) returns -2 but correct answer should be 2 . To get the correct value we need to send the absolute value of the inputs to the algorithm or use the absolute value of the return value.

.2) GCD(0,0)=0 but the algo will try to do 0%0 for that we might 

get RTE. We need to take care of this manually.