Автор работы: Пользователь скрыл имя, 13 Апреля 2013 в 19:36, реферат
4.1 Евклид алгоритмі және арифметиканың негізгі теоремасы.
4.2 Ең үлкен ортақ бөлгіш және ең кіші ортақ еселік
4.4 Салыстыру теориясы
Анықтама. Қалындылардың толық жүйесінен алынған, 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 болатыны белгілі.
Теорема (Эйлер). 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алыстырулар жүйесін шеш: