Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 161
Текст из файла (страница 161)
1. и = 1,2,4,5,8, 10,20,40. 3. Если а нечетное, то а = 2тп + 1 для некоторого целого числа т. Следовательно, а = (2т+ 1) = 4тз+ 4т+ 1 и а — 1 = 4т + 4т = 4т(т+ 1). Но или т, или т+ 1 является четным. Очевидно, а — 1 делится на 8. 5. Если а гв Ь (пюд п), где и = НОК(иы пз, пз,..., п»), то а — Ь делится на НОК(пы пз, пз, ...,п»), так что а — Ь делится на и, для 1 < 1 < )с. Таким образом, а ге Ь (тод п,). Обратно, предположим, что а еа Ь (тод и,), для некоторого 1 < 1 < Л.
Тогда а — Ь делится на и, для некоторого 1 < 1 < Л. По определению НОК, а — Ь делится на НОК(пи из,из,, и»), и а гв Ь (тод п). 7. Докажем индукцией по т. Несомненно, а гя Ь (пюд п). Поэтому утверждение истинно для т = 1. Предположим, что оно истинно для и = Л, поэтому а" = 6" (пюд и). По теореме 3.54, если а эа Ь (пюд и) и а" = 6" (шод и), то а»+' ш 6»+', поэтому утверждение истинно для и = )с + 1. 9.
Если а = Ь (шос) Оба; †„ ), то а — Ь = Л д ) для некоторого Л. Поэтому ас — Ьс = й и~оды „1 с, ПосколькУ НОД(с, п) ~с, то йойТ,-„->. — целое число, скажем, д. Таким обРазом, ас — Ьс = Лдп и ас — Ьс шоб и. Обратно, если ас = — Ьс глоб п, то ас — Ьс = Лп для некоторого lс. Поскольку (а — Ь)с = Лп, (а — Ь)йф;-„- = нбвд-„—. Поскольку убдд;„- и йбф;~ взаимно простые числа, йбф-- делит (а — Ь), поэтому а ш Ь (глод йбф;-„-). 11. а) (1,5,2,3)(4); б) 1; в) (1,3,5,4)(2); г) (1,3)(2)(4,6,7)(5)(8). 13. Предположим, что дН = Нд для всех д 6 С. Пусть Л 6 Н. Поэтому Лд 6 Нд. Поскольку Нд = дН, то существует элемент Л' такой, что Лд = дЛ' и Л = дЛ'д ' б дНд Следовательно, Н С дНд ', Предположим, что дЛд ' 6 дНд ' Поскольку Нд = дН, то существует элемент Л' такой, что дЛ = дЛ' и Л' = дЛд '.
Следовательно, дЛд ' 6 Н и дНд ' С Н. Таким образом, дНд ' = Н. ответы к упражнениям 901 Раздел 10.3. 1. а) х к— е 81 (тод 300); 6) х ке 815 (пюс1 1260); в) х гя 16а — 156 (шод 240); г) х ге 1272 (пкк1 2310). 3. 1459 разноцветных шариков; 97 рядов по 15 шариков, 182 рядов по 8 шариков и 63 рядов по 23 шариков.
5. а) яке 21 (глод 72); 6) х = 104 (тос1 180); в) нет решения. Раздел 10.4. 1. т=4п=2. 3. Поскольку 1009 — простое число, то по теореме Уилсона 1008(де 1 (глод (1009). Поскольку 1008 ге -1 (пюс1 (1009), то 1007! га — 1 (пюс1 1009). 5. докажем по индукции, что если п = Р,' Рз' Рс с, то Ф(п) = П, , 1 (, * — 1) При 1 теорема верна в силу теоремы 10.20. Предположим, теорема верна при с = Ь, так что, если т = р,'рз' .
.р„', то ф(ги) = П , р.' '(рс — 1). Допустим, что и = р,'рз* ...р„ +, Тогда ф(п) = ф(ги)ф(р„",") по теореме 10.19. Но ф(р„"+,') = р„"" ,(рь4с — 1) по теореме 10.20, поэтому ф(п) = Ц", , р,' (Р, — 1)(рь+сс (Рь+с — 1)) = П,=с р,' (Р* 1). 7. 1080. 9. По теореме Уилсона, число р простое тогда и только тогда, когда (р — 1)! ке — 1 (пюд р).
Последнее имеет место тогда и только тогда, когда (р — 1)! + 1 ке 0 (пюд р). А это имеет место тогда и только тогда, когда (р — 1)! + 1 делится на р. Раздел 10.5. 1. Если а не равно 0 по модулю р, то а = Ь (пкк1 р), где 1 < Ь < р — 1. По малой теореме Ферма, У' ': — 1 (пюд р). Но а' ' ге У' ' (пюд р). Следовательно,а" ' ке 1 (пюс1 р). 3.
Поскольку 1 га 0 (спад р — 1), 1 = )с(р — 1) для некоторого целого )с. Пусть 1 < а < р — 1. Поскольку ае ' ке 1 (пюс1 р), а = а~Се 0 = (а~е О) гя 1 гя 1 (пюс1 р), то 1 +2 + «- (р — 1) ке 1 «- 1+ + 1 (гпод р) ге р — 1 (пюс1 р) = = — 1 (пюд р). 7. Поскольку ае гя а (шод р), У' (пкн1 р).
а 124578 9. а) огд„а 1 б 3 6 3 2 6) ж Ь (тос1 р) и (а -1-Ь)е ж а+ Ь (тод р), то (а+6)е ж аз+У' а 1 2 4 5 7 8 10 11 в) 13 14 16 17 19 20 22 23 25 26 огд„а 1 18 9 18 9 6 3 18 9 18 9 6 3 18 9 18 9 2 902 Ответы и упражнениям Раздел 11.1. 1. (а), (с), (е). 3. а) а„= с1. 3"; в) а = с1 (-3)" + сг 2"; б) а„= с1 ° ( — 3)"; г) а„=с (~~' ) +с (~~'~) б) а =6" г) а =4 ° 3" — 2 ° 4 б) а„= 2 . 2" + и 2" г) а„= — 3+ 4и; 5. а) а =( — 4)"; в) а =3" +2"; 7.а)а =3 3" +4и 3"; в) а = ( — 2)" +Зи ( — 2)"; д) а„= 2 ° (-1)" — 8и ° ( — 1) 9. а) а„=с1 4" +сг; б) а„= с1 + сгп + сз сов ( — ") + сз юп ( "г ); В)а =с1+сг'( 1) +сзсоз(г)+с4Б1п(г); г) а =С1+сг и+сзи +с4сов( 4 )+сзюп("4 ) +овсов( 4 )+ств!и( 4 ).
11. Воспользуемся индукцией. При и = 3 имеем Тз = а+ 6 = а Фиб(2) + Ь Фиб(1) Допустим, Дь = аФиб(й — 1) + ЬФиб(й — 2) для любого 3 < 14 < т. 1 =А 1+1 -г= = а Фи 6(т — 2) + Ь Фиб(т — 3) + а Фиб(т — 3) + Ь Фиб(т — 4) = а(Фиб(т — 2) + Фиб(т — 3)) + 6(Фиб(т — 3) + Фиб(т — 4)) = а Фиб(т — 1) + Ь Фиб(т — 2). Раздел 11.2. 1.
а) а„= с1 б) а„ = с1 в) с1 3" + 2" — 5 сг'( 4)» гз 2 („-згкз) + с, (з — кз ) + э (3) 2" +сги 2" + из+ 8п+ 32. г) а =с1 д) а„ = с1 11. а) 2401 ю 1 (пюй 5); б) 2401 гв 1 (пю11 2); в) 2401 эа 1 (пю4( 10); г) поскольку 74 ю 1 (пюй 10), (74) эз 1" (пюс( 10), то 744 ээ 1 (пнк1 10).
Последняя десятичная цифра числа 7~~~ есть 1. 13. а) 7; б) 376; в) 68; г) 961; д) 535044134. 15. а) Если а 1 ю -1 (п1о11и), то а" ' эа 1 (пго11 и). Поскольку а г гв — 1 (1по11п), оно не сравнимо с 1 по модулю п. Таким образом, все требования критерия Лукаса удовлетворены, поэтому и — простое число; б) 2'в ю — 1 (пюд 37), 2'г ю 26 (тод 37), поэтому число 37 простое; 3'вв гв — 1 (пюд 199), Звв гв 106 (пнн1 199), 31Б гв 125 (пюс( 199), поэтому число 199— простое. 17. а) Згзв гв 1 (глод 257); 31гз гв — 1 (тос( 257).
Поэтому число 257 простое. б) Зв"зв м 1 (пгод 65537); 3 геев ю — 1 (тод 65537); бвзззв ю 1 (тоа 65537); 5згтвв ю — 1 (пюй 65537). Ответы к упражнениям 903 с> 2" + п. 2"; с> ° ( — 3) + сгп ° ( — 3)" + >иг ° ( — 3) с>+ сги 2" — 5и; с> 3" + сг (-2)" + >зп 3"; 2 (с1 соз ( з ) + сг з1п ( з ) ) + — 11. п(п+ 1)(2и+ 1) 6 2"+' — 2; 3. В) а„ б) а В) а„ г) а„ д) а п(Зи — 1) а 2 а. = 1п(и+1)(и+2).
5. В) а„ В) а„ б) г) Раздел 11.3. 1. 12. 3. 644. 5. Зхг + 8х — 6. 10 (Зх+ 4)(Зх + 7) 9. По определению, <3(х!) = (х + 1) < — хд = х)(х 4- 1 — 1) = х х!. 1(х) 1(х+ 1) 1(х) /(х+ 1)д(х) — 1'(х)д(х+ 1) д(х) д(х + 1) д(х) д(х + 1)д( ) Дх + 1)д(х) — Дх)д(х) + 1(х)д(х) — Дх)д(х + 1) д( + 1)д(х) У(х + 1) — Пх))д( ) — <'(х)(д(х + 1) — д(х)) д(х + 1)д(х) <3Дх) д(х) — 1(х) Сзд(х) д( + 1)д( ) а. 3.. 11. х.
13 х<4) 7х<г> 5х + 5 15. х<з) + 9х<4» -- 20х<з> + 10х<г» -- х — 1 17 х4 зхз 2хз + 2х + 1 19. х — 11х4 + 42хз — 65х + 34х — 1. 21. -3. Раздел 11.5. 1. 58137. 3. -8988. 5. 62132. ".-, '<') >"" (и+1)<'> — 1<'> ° (п+ Ц 2>1 2 2 Раздел 11.4. 1. 18х — 10. 3. 60х<г) + 72х — 18. (х<з) 2х<з) Ц(4х<з) + бх<г> 12х+ 1)+ +((х+ 1) + 2(х+ 1)<з) — 6(х+ 1)<г) + х — 2)(3х<г) — 4х) 7. (х<4> Зх<з> + бх<г>)(4х<з> — бт+ 3) (х<4> Зх<г> + Зх)(4х<з> дх<г> + 12х) (х<4> — зх<з> + бх<г)) ((х + 1) <а) — 3(х + 1)<з) .,- 6(х 4- 1)<г) ) 904 Ответы к упражнениям Н с(с+ ц ~- са+,.
~ с(а!+24 !да!+с!2!~ !! с=! с=! =! (и+ Ц(п)(п — Ц (и+ Ц(п)(и+2) 11. 177144. 13. 22520. 15. 26106. 17. 6203013120. 19. 28385280. 21. Пусть сьев(х) = 7"(х), тогда !5 ~ у(с) = с5(Р(с+ ц — Г(*)) = Ь(Р(с+ ц — ЬР(*) = Π— у(*) = — д*) . Раздел 12.1. 1. а) й" Зт 2187 б) ИЯь ! = 3'Бэ~~ = 6 ' 301 = 1806' в) С(п+ )с — 1, п) = С(7+ 3 — 1,7) = С(9,7) = 36; г) С(п — 1, й — Ц = С(6,2) = 15; д) Я! ! + Яз~ ! + Яз~ ! = 1+ 63 + 301 = 365; е) оь!"! — — 301. 3. и'!1с О 1 2 3 4 5 6 7 8 9 10 11 12 11 О 1 1023 28501 145750 246730 179487 63987 11880 1155 55 1 12 О 1 2047 86526 611501 1379400 1323652 627396 159027 22275 1705 66 1 5. а) (с" = 4'з = 16777216; б) НЯск,"~ = 4!Яс! ! = 24 611501 = 14676024; в) С(и + lс — 1, и) = С(15, 12) = 455; г) С(п — 1,/с — Ц = С(11,3) = 165; д) (е) Я! с! + Яз! ! + Яа! ! + Яс! ! = 1 + 2047 + 86526 + 611501 = 70075 е) оь!"! = Яс! ! = 611501.
7. а) о(п,О) = —,( — Ц (о)(0 — 0)" = 0; 6) 5(п,lс — Ц 4-)сЯ(п,lс) = (1с — Ц1 ( — ц ((с — с — ц +Й вЂ” 2 ( — ц (/с — с)" = ()с — ц! ( с )' (/с — ц! ( с/ ~(-ц . (ус — с — ц" + ~ ~( — ц . (сс — с)" = ', -Е(-ц' ". ' (~-*) +Е(-ц! " ( -*) ( — ц* (й — !)" + ~ ( — ц* (й — с)" + !с" ( — ц — (сс — с) + сс Ответы к упражнениям 905 ~'(-Цс ", ' (Д-1)" +Д" (", ()- ). с;( ц* — ' ((,;)-+),- =1 — ~.(-ц' (д — ')" + д" ( ", (д). ()).
(, 23((-' — Ц. — ~~> (- ц, (/с — с)" + Й" 1 (, (/с)( ()с)! ) 23(сс — с)( —,', ~ (-ц " ().-2)-" =) Я(и+ 1,/с). Раздел 1х.х 1 (101 252 1. Сз= — = — =42; 6~ 5)) 6 1 (141 3432 Ст = — = — = 429. 817) 8 1 (Зо') 3. См = — = 9694845. 16 ~ 15( Се = — = — = 132; Раздел 12.4. 1. В(х, С) = 1 + бх + 6хз. 3. Л(х,с) = (1+4х+гхз)2. 5. сс(х, С) = (1 + Зх+ хз)(1 + 2х) + х(1 + Зх + 2хз).
7. Я(х,С) = (1«-Зх«-хз)г(1«-х) Раздел 12.3. 1. 0 = (1 — Ц" = (",) — (",) + (,") — ". + (-Ц" („"). 1 1 1 1 1 1 1 1 1 1 1 1! 2! 3) 4! 5с 6! 7) 8! 9! 14с 15! -4.1 н 10 '. 5. а) 7)(1 — 1+ — ' — -' «- — ' — — '+ — ' — — ') = 1854; 2 0 2с 120 220 Босо б) 7! — 1855 = 3185; + 2 0 + 24 сзо + 720) 1855; г) О. 7. а) 7с(1 — 1+1 + +-,'- — — ') = 1854; б) 7!(1 — 1+ — — — + — ' — + «-+) = 1855; а) 7! — 1855 = 3185; г) 7) — 1855 — 1854 = 1331.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
