הלמה של אוקלידס – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
Cat-a-lot: הסיר מקטגוריה:למות
מאין תקציר עריכה
שורה 11:
'''הלמה של אוקלידס'''. אם <math>p</math> ראשוני ו-<math>p|ab</math> אז <math>p|a</math> או <math>p|b</math>.
 
נגדיר <math>d=\gcd(p,a)</math> ([[מחלק משותף מקסימלי]]). d מחלק של p ולכן מהגדרת הראשוניות d=1 או d=p. אם d=p אז מכיוון ש-<math>d|a</math> נקבל <math>p|a</math> כפי שרצינו להוכיח. על כן נניח ש-d=1, כלומר a ו-p [[מספרים זרים]]. לפי [[אלגוריתם אוקלידס המורחב]] קיימים n ו-m שלמים כך ש-<math>1=na+pmmp</math>. נכפיל שוויון זה ב-b:{{כ}} <math>b=nab+pmbmpb</math>. p מחלק הן את ab והן את עצמו ולכן <math>p|n(ab)+p(mb) = b</math> כפי שרצינו להוכיח.
 
==המשפט ההפוך==