Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
12
1.PodzielnośćialgorytmEuklidesa
Zadanie1.1.6
Zbadajpodzielność:
a)liczbpostaci4n+1przezliczby3n;
b)liczbpostaci5n+1przezliczby4n;
c)liczbpostaci(k+1)
n+1przezliczbykn,k–ustalonaliczbanaturalna;
d)liczbpostaci3n+nprzezliczby2n.
KrzysztofKowitzzauważył,że2nniedzieli3n+ndlażadnychliczbpa-
rzystychnorazdlan=16k+r,gdzier∈{1,3,5,7,9,11,15}.Biorącmoduł
16,np.dlan=16+5otrzymujemy:
Table[Mod[3^(16k+5)+16k+5,16],{k,0,20}]
{8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8}
Zkongruencji316k+5+16k+5≡8(mod16),216k+5≡0(mod16)wynika,
że216k+5niedzieli316k+5+16k+5.Pozostajesprawdzić,że216k+13niedzieli
316k+13+16k+13dlażadnejliczbycałkowitejdodatniejk.Tutajmożna
skorzystaćzpomocyprogramuMathematica;zapomocąkomendy
Table[Mod[3^(16*i+13)+16*i+13,2^14],{i,0,2^14-1}]
możnazauważyć,żeciągresztliczbpostaci316n+13+16n+13modulo214jest
okresowy,niewystępujewnimliczba0ijegookreswynosi214.
Zadanie1.1.7([ETL2],zad.6,s.13)
Udowodnij,żedlakażdejliczbynaturalnejnidlakażdejliczbynaturalnej
nieparzystejkliczba1+2+...+njestdzielnikiemliczby1k+2k+...+nk.
Dorozwiązaniategozadaniawykorzystamykilkawzorów,któremożemy
otrzymać,wywołującjezpamięciprogramuMathematica(obokzdefiniowa-
nejwprogramiesumyzamieściliśmytakżewzórjawnydlak=1,3,5).
Sum[i,{i,1,n}]=1/2n(1+n)
Sum[i^3,{i,1,n}]=1/4n^2(1+n)^2
Sum[i^5,{i,1,n}]=1/12n^2(1+n)^2(-1+2n+2n^2)
Dlak=1podzielnośćjestoczywista,dlak=3także,natomiastdlak=5
należywykazać,że6jestdzielnikiemliczbyn(n+1)(2n2+2n−1)dladowolnej
liczbynaturalnejn.Jasnejest,że2dzielijednązliczbn,n+1,natomiast3
dzielijednązliczbn,n+1,2n2+2n−1,cosprawdzasię,rozpatrująctrzy
przypadki,wzależnościodresztyzdzielenianprzez3.
Dlatrzechkonkretnychwartościksprawdziliśmypodzielnośćdladowol-
negon.Ajakbędziedladowolnegonieparzystegok?
Rozpoczniemyodpodzielności:dladowolnejliczbnaturalnejnieparzy-
stejkidladowolnychliczbcałkowitycha,bzachodzipodzielność:
a+b|ak+bk.
