Сандар теориясы

 ІV тарау. Сандар теориясы

 

4.1 Евклид алгоритмі және арифметиканың негізгі теоремасы.

 

Теорема (қалдықпен бөлу туралы). Егер болса. Онда

шарты орындалатындай бір  ғана сандары табылады.

Осы теореманың шартындағы – бөлінгіш, – бөлгіш, – бөлінді, ал – қалдық деп аталады.

 

Анықтама. және сандарының ең үлкен ортақ бөлгішін арқылы белгілейік.

Қасиеті. Егер a > b болса, (a, b) = (a – b, b).

 

Евклид алгоритмі әдетте екі бүтін санға қолданылады. Мысалы сандары берілсе, алдымен санын санына қалдықпен бөлеміз. Егер қалдық нөлге тең болса, онда алгоритм өз жұмысын тоқтатады. Кері жағдайда бөлгішті қалдыққа тағы да қалдықпен бөлеміз. Осы әрекет қалдық нөлге тең болғанша жалғасады. Евклид алгоритмін жоғарыдағы екі санға қолданғанда пайда болған ең соңғы нөлге тең емес қалдық – осы сандардың ең үлкен ортақ бөлгішін береді. Оны арқылы белгілейміз.

Енді Евклид алгоритмінің жалпы жазылуын келтірейік:

Кез келген  a > b; a, b Î сандары үшін қалдық нөлге тең болмаған жағдайда, бөлгішті қалдыққа бұрыштап бөлу арқылы келесі теңдіктер тізбегін аламыз.

a = bq₁ + r₁, 0 £ r₁ < b

b = r₁q₂ + r₂ , 0 £ r₂ < r₁

r ₁ = r₂ q₃ + r₃, 0 £ r₃ < r₂

r₂ = r₃ q₄ + r₄ ,0 £ r₄ < r₃

_{..................................................................}

r_{n -3} = r_{n -2} q_{n -1} + r_{n -1}, 0 £ r_{n -1} < r_{n -2}

r_{n -2} = r_{n -1} q_n + r_n, 0 £ r_n < r_{n -1}

r_{n -1} = r_n q_{n +1}, r_{n +1} = 0

 

b > r ₁ > r ₂ >... > r _n > 0,

Мысал. а = 525, b = 231 сандары берілсін. Осы сандарға Евклид алгоритмін қолдану үлгісін келтірейік.

_     _42|   42 |   0

_     63|   42 |   21   2

_     231|   189 |     42   1

525|   462 |     63   3

231   2

Бұл есептеуді төменгі  теңдіктер арқылы жазайық:

525 = 231 2 + 63, -

231 = 63 3 + 42,

63 = 42 1 + 21,

42 = 21 2.

Демек, (525, 231) = 21. Енді осы табылған ең үлкен ортақ бөлгіштің сызықты өрнектелуін келтіреміз.

21 = 63 - 42 1 = 63 - (231 - 63 3) 1 = 525 - 231 2 - (231 - (525 - 231 2) 3) = 525 4 - 231 9

Біздің іздеген сызықты коэффициенттер u және v сәйкес 4 және – 9 сандары болады.

Теорема (Ең үлкен  ортақ бөлгіштің сызықты өрнектелуі). Егер d = (a, b) болса, онда d = au + bv болатындай u және v бүтін сандары табылады.

Дәлелдеуі. жиынын қарастырайық. және . Енді сандарын алайық. Онда x-ті y-ке бөлгендегі қалдық -ға тиісті болады. Шынында:

x = yq + r , 0 £ r < y ,

r = x – yq = ( au₁ + bv₁ ) – ( au₂ + bv₂ ) q = a ( u₁ – u₂ q )+ b (v₁ – v₂q ) Î .

Егер d – -ға тиісті ең кіші оң сан болса, онда а саны d-ға бөлінеді. Өйткені, a = dq + r₁ , 0 Ј r₁ < d , a , d . Демек r₁ , ал санын таңдауымыздан r₁ = 0. Тура осылай b санының d-ға бөлінетінін көреміз. Ендеше d - a және b сандарының ортақ бөлгіші. d болғандықтан, оны d = au₀ + bv₀ түрінде жаза аламыз . Егер d₁ – a және b сандарының қандай да бір ортақ бөлгіші болса, онда d₁|(au₀ + bv₀), яғни d₁|d . Демек d і d₁ немесе d – ең үлкен ортақ бөлгіш болады. Кері жолы Евклид алгоритмінің тікелей салдары.          Теорема дәлелденді.

(525, 231) = 21,  21 = 525 4 - 231 9

Біздің іздеген сызықты коэффициенттер u және v сәйкес 4 және – 9 сандары болады.

Жаттығұлар:

1.  (187,221), (6188,4709) және (314,159) сандарын және олардың бастапқы сандар арқылы сызықты өрнектелуін табыңдар.

2. d = (317811, 196418) санын және оның d = 317811 u + 196418 v түріндегі сызықты өрнектелуін тап.

3. d = (81719, 52003, 33649, 30107) =?.

4. Қалдықпен бөлу(алдымен біріншісін екіншісіне және керісінше): 1) 17 -ні 161-ге; 2) –17-ні 161-ге; в) 17-ні –161-ге; г) –17-ні –161-ге.

5. Ковбой барға кіріп, 3 долларлық бір стакан виски, 1 доллар 11 центтік Marlboro қорабын, алты патрон және 13 қорап шырпыға тапсырыс берді. Барлығына – 28 доллар 25 цент сұраған барменді ковбой сол заматта атып тастады. Не үшін?

6. Егер және болса, онда саны санына бөлінетінін дәлелде.

7. Кез келген натурал саны үшін бөлшегі қысқармайтынын дәлелде.

8. Кез келген , және  натурал сандары үшін егер болса, онда болатынын дәлелде.

 

Бөлінгіштік қасиеттері.

1. – натурал санның ондық санау жүйесінде жазылуы болсын.

1) Берілген сан 3-ке  бөлінеді сонда тек сонда ғана, егер оның цифрларының қосындысы  3-ке бөлінсе.

2) Берілген сан 9-ға  бөлінеді сонда тек сонда ғана, егер оның цифрларының қосындысы  9-ға бөлінсе.

3) Берілген сан 11-ге  бөлінеді сонда тек сонда ғана, егер оның тақ орындағы цифрларының  қосындысы мен жұп орындағы  цифрларының қосындысының айырымы  11-ге бөлінсе.

2. Бүтін санның ондық  жүйедегі жазылуында 300 бірлік, ал  қалған цифрлары нөлге тең  болса, бұл сан толық квадрат  болуы мүмкін бе?

3. 1,2,3,4,5,6,7 сандары жазылған жеті  жетон бар. Осы жетондар арқылы  құрылған ешбір екі жетіорынды  сан бір біріне бөлінбейтінін көрсет.

4. – натурал санның ондық санау жүйесінде жазылуы болсын. Енді санын табайық. Егер табылған сан 19-дан үлкен болса, осы әрекетті алынған санға қайта қолданамыз. Бұл амалды табылған сан 19-дан кем болғанша жалғастырамыз. Онда бастапқы сан 19-ға бөлінуі үшін нәтиже санның 19-ға тең болуы қажетті және жеткілікті болатынын дәлелде.

5. – натурал санның ондық санау жүйесінде жазылуы болсын. Енді санын табайық. Онда бастапқы сан 7-ге бөлінуі үшін алынған санның 7-ге бөлінуі қажетті және жеткілікті болатынын дәлелде.

6.Кез келген  натурал саны үшін санының 24-ке бөлінетінін дәлелде.

7. Кез келген натурал саны үшін саны бүтін болатынын дәлелде.

8. Қандай натурал саны үшін саны 323 санына бүтін бөлінеді.

9. санының бүтін болмайтынын көрсет.

10. Кез келген және натурал сандары үшін қосындысының бүтін сан болмайтынын көрсет.

11. Келесі сандар бүтін сан болатынын дәлелде.

1) ,

2) ,

3) .

 

 

4.2 Ең үлкен ортақ бөлгіш және ең кіші ортақ еселік.

 

Анықтама. және сандарының ең кіші ортақ еселігін арқылы белгілейік.

Қасиеттері. және – сандарының сәйкес ең үлкен ортақ бөлгіші мен ең кіші ортақ еселігін білдірсін. Онда

1) .

2) .

3) .

Лемма. Натурал сандар жиынында анықталған екі орынды функциясы келесі қасиеттерге ие:

1) ; 2) ; 3) .

Онда  – ең кіші ортақ еселік болатынын дәлелде.

 

4.3 Жай сандар.

 

Анықтама. Тек екі бөлгіші болатын натурал сан жай сан деп аталады. Жай сан болмайтын натурал санды құрама сан деп атаймыз.

Лемма. Кез келген – құрама санының -нен артпайтын жай бөлгіші болады.

 

Теорема (жай сандар жиынының ақырсыздығы). Жай сандар жиыны ақырсыз жиын болады.

 

Теорема (арифметиканың негізгі теоремасы). Кез келген натурал сан жай сандардың көбейтіндісіне жіктеледі.

 

 

Жаттығулар.

1. Айырымы 17-ге тең  жай сандардың барлық парын  табыңдар.

2. Жай санды 30-ға бөлгендегі  табылған қалдықтың жа жай  болатынын көрсет.

3. болса және сандарының арасында ең болмағанда бір жай сан табылатынын дәлелде.

4. Егер  саны санына бөлінсе, онда жай сан болатынын дәлелде.

5. теңдігі орындалатындай және жай сандарының барлығын табыңдар.

6. түріндегі жай сандар жиынының ақырсыз болатынын көрсет.

7. түріндегі жай сандар жиынының ақырсыз болатынын көрсет.

8. 111, 1111, 11111, 111111, 1111111 сандарын жай  көбейткіштерге жікте.

9. Қатарынан келетін 1000 құрама  санның болатынын көрсет.

10. Кез келген  натурал саны үшін арасында бір ғана жай сан болатынын қатарынан келетін натурал сан табылатынын дәлелде.

11. Тек жай сандардан тұратын  арифметикалық прогрессия табыла  ма?

12. Егер  – жай сан болса, онда және – жай сан болатынын көрсетіңдер. Осы түрдегі жай сандарды Мерсенн сандары деп атайды.

13. Егер  – жай сан болса, онда – жұп сан, ал – 2-нің дәрежесі болатынын көрсетіңдер. түріндегі жай сандарды Ферма сандары деп атайды.

4.4 Салыстыру теориясы

4.4.1 Анықтама және қарапайым қасиеттері.

Анықтама. а, b Z , N. Егер а және b сандарын m-ге бөлгенде, олардың қалдықтары бірдей болса, онда а және b сандарын модулі бойынша салыстырымды деп айтып, бұл ұғымды арқылы белгілейміз.

Бұл бинарлық қатынас рефлексивті, симметриялы және транзитивті, яғни модуль бойынша салыстыру қатынасы эквиваленттік қатынас болады. Бүтін сандар сақинасында, бұл қатынас бойынша табиғи жолмен фактор-сақина анықталады. Оны модулі бойынша қалындылар сақинасы деп атап, Z _m арқылы белгілейміз. Жоғарыдағы анықтамадан салыстыру қатынасының келесі қажетті және жеткілікті шарты шығады:

Демек, болуы үшін a=b+mt теңдігі орындалатындай t бүтін санының табылуы қажетті және жеткілікті.

Қасиет 1. Берілген модул бойынша салыстыруларды мүшелеп қосуға болады.

Дәлелдеуі. a₁º b₁(mod m), a₂º b₂(mod m). Демек, сандары табылып, a₁ =b₁ +mt₁ ,   a₂ =b₂ +mt₂ теңдіктері орындалады. Осы екі теңдікті мүшелеп қоссақ, a₁ +a₂ =b₁ +b₂ +     m(t₁ +t₂ ), яғни a₁ +a₂ º b₁ +b₂ (modm).

Қасиет 2. Салыстырудың кез келген жағындағы қосылғышты, оның екінші жағына таңбасын өзгертіп көшіруге болады.

Қасиет 3. Салыстырудың кез келген жағына модулге еселі санды қосуға болады.

Қасиет 4. Берілген модул бойынша екі салыстыруды мүшелеп көбейтуге болады, яғни .

Қасиет 5. Салыстырудың екі жағын да бірдей дәрежеге шығаруға болады, яғни

Қасиет 6. Егер a₀ º b₀ (modm), a₁ º b₁ (modm),..., a_n º b_n (modm), x º y(modm), онда                a₀ xⁿ +a₁ x^n-1 +...+a_n º b₀ yⁿ +b₁ y^n-1 +...+b_n (modm).

Қасиет 7. Салыстырудың екі жағын да модулмен өзара жай болатын олардың ортақ бөлгішіне қысқартуға болады.

Қасиет 8. Салыстырудың екі жағы мен модулді бірдей санға көбейтуге және олардың ортақ бөлгішіне бөлуге болады.

Қасиет 9. Егер a º b салыстыруы бірнеше әртүрлі модул бойынша орындалса, онда бұл салыстыру аталған модулдердің ең кіші ортақ еселігі үшін де орындалады.

Қасиет 10. Егер салыстыру m модулі бойынша орындалса, онда ол осы m саныны кез келген бөлгіші d модулі үшін де орындалады.

Қасиет 11. Егер салыстырудың бір жағы мен модулі қандай да бір санға бөлінсе,

Мысал. Кез келген n натурал саны үшін 37ⁿ⁺² +16ⁿ⁺¹+23ⁿ саны 7-ге бөлінетінін дәлелде.

Шешуі. 37 º 2(mod7), 16 º 2(mod7), 23 º 2(mod7). Енді бірінші салыстыруды n+2, екіншіні n+1, ал үшіншіні n дәрежеге шығарып, мүшелеп қосамыз. Онда . Демек берілген сан 7-ге бөлінеді.

Жаттығулар.

1. 3¹⁰⁵ +4¹⁰⁵ саны 181-ге бөлінетінін дәлелде.

2. Кез келген n натурал саны үшін 5^2n-1 × 2ⁿ⁺¹ +3ⁿ⁺¹× 2^2n-1 саны 9-ға бөлінетінін дәлелде.

3. (9674⁶+28)¹⁵ санын 39-ға бөлгендегі қалдықты тап.

4. N натурал санын 3-ке және 37-ге бөлгендегі қалдықтар сәйкес 1 және 33 сандары болады. Осы санды 111-ге бөлгендегі қалдықты тап.

5. n санының барлық оң тақ мәндерінде S_m=1ⁿ+2ⁿ+3ⁿ+...+mⁿ саны 1+2+3+...+m санына бөлінетінін көрсет.

6. 20¹⁵-1 саны 11× 31× 61 көбейтіндісіне бөлінетінін дәлелде.

7. p және q – 3-тен артық жай сандар болса, онда p² - q² санының 24-ке бөлінетінін дәлелде.

8. Егер натурал сан 99-ға бөлінсе, онда оның цифрларының қосындысы 18-ден кем болмайды.

10. Ешбір натурал n және k ( k>1) сандары үшін 3^{n k} санының 5-ке бөлінбейтінін дәлелде.

4.4.2 Қалындылардың толық және келтірілген жүйелері.

Осының алдында º _m қатынасы бүтін сандар жиынын өзара қиылыспайтын кластарға бөледі. Барлық кластар саны m -ге тең. Әрбір класта m –ге бөлгенде қалдықтары бірдей болатын бүтін сандар жатады.

Анықтама. º _m  арқылы анықталған эквиваленттік кластың кез келген элементін m модулі бойынша қалынды деп атаймыз. Әрбір кластан бір-бір элементтен алынып құрылған қалындылар жүйесін m модулі бойынша қалындылардың толық жүйесі (толық жүйеде дәл m бүтін сан болады) деп атайды. Ал тек m –ге бөлгенде пайда болған қалдықтардан құрылған жүйе – ең кіші теріс емес қалындылар деп аталады. Егер ïrï модулдері бойынша ең кіші болса, онда r қалындысы абсолютті кіші қалынды делінеді:

Мысал m = 5. Онда:

0, 1, 2, 3, 4 - ең кіші теріс  емес қалындылар;

-2, -1, 0, 1, 2 - абсолютті  кіші қалындылар.

Келтірілген екі қалындылар жүйесі де толық жүйе болады.

Лемма 1. 1) m модулі бойынша өзара салыстырымды болмайтын m сан m модулі бойынша қалындылардың толық жүйесі болады.

2) Егер а және m сандары өзара жай, ал x санының мәндері m модулі бойынша толық жүйеден таңдалса, онда кез келген b саны үшін аx+b түріндегі сандар да m модулі бойынша толық жүйе құрады.

Дәлелдеуі. 1) тұжырым айқын. .2) тұжырымды дәлелдейік. аx+b түріндегі сандардың саны дәл m-ге тең. Енді осы алынғани сандар жүйесіндегі кез келген екі санның m модулі бойынша салыстырымды емес екенін көрсетейік. Шынынд x₁ және x₂ толық жүйеден алынған қандай да бір сандар үшін a x₁ +b º a x₂ +b(mod m) болсын дейік. Онда:  a x₁ +b º a x₂ +b(mod m) немесе a x₁ º a x₂ (mod m). Яғни x₁ º x₂ (mod m). Бұл x₁ және x₂ толық жүйеден алынғанына қайшы. Берілген º эквиваленттік кластың барлық сандары осы эквиваленттік кластың бір элементіне m –ге еселі санды қосу арқылы алнатындықтан, осы кластың барлықт сандарының m молдулімен ең үлкен ортақ бөлгіші бірдей болады. Біз олардың ішінде m модулімен ең үлкен ортақ бөлгіші 1-ге тең қалындыларды бөліп қарастырамыз.