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:
Euclidian algorithm:
Euclid algorithm এর যে principal এর উপর কাজ করে তাহলো
দুটি সংখ্যা 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
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.
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.
