Algebra 2-03 arytmetyka modulo n

[ Pobierz całość w formacie PDF ]
Wykład3
Arytmetykamodulo
n
Niech
n
b¦dziedodatni¡liczb¡całkowit¡(
n>
0)iniech
a,b
2
Z
.Mówi-
my,»e
a
przystajedo
b
modulo
n
je±li
n
|
(
a
−
b
)ipiszemywtedy
a
b
mod
n
.
Relacjaprzystawaniamodulo
n
jestrelacj¡równowa»no±ci.Rzeczywi±cie
relacjajestzwrotnabodlaka»dejliczbycałkowitej
a
,liczba0=
a
−
a
jest
podzielnaprzez
n
.Zatem
a
a
mod
n
.Relacjatajestrównie»symetryczna
boje±li
n
|
(
a
−
b
)torównie»
n
|
(
b
−
a
),bo
b
−
a
=
−
(
a
−
b
).Relacjajest
przechodnia,boje±li
n
|
(
a
−
b
)i
n
|
(
b
−
c
)torównie»
n
dzieli(
a
−
b
)+(
b
−
c
)=
a
−
c
,awi¦c
n
|
(
a
−
c
).
c
d
mod
n
to
a
+
c
b
+
d
mod
n
i
a
·
c
b
·
d
mod
n
.Ka»d¡
relacj¦równowa»no±ci,któraspełniapowy»sz¡własno±¢nazywa¢b¦dziemy
kongruencj¡
w
Z
.
Oznaczmyprzez[
a
]klas¦abstrakcjielementu
a
wzgl¦demrelacjiprzysta-
waniamodulo
n
,awi¦c:
[
a
]=
{
b
2
Z
:
n
|
(
a
−
b
)
}
Mo»nazauwa»y¢,»eklasaabstrakcjielementu
a
jestwyznaczonaprzezreszt¦
zdzieleniategoelementuprzez
n
i»edwaelementys¡wrelacjiwtedyi
tylkowtedygdydaj¡t¦sam¡reszt¦przydzieleniuprzez
n
.Awi¦cwtym
przypadkumamydokładnie
n
ró»nychklasabstrakcji:
[0]=
{
x
2
Z
:
n
|
x
}
=
n
Z
[1]=
{
x
2
Z
:
n
|
(
x
−
1)
}
=1+
n
Z
[2]=
{
x
2
Z
:
n
|
(
x
−
2)
}
=2+
n
Z
.
.
.
[
n
−
1]=
{
x
2
Z
:
n
|
(
x
−
(
n
−
1))
}
=(
n
−
1)+
n
Z
Zamiastzapisu[
a
]b¦dziemyzwykleu»ywa¢zapisu
a
,aczasemb¦dziemy
opuszcza¢kresk¦nadelementem.Przez
Z
n
oznacza¢b¦dziemyzbiórklas
abstrakcjirelacjiprzystawaniamodulo
n
,awi¦c:
Z
n
=
{
0
,
1
,...,n
−
1
}
1
Relacjaprzystawaniamodulo
n
majeszczejedn¡bardzowa»n¡własno±¢:
je±li
a
b
mod
n
Wzbiorze
Z
n
mo»nawprowadzi¢nast¦puj¡cedziałania:
¯
a
+
n
¯
b
=
a
+
b
¯
a
·
n
¯
b
=
a
·
b
C
zy
d
z
i
ała
n
iat
es¡
dob
rzeo
kre±l
one?
C
zym
o»esi¦zdarzy¢takasytuacja,»e
a
=
c,b
=
d
a
a
+
c
6
=
b
+
d
lub
a
·
c
6
=
b
·
d
?Otó»nie,awynikatozf
a
kt
u,
»erelacjaprzystawaniamodulo
n
jestkongruencj¡.Je±limamy
a
=
c,b
=
d
to
a
c
mo
d
n
,b
d
mod
n
,
as
t¡d
a
+
c
b
+
d
mod
n,a
·
c
b
·
d
mod
n
,
awi¦c
a
+
c
=
b
+
d
i
a
·
c
6
=
b
·
d
Oczywi±ciespełnionajestnast¦puj¡cawłasno±¢:
¯
a
=
¯
b
()
a
b
mod
n
idwieklasys¡alborównealbos¡rozł¡czne.
Twierdzenie1
Dladowolnychklas
¯
a,
¯
b,
¯
c
2
Z
n
mamy:
(i)¯
a
+(
¯
b
+¯
c
)=(¯
a
+
¯
b
)+¯
c,
(ii)¯
a
+
¯
b
=
¯
b
+¯
a,
(iii)¯
a
+
¯
0=
¯
0+¯
a
=¯
a,
(iv)¯
a
+
¯
Przykład
Skonstruowa¢tabelkidziała«wpier±cieniu
Z
5
.
·
n
01234
000000
101234
202413
303142
404321
Struktur¦(
Z
n
,
+
,
·
)nazywa¢b¦dziemy
pier±cieniemresztmodulo
n
.
Pytanie,któreterazsi¦pojawiato:Kiedyrównanie
a
·
n
x
=1marozwi¡-
zaniewpier±cieniu
Z
n
?Odpowiedzimo»naudzieli¢korzystaj¡czwcze±niej-
szychrozwa»a«dotycz¡cychrówna«diofantycznych.
Twierdzenie2
Równaniea
·
n
x
=1
marozwi¡zaniewpier±cieniuZ
n
wtedy
itylkowtedygdyliczbyains¡wzgl¦dniepierwsze.Inaczejmówi¡cliczbaa
jestodwracalnamodulonwtedyitylkowtedygdyNWD
(
a,b
)=1
.
2
n
−
a
+¯
a
=
¯
0
,
(v)¯
a
·
(
¯
b
·
¯
c
)=(¯
a
·
¯
b
)
·
¯
c,
(vi)¯
a
·
¯
b
=
¯
b
·
¯
a,
(vii)¯
a
·
¯
1=
¯
1
·
¯
a
=¯
a,
(viii)¯
a
·
(
¯
b
+¯
c
)=¯
a
·
¯
b
+¯
a
·
¯
c,
(ix)(
¯
b
+¯
c
)
·
¯
a
=
¯
b
·
¯
a
+¯
c
·
¯
a.
n
−
a
=
¯
+
n
01234
001234
112340
223401
334012
440123
Dowód
Je±liNWD(
a,n
)=1toistniej¡liczbycałkowite
u,v
takie,»e
au
+
nv
=1wtedymodulo
n
mamy¯
a
·
¯
v
=1,awi¦cliczba
a
jestodwracalna
modulo
n
.Je±literazliczba
a
jestodwracalnamodulo
n
toistnieje
b
,»e
a
·
n
b
=1i
a
·
b
−
1=0tooznacza,»e
n
|
(
ab
−
1),awi¦cistnieje
k
,»e
ab
−
1=
kn
,zatemrównanie
ax
+
ny
=1marozwi¡zanie,atooznacza,»e
liczby
a
i
n
s¡wzgl¦dniepierwsze.
Zadanie
Znale¹¢elementodwrotny(je±liistnieje)do25modulo34.
Bezpo±redni¡konsekwencj¡tegoTwierdzeniajestnast¦puj¡ceTwierdze-
nie:
Twierdzenie3
Je±lip>
0
jestliczb¡pierwsz¡towpier±cieniuZ
p
ka»dy
niezerowyelemntjestodwracalny.
Niezerowyelement
a
pier±cienia
Z
n
nazywamydzielnikiemzeraje±liist-
niejeniezerowyelement
b
,taki»e
ab
=0w
Z
n
.Naprzykładelement2jest
dzielnikiemzeraw
Z
6
bow
Z
6
mamy2
·
3=0.
Twierdzenie4
Pier±cie«Z
n
posiadadzielnikizerawtedyitylkowtedygdy
nniejestliczb¡pierwsz¡.
Pier±cie«
Z
p
gdzie
p
jestdodatni¡liczb¡pierwsz¡nazywamy
ciałem
resztmodulo
p
.
Twierdzenie5
Je±lia,bs¡liczbamiodwracalnymimodulontoichiloczyn
te»jestodwracalnymodulon.
Dowód
Istniej¡liczby
a
0
i
b
0
takie,»emodulo
n
mamy
a
·
a
0
=1i
b
·
b
0
=1
wtedyliczba
b
0
·
a
0
jestodwrotnado
ab
modulo
n
.
3
[ Pobierz całość w formacie PDF ]