Evklid algoritmi

7.1. Butun sonlar bo`linishining sodda xossalari
1-lemma. Agar b soni c ga bo`linsa va a soni b ga bo`linsa, u holda a soni c ga bo`linadi.
Isbot: Lemma shartidan b=cq₁ va a=bq₂ kelib chiqadi, bunda q₁,q₂Z . Bundan a=bq₂= cq₁q_2.
q₁q₂=q deb belgilasak, a= cq₁q₂=cq, qZ.


2-lemma. Agar m=a+b bo`lib, m va a sonlarning har biri d soniga bo`linsa, u holda b soni ham d soniga bo`linadi.
Isbot: Lemma shartiga ko`ra m=dq₁ va a=dq₂, bunda q₁,q₂Z. m=a+b tenglikda b=( q₁-q₂)d. Demak, b soni d ga bo`linadi.


7.2. Natural sonlarning bo`linish belgilari
1. 6 ga bo`linish belgisi.
Agar biror natural son 2 ga ham, 3 ga ham qoldiqsiz bo`linsa, bu son 6 ga qoldiqsiz bo`linadi.
Misol. 1224; 12378; 10002 sonlarining har biri ham 2 ga, ham 3 bo`linadi. Shuning uchun ular 6 ga qoldiqsiz bo`linadi. (Buni tekshirib ko`rish o`quvchilarga tavsiya etiladi.)
2. 7 ga bo`linish belgisi.
Agar berilgan natural sonning oxirgi uchta raqami ifodalaydigan son bilan qolgan raqamlari ifodalaydigan sonning (yoki aksincha) ayirmasi 0 ga teng bo`lsa, yoki 7 ga teng bo`lsa, bu son 7 ga qoldiqsiz bo`linadi.
Misol. 1) 296 324 soni 7 ga qoldiqsiz bo`linadi, chunki oxirgi uchta raqamidan iborat 324 soni va qolgan raqamlardan iborat son 296 ning ayirmasi
324-296=28.
28 soni esa 7 ga qoldiqsiz bolinadi.
2) 423423 soni ham 7 ga qoldiqsiz bo`linadi, chunki 423-423=0
( tekshirib ko`rish o`quvchilarga tavsiya etiladi.)