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