נושא: הוכחת משפט החלוקה עם שארית

בסיס:

a=0

אזי לכל b, עבור q = r = 0 , מתקיים : a=b*q+r

כלומר, עבור a=0 וכל b, קיימים q ו-r כנדרש.

הנחת האינדוקציה:

יהי a=n כלשהו, אזי לפי הנחה, לכל b>0 כלשהו קיימים q ו-r כך ש-n=a=b*q+r

צעד האינדוקציה:

נתבונן ב- S(n) :

S(n) = S(b*q+r) = b*q + r + 1

לפי הגדרת העוקב.

מכיוון ש r<b , אזי S(r)<b או ש- S(r)=b.

אם S(r)<b ,

 אזי q’=q ו-r’=S(r) , מקיימים את הטענה עבור S(n),

זאת משום שלפי הגדרת פעולת העוקב:

   b*q + r + 1 = b*q+S(r)

אם S(r)=b ,

 אזי q’=S(q) ו-r’=0 , מקיימים את הטענה עבור S(n) ,

 זאת משום ש:

B*q + r + 1 = b*q + S(r) = b*q + b = b*(q+1) = b*S(q) + 0

מכיוון שהראנו נכונות ל-n כלשהו ולעוקבו, ללא הגבלת הכלליות, הרי שהטענה נכונה לכל n טבעי.

מ.ש.ל.