Сандар теориясы
ІV тарау. Сандар теориясы
4.1 Евклид алгоритмі және арифметиканың негізгі теоремасы.
Теорема (қалдықпен бөлу туралы). Егер болса. Онда
шарты орындалатындай бір ғана сандары табылады.
Осы теореманың шартындағы – бөлінгіш, – бөлгіш, – бөлінді, ал – қалдық деп аталады.
Анықтама. және сандарының ең үлкен ортақ бөлгішін арқылы белгілейік.
Қасиеті. Егер a > b болса, (a, b) = (a – b, b).
Евклид алгоритмі әдетте екі бүтін санға қолданылады. Мысалы сандары берілсе, алдымен санын санына қалдықпен бөлеміз. Егер қалдық нөлге тең болса, онда алгоритм өз жұмысын тоқтатады. Кері жағдайда бөлгішті қалдыққа тағы да қалдықпен бөлеміз. Осы әрекет қалдық нөлге тең болғанша жалғасады. Евклид алгоритмін жоғарыдағы екі санға қолданғанда пайда болған ең соңғы нөлге тең емес қалдық – осы сандардың ең үлкен ортақ бөлгішін береді. Оны арқылы белгілейміз.
Енді Евклид алгоритмінің жалпы жазылуын келтірейік:
Кез келген a > b; a, b Î сандары үшін қалдық нөлге тең болмаған жағдайда, бөлгішті қалдыққа бұрыштап бөлу арқылы келесі теңдіктер тізбегін аламыз.
a = bq1 + r1, 0 £ r1 < b
b = r1q2 + r2 , 0 £ r2 < r1
r 1 = r2 q3 + r3, 0 £ r3 < r2
r2 = r3 q4 + r4 ,0 £ r4 < r3
..............................
rn -3 = rn -2 qn -1 + rn -1, 0 £ rn -1 < rn -2
rn -2 = rn -1 qn + rn, 0 £ rn < rn -1
rn -1 = rn qn +1, rn +1 = 0
b > r 1 > r 2 >... > r n > 0,
Мысал. а = 525, b = 231 сандары берілсін. Осы сандарға Евклид алгоритмін қолдану үлгісін келтірейік.
|
|
_ |
525| |
231 |
Бұл есептеуді төменгі теңдіктер арқылы жазайық:
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
Біздің іздеген сызықты
Теорема (Ең үлкен
ортақ бөлгіштің сызықты
Дәлелдеуі. жиынын қарастырайық. және . Енді сандарын алайық. Онда x-ті y-ке бөлгендегі қалдық -ға тиісті болады. Шынында:
x = yq + r , 0 £ r < y ,
r = x – yq = ( au1 + bv1 ) – ( au2 + bv2 ) q = a ( u1 – u2 q )+ b (v1 – v2q ) Î .
Егер d – -ға тиісті ең кіші оң сан болса, онда а саны d-ға бөлінеді. Өйткені, a = dq + r1 , 0 Ј r1 < d , a , d . Демек r1 , ал санын таңдауымыздан r1 = 0. Тура осылай b санының d-ға бөлінетінін көреміз. Ендеше d - a және b сандарының ортақ бөлгіші. d болғандықтан, оны d = au0 + bv0 түрінде жаза аламыз . Егер d1 – a және b сандарының қандай да бір ортақ бөлгіші болса, онда d1|(au0 + bv0), яғни d1|d . Демек d і d1 немесе d – ең үлкен ортақ бөлгіш болады. Кері жолы Евклид алгоритмінің тікелей салдары. Теорема дәлелденді.
(525, 231) = 21, 21 = 525 4 - 231 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-ке
бөлінеді сонда тек сонда ғана,
егер оның цифрларының
2) Берілген сан 9-ға
бөлінеді сонда тек сонда ғана,
егер оның цифрларының
3) Берілген сан 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. Берілген модул бойынша салыстыруларды мүшелеп қосуға болады.
Дәлелдеуі. a1º b1(mod m), a2º b2(mod m). Демек, сандары табылып, a1 =b1 +mt1 , a2 =b2 +mt2 теңдіктері орындалады. Осы екі теңдікті мүшелеп қоссақ, a1 +a2 =b1 +b2 + m(t1 +t2 ), яғни a1 +a2 º b1 +b2 (modm).
Қасиет 2. Салыстырудың кез келген жағындағы қосылғышты, оның екінші жағына таңбасын өзгертіп көшіруге болады.
Қасиет 3. Салыстырудың кез келген жағына модулге еселі санды қосуға болады.
Қасиет 4. Берілген модул бойынша екі салыстыруды мүшелеп көбейтуге болады, яғни .
Қасиет 5. Салыстырудың екі жағын да бірдей дәрежеге шығаруға болады, яғни
Қасиет 6. Егер a0 º b0 (modm), a1 º b1 (modm),..., an º bn (modm), x º y(modm), онда a0 xn +a1 xn-1 +...+an º b0 yn +b1 yn-1 +...+bn (modm).
Қасиет 7. Салыстырудың екі жағын да модулмен өзара жай болатын олардың ортақ бөлгішіне қысқартуға болады.
Қасиет 8. Салыстырудың екі жағы мен модулді бірдей санға көбейтуге және олардың ортақ бөлгішіне бөлуге болады.
Қасиет 9. Егер a º b салыстыруы бірнеше әртүрлі модул бойынша орындалса, онда бұл салыстыру аталған модулдердің ең кіші ортақ еселігі үшін де орындалады.
Қасиет 10. Егер салыстыру m модулі бойынша орындалса, онда ол осы m саныны кез келген бөлгіші d модулі үшін де орындалады.
Қасиет 11. Егер салыстырудың бір жағы мен модулі қандай да бір санға бөлінсе,
Мысал. Кез келген n натурал саны үшін 37n+2 +16n+1+23n саны 7-ге бөлінетінін дәлелде.
Шешуі. 37 º 2(mod7), 16 º 2(mod7), 23 º 2(mod7). Енді бірінші салыстыруды n+2, екіншіні n+1, ал үшіншіні n дәрежеге шығарып, мүшелеп қосамыз. Онда . Демек берілген сан 7-ге бөлінеді.
Жаттығулар.
1. 3105 +4105 саны 181-ге бөлінетінін дәлелде.
2. Кез келген n натурал саны үшін 52n-1 × 2n+1 +3n+1× 22n-1 саны 9-ға бөлінетінін дәлелде.
3. (96746+28)15 санын 39-ға бөлгендегі қалдықты тап.
4. N натурал санын 3-ке және 37-ге бөлгендегі қалдықтар сәйкес 1 және 33 сандары болады. Осы санды 111-ге бөлгендегі қалдықты тап.
5. n санының барлық оң тақ мәндерінде Sm=1n+2n+3n+...+mn саны 1+2+3+...+m санына бөлінетінін көрсет.
6. 2015-1 саны 11× 31× 61 көбейтіндісіне бөлінетінін дәлелде.
7. p және q – 3-тен артық жай сандар болса, онда p2 - q2 санының 24-ке бөлінетінін дәлелде.
8. Егер натурал сан 99-ға бөлінсе, онда оның цифрларының қосындысы 18-ден кем болмайды.
10. Ешбір натурал n және k ( k>1) сандары үшін 3n 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 модулі бойынша салыстырымды емес екенін көрсетейік. Шынынд x1 және x2 толық жүйеден алынған қандай да бір сандар үшін a x1 +b º a x2 +b(mod m) болсын дейік. Онда: a x1 +b º a x2 +b(mod m) немесе a x1 º a x2 (mod m). Яғни x1 º x2 (mod m). Бұл x1 және x2 толық жүйеден алынғанына қайшы. Берілген º эквиваленттік кластың барлық сандары осы эквиваленттік кластың бір элементіне m –ге еселі санды қосу арқылы алнатындықтан, осы кластың барлықт сандарының m молдулімен ең үлкен ортақ бөлгіші бірдей болады. Біз олардың ішінде m модулімен ең үлкен ортақ бөлгіші 1-ге тең қалындыларды бөліп қарастырамыз.
Анықтама. Қалындылардың толық жүйесінен алынған, m модулімен ең үлкен ортақ бөлгіші 1-ге тең қалындылар жүйесін m модулі бойынша келтірілген қалындылар жүйесі деп атайды.
Келтірілген қалындылар жүйесін әдетте ең кіші оң қалындылар ішінен таңдайды. Олардың санын j (m) – Эйлер функциясының мәніне тең деп есептейді. Яғни j (m) – m модулі бойынша келтірілген қалындылар жүйесіндегі сандардың санын білдіреді.
Мысал. m = 42 болсын. Онда осы модул бойынша келтірілген қалындылар жүйесі төмендегідей: 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Лемма 2. 1) m модулі бойынша екеуара салыстырымды болмайтын j (m) сан m модулі бойынша келтірілген қалындылар жүйесін құрады.
2) Егер (a,m) = 1 және x саны қандай да m модулі бойынша келтірілген қалындылар жүйесінен мәндер таңдаса, онда аx сандар да m модулі бойынша келтірілген қалындылар жүйесінен мәндер таңдайды.
Дәлелдеуі. 1-ші тұжырым анықтамадан. 2-ші тұжырымды көрсетейік. аx сандары екеуара салыстырымсыз және олардың саны дәл j(m)-ге тең. (a,m)=1, (x,m)=1 Þ (ax.m)=1 болғандықтан, олардың әрқайсысы модулмен өзара жай. Демек, аx сандары да m модулі бойынша келтірілген қалындылар жүйесін құрады.
Лемма 3. m1, m2, ..., mk – екеуара жай сандар тізімі және m1 m2 ...mk =M1 m1 =M2 m2 =...=Mk mk болсын . Мұндағы Mj =m1 ...mj-1 mj+1 ...mk
1) Егер x1 , x2 , ..., xk сандары сәйкес m1 , m2 , ..., mk модулдері бойынша қалындылардың толық жүйесін қабылдаса, онда M1 x1 +M2 x2 + ...+Mk xk сызықты өрнегінің мәндері де m=m1 m2 ...mk модулі бойынша қалындылардың толық жүйесінің мәндерін қабылдайды.
2) ) Егер x1 , x2 , ..., xk сандары сәйкес m1 , m2 , ..., mk модулдері бойынша қалындылардың келтірілген жүйесін қабылдаса, онда M1 x1 +M2 x2 + ...+Mk xk сызықты өрнегінің мәндері де m = m1 m2 ...mk модулі бойынша қалындылардың келтірілген жүйесін құрады.
Дәлелдеуі.
1) M 1 x 1 +M 2 x 2 + ...+M k x k өрнегі x 1 , x 2 , ..., x k сандарының аталған мәндері ұшін m1 m2 ...mk =m мән қабылдайтыны түсінікті. Осы мәндердің m модулі бойынша екеуара салыстырмды болмайтынын көрсетсек болады. Егер
Болса, онда Ms –тен бөлек кез келген Mj көбейтіндісі ms санына еселі болады, Сондықтан, соңғы салыстырудың екі жағындағы ms санына еселі қосылғыштарды алып тастасақ, Þ болатынын көреміз. Бұл x s сандарының m s модулі бойынша қалындылардың толық жүйесінің мәндерін түгел қабылдап өтетініне қайшы болады.
2). M1 x1 + M2 x2 + ...+ Mk xk өрнегі j (m1 ) j (m2 ) × ... × j (mk ) = j(m1 m2 × ... × mk ) = j(m) (Эйлер функциясы мультипликативті!) әртүрлі мән қабылдайды және олар m = m1 m2 ...mk модулі бойынша өзара жай сандар болады. Оны жоғарыдағы әдіспен көрсете аламыз. Ал кез келген 1 £ s £ k үшін (M1 x1 + M2 x2 + ...+ Mk xk ,ms ) = (Ms xs , ms ) = 1 болғандықтан, (M1 x1 + M2 x2 + ...+ Mk x k ,ms ) =1, демек M 1 x 1 +M 2 x 2 + ...+M k x k өренегініңғ мәндері m модулі бойынша келтірілген қалындылар жүйесін құрады.
Лемма 4. x1 , x2 , ..., xk ,x және x1 , x2 ,..., xk , x сандары i ¹ j (mi, mj )=1 болғанда, сәйкес m1, m2 , ..., mk және m=m 1 m 2 ...m k модулдері бойынша толық және келтірілген қалындылар жүйелерін аралап шықсын,. онда {x1 /m1 +x2 /m2 +...+xk /mk } бөлшектері {x/m} бөлшектерімен, ал { x 1 /m 1 + x 2 /m 2 +...+ x k /m k } бөлшектері {x /m} бөлшектерімен бірдей болады.
Дәлелдеуі. {x 1
/m 1 +x 2 /m 2
+...+x k /m k
} және {x 1
/m 1 + x 2
/m 2 +...+ x k
/m k } қосындыларын ортақ бөлімге
келтірейік: {x 1
/m 1 +x 2 /m 2
+...+x k /m k
}=
{M 1
x 1 +M 2 x 2
+...+M k x k
)/m} және { x 1
/m 1 + x 2
/m 2 +...+ x k
/m k }=
Енді бірдің түбірлері, қалындылар жүйелері және Мебиустің m (m) мультипликативті функциясының арасындағы байланысты келтіреміз.
арқылы 1-дің m-ші дәрежелі -шы түбірін белгілейік. Оны есептеу формуласы: . Сонымен бірге, бізге 1-дің m-ші дәрежелі түбірлерінің қосындысы e0 + e1 +...+ em-1 болатыны белгілі.
4.4.3 Эйлер және Ферма теоремалары.
Теорема (Эйлер). m>1 , (a,m)=1 , ал j (m) – Эйлер функциясы болсын. Онда:
aj ( m ) º 1(modm).
Дәлелдеуі. x саны m модулі бойынша қалындылардың келтірілген класын аралап өтсін. Яғни , мұндағы c= j (m) олардың саны, ал r 1 ,r 2 ,..., r c – модулі бойынша ең кіші келтірілген қалындылар. Енді санына сәйкес модулі бойынша ең кіші келтірілген қалындыларды r 1 , r 2 ,..., r c арқылы белгілесек, онда бұрын белгілі болғандай
Осы салыстыруларды мүшелеп көбейтсек, болады. Ал және бұл көбейтінділер модулмен өзара жай болғандықтан, салыстырудың екі жағын осы көбейтіндіге қысқартсақ, . Теорема дәлелденді.
Теорема (Ферма). р – жай сан және ол a санының бөлгіші болмаса, онда
.
Дәлелдеуі. Эйлер теоремасының салдары
Салдар 1. Кез келген саны мен жай саны үшін .
Дәлелдеуі. Жаттығу.
Салдар 2. Кез келген сандары үшін (a+b)p º ap +bp (mod p) .
Мысал 1. Бір орынды санның тоғызыншы дәрежесі 7-ге аяқталады.
Шешуі. Берілгені бойынша a 9 º 7(mod 10). Сонымен бірге, (7, 10)=1 және ( a , 10)=1. Эйлер теоремасы бойынша a j (10) º 1(mod 10). Демек a 4 º 1(mod 10). Оны квадраттасақ, a 8 º 1(mod 10). Онда . Яғни a =7.
Жаттығу.
1. Дәлелде 1 18 +2 18 +3 18 +4 18 +5 18 +6 18 º -1(mod 7)
2. 7 402 санын 101-ге бөлгендегі қалдықты тап.
3. 243 402 санының соңғы екі цифрын тап.
Шешуі. Бұл санның соңғы екі цифры – осы санды 100-ге бөлгендегі қалдықты береді. 243=200+43; 200+43 º 43(mod 100) болғандықтан, осы салыстырудың екі жағын 402-ге дәрежелеп, салыстырудың сол жағын Ньютон биномы бойынша жіктесек (әрине ойша), сол жағындағы соңғы қосылғыштан басқасы 200-дің қандай да бір дәрежесі болғандықтан, олар 100-ге бөлінеді, демек ол қосылғыштар 0-мен салыстырымды. Демек ол қосылғыштарды ескерсеуге болады. Ендеше 243 402 º 43 402 (mod 100). Ал 43 және 100 сандары өзара жай болғандықтан, Эйлер теоремасы бойынша 43 j (100) º 1(mod 100). Онда j (100)= j (2 2 × 5 2 )=(10–5)(10–2)=40 болғандықтан, 43 40 º 1(mod 100), онда . Демек 243 402 санының соңғы цифрлары 4 және 9 .
Жаттығулар.
0. (73 12 -1) саны 105-ке бөлінетінін дәлелде.
1. а) 13 176 -1 саны 89-ға; б) 52 60 -1 саны 385-ке бөлінетін дәлелде.
2. 3 100 -3 60 -3 40 +1 саны 77-ге бөлінеді.
4. Дәлелде:
а) 1 19 +2 19 +4 19 +5 19 +7 19 +8 19 º 0(mod 9);
б) 1 14 +3 14 +7 14 +9 14 º 0(mod 10).
5. Келесі сандардың соңғы екі цифрын тап:
а) 19 321 ; б) 131 161 .
6. Қалдықты тап:
а) 3 200 +7 200 санын 101-ге ; б) 7 65 +11 65 санын 80-ге бөлгенде.
7. Соңғы 1000 цифры бірден және екіден тұратын 2 санының дәрежесі болатынын көрсет.
8. Бірінші мүшесі мен айырымы натурал сандар болатын a, a+d, a+2d, ... – ақырсыз арифметикалық прогрессиясы берілсің. Осы прогрессияда канондық жіктеулерінде бірдей жай сандар кездесетіндей (әрине әртүрлі дәрежемен) мүшелер саны ақырсыз болатынын дәлелде.
4.4.4 Қалдықтар туралы қытай теоремасы.
Лемма 1 Егер сандары санымен өзара жай болса, онда саны да санымен өзара жай болады.
Дәлелдеуі. Кез келген үшін саны сақинасында керіленетін элемент, демек элементінің де кері элементі бар. Яғни . Ендеше ол санымен өзара жай.
Лемма 2 Егер сандары ( ) – санының бөлгіші болсын, онда саны да санының бөлгіші болады.
Дәлелдеуі. бойынша индукцияны қолданамыз. болғанды бәрі анық. Енді кез келген сандары үшін лемманың тұжырымы дұрыс болсын. Яғни саны да санының бөлгіші. Онда 1 лемма бойынша . Ендеше индукция жоруынан саны санының бөлгіші болады.
Теорема (Қалдықтар туралы қытай теоремасы). m1 ,m2 ,...,mk өзара жай сандар және кез келген бүтін сандары үшін салыстырулар жүйесінің аралығында бір ғана шешімі болады. Дәлелдеуі. болсын. Онда . Ендеше сандары табылып, болады. деп алайық. Онда және . Егер деп алсақ, онда . Демек, ол берілген салыстырулар жүйесінің шешімі болады. Егер осы салыстырулар жүйесінің басқа шешімі болса, онда . Яғни . Ал аралығында бұл тек үшін ғана орындалады. Теорема дәлелденді.
Мысал. 4-ке бөлгендегі қалдығы 1, 5-ке бөлгендегі қалдығы 3, ал 7-ге бөлгендегі қалдығы 2 болатын санды тап.
Лемма 3. Егер теоремадағы b1 ,b2, ..., bk сандары m1 ,m2 ,...,mk модулдері бойынша қалындылардық толық жүйесін қабылдап өтсе, онда x 0 саны m1 m2 ...mk модулі бойынша қалындылардың толық жүйесін қабылдап өтеді.
Жаттығулар:
1. Салыстырулар мен салыстырулар жүйесін шешіңдер:
а) 5x º 3(mod 12);
b) 256x º 179(mod 337);
c) 1215x º 560(mod 2755);
d) 1296x º 1105(mod 2413);
e) 115x º 85(mod 335).
2 . Cалыстырулар жүйесін шеш:
3 . 7-ге бөлгендегі қалдығы 3, 11-ге бөлгендегі қалдығы 5, ал 13-ке бөлгендегі қалдығы 4 болатын санды тап.
4 Cалыстырулар жүйесін шеш:
5. Cалыстырулар жүйесін шеш:
- Сандинистский фронт национального освобождения
- Сандино, Аугусто Сесар
- Сандро Баттичелли
- Сандро Боттічеллі
- Сандық автоматта уақыт диограммасының жұмысы
- Сандық жасау техналогиясы
- Сандық жүйе
- Санация предприятий
- Санация предприятий
- Санация предприятий и способы ее осуществления
- Санация предприятия
- Санация предприятия
- Санаційна спроможність підприємства
- Сандакан
