Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.3.Zadania
21
Widentycznysposóbdowodzimy,żed|b.
Załóżmyteraz,żepewnaliczbanaturalna
c
dzielizarówno
a
,jak
b
.Wówczas
c
dzieli
d=Ia+βb
,codowodzi,że
d
jestnajwiększymwspólnymdzielnikiem
a
i
b
.
Korzystajączciąguzwiązków(1.5)orazfaktu,że
rk
jestnajwiększymwspólnym
dzielnikiem
a
i
b
,możnawinnysposóbudowodnićtwierdzenie1.9.Cowięcej,widać
także,żealgorytmEuklidesapozwalaefektywniewyrazić
NWD(a,b)
jakoliniową
kombinacjęliczbaib.
Jeśli
NWD(a,b)=1
,wówczasmówimy,że
a
i
b
sąliczbamiwzględniepierwszy-
miipiszemy(a,b)=1lubaib.
Liczbycałkowite
I,β∈Ztakie,że
Cowięcej,liczbycałkowite
Euklidesa.
Wniosek10100
a
i
b
sąwzględniepierwszewtedyitylkowtedy,gdyistnieją
I
i
Ia+βb=1.
β
możnawyznaczyćzapomocąalgorytmu
1.3.Zadania
Zadanie1010Dlapodanychliczbcałkowitych
a,b
wskaż
!,r∈Z
takie,że
a=b!+r,
0⩽r<b.
1.a=17,b=3;
2.a=3,b=13;
3.a=−34,b=16.
Zadanie1020WykorzystującalgorytmEuklidesa,dlapodanychliczbcałkowitych
a,b
znajd§d=NWD(a,b)oraztakieI,β∈Z,żed=Ia+βb.
1.a=246,b=348.
2.a=105,b=800.
Zadanie1030Wykaż,żejeśli
a,b,c∈N−{0}
i
c≡a
(
modb
),wówczas
NWD(a,b)=
NWD(b,c).
Wskazówka.Wykorzystajdefnicję
NWD
liczbcałkowitychifakt,że
c=!b+a
dlapewnego
!∈Z.
