العامل المشترك الأكبر باستخدام العوامل الأولية

يصبح سرد العوامل بطيئًا مع الأعداد الأكبر، والتحليل إلى العوامل الأولية أسرع. حلّل كلا العددين إلى عواملهما: 45 هو 3 × 3 × 5 و75 هو 3 × 5 × 5. العوامل الأولية المشتركة بينهما هي 3 واحدة و5 واحدة.

اضرب العوامل الأولية المشتركة: 3 × 5 يساوي 15، وهو القاسم المشترك الأكبر للعددين 45 و75. لا يُعدّ العامل الأولي مشتركًا إلا بعدد مرات ظهوره في كلا العددين: يحتوي 45 على عاملين من 3، لكن 75 يحتوي على عامل واحد فقط، لذا نأخذ 3 واحدة فقط.

لماذا ينجح ذلك: لا يمكن تكوين عامل مشترك إلا من الأعداد الأولية الموجودة في كلا العددين. إن أخذ كل عدد أولي مشترك بأكبر عدد من المرات التي يسمح بها كلا العددين ينتج أكبر عامل مشترك. عند التعامل مع الأسس، خذ كل عدد أولي مشترك بأسه الأصغر: 3^2 × 5 و3 × 5^2 يعطيان 3 × 5.