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:

	int gcd ( int a, int b ) {
	if ( b == 0 ) return a;
	return gcd ( b, a % b );
	}

view raw GCD.cpp hosted with ❤ by GitHub

আমরা এটি প্রমান করতে পারি। কিন্তু এটি প্রমান করার আগে প্রথমে 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.

Common Divisors

Common divisor: 

         যদি  d, a এর একটি divisor হয় এবং d যদি b এর ও একটি divisor হয় তাহলে আমরা বলতে পারি যে d হল a এবং b এর common divisor।

         6 এর divisor হল 1, 2, 3, 6
         12 এর divisor হল 1, 2, 3, 4, 6, 12

         Common divisor (6, 12) = 1, 2, 3, 6

কিছু দরকারি তথ্য common divisor এরঃ

        1)   d | a এবং d | b implies  d | (a+b) এবং d | (a-b)
                         
        আরও সাধারনভাবে বলা যায় যে, d | a এবং d | b implies d | (ax+by) [সকল x এবং y এর জন্য] এবং যদি  a|b তবে,|a|≤|b| অথবা b=0

        2)  Number of Common Divisor(a, b) = Number Of Divisor (gcd(a, b))

             প্রমানঃ

             GCD(24, 30) = 6
             অর্থাৎ 24 এবং 30 এর মধ্যে এমন কোনো common divisor      নেই যা 6 এর চেয়ে বড়। 6 এর divisor হল 1, 2, 3, and 6।  24, 30     এর জন্য 6 এর চেয়ে ছোট বা সমান কোনো সংখ্যা নেই যা 24, 30     কে ভাগ করতে পারে এবং{1, 2, 3, 6} এর সেটে এ পরে না।

Problem : COMDIV - Number of common divisors

Editorial : Editorial Link