شبكة الرياضيات رمز

Relatively Prime Numbers

تعريف 1: نقول عن عددين صحيحين a,b  إنهما أوليان نسبيا relatively prime, أو أوليان فيما بينهما,  أو أن  a  أولي نسبيا إلى  b  إذا كان العدد واحد هو القاسم المشترك الأكبر لهما.

مثال 1: العددين 12, 25 أوليان نسبيا لأن (12,25)=1 بينما 12, 27 غير أوليان نسبيا لأن (12,27)=3 .  

بدلالة عددين وقاسمهما المشترك الأكبر يمكن الحصول على عددين أوليان نسبيا وهذه تعتبر خوارزمية صغيرة جدا لتوليد أعداد أولية نسبيا نثبتها الآن.

حقيقة 1: إذا كان d=(a,b) فإن  (a/d,b/d)=1. أي أن b/d , a/d أوليان نسبيا.

البرهان: افرض أن c قاسم مشترك موجب للعددين b/d , a/d, وأن c>1.  إذا  a/d=mc , b/d=nc  وعليه فإن

a=(cd)m , b=(cd)n

إذا cd قاسم مشترك لكلا من a, b  وهذا مناقض أعظمية القاسم d حيث cd>d.  إذا c=1  ويثبت المطلوب.

حقيقة 2: إذا كان a,b أوليان نسبيا فإن a+b و ab أوليان نسبيا وكذلك a-b و ab أوليان نسبيا.

البرهان: بما أن a,b أوليان نسبيا يكافيء أن a,-b أوليان نسبيا يكفي اثبات الحقيقة في حالة ab, a+b.  ليكن k قاسم للعددين a+b و ab وليكن p أحد عوامل k الأولية. إذا p يقسم ab وبالتالي يقسم احد العددين a,b ولنفرض أنه يقسم a. ولكن p يقسم a+b إذا لابد أن يقسم العدد الآخرb إذا p قاسم للعددين a,b وهذا تناقض.