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

הלמה נקראת על שמו של ה[[מתמטיקאי]] היווני בן [[המאה השלישיתה-3 לפנה"ס]] [[אוקלידס]], שהלמה מופיעה כמשפט ה-30 בכרך השביעי של ספרו [[יסודות (ספר)|יסודות]].

נגדיר <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+mp</math>. נכפיל שוויון זה ב-b:{{כ}} <math>b=nab+mpb</math>. p מחלק הן את ab והן את עצמו ולכן <math>p|n(ab)+p(mb) = b</math> כפי שרצינו להוכיח.