بزرگترین مقسوم علیه مشترک (Greatest Common Divisor) چند عدد

اعداد طبیعی (natural numbers) زیر را در نظر بگیرید :

\[ {a_1},{a_2},...,{a_n} \]

بزرگترین مقسوم علیه مشترک (Greatest Common Divisor) برای این اعداد، عدد $ b $ می باشد که بزرگترین عدد طبیعی (natural number) است که مقسوم علیه مشترک (common divisor) این اعداد باشد.

فرض کنید که اعداد مثبت $ {a_1},{a_2},...,{a_n} $ را به صورت ضرب اعداد اول (products of primes) بنویسیم :

\[ \begin{array}{l} {a_1} = p_1^{{k_{11}}}p_2^{{k_{12}}} ... p_m^{{k_{1m}}}\\ {a_2} = p_1^{{k_{21}}}p_2^{{k_{22}}} ... p_m^{{k_{2m}}}\\ ...\\ {a_n} = p_1^{{k_{n1}}}p_2^{{k_{n2}}} ... p_m^{{k_{nm}}} \end{array} \]

که در آن، $ {p_1},{p_2},...,{p_m} $ ، اعداد اول (prime numbers) متفاوتی می باشند. مقادیر $ {k_{ij}} $ ، اعداد صحیح مثبت (positive integers) هستند ( $ \quad i = 1,2,...,n $ و $ j = 1,2,...,m \quad $ )

بنابراین بزرگترین مقسوم علیه مشترک (Greatest Common Divisor) برای $ {a_1},{a_2},...,{a_n} $ به صورت زیر محاسبه می شود :

\[ b = p_1^{{\sigma _1}}p_2^{{\sigma _2}}...p_m^{{\sigma _m}} \quad\quad\quad {\sigma _j} = \mathop {\min }\limits_{1 \le i \le n} {k_{ij}} \]