Rozdziaª
1
Zadania
1.1
Liczb
y
pierwsze
1.
Wyk
orzystuj¡c
sito
Eratostenesa
wyznaczy¢
wszystkie
liczb
y
pierwsze
mniejsze
ni»
200
.
2.
Wyliczy¢
na
jwi¦kszy
wsp
óln
y
dzielnik
d
liczb
n
i
m
oraz
znale¹¢
liczb
y
caªk
o
wite
p
i
q
takie,
»e
d
=
pn
+
q
m
.
(a)
n
=
21
,
m
=
55
.
(b)
n
=
15
,
m
=
303
.
(c)
n
=
303
,
m
=
159
.
(d)
n
=
77
,
m
=
371
.
(e)
n
=
183
,
m
=
305
.
3.
Udo
w
o
dni¢,
»e
dla
do
w
oln
yc
h
liczb
naturaln
yc
h
do
datnic
h
a
i
b
mam
y
(
n
a
1
;
n
b
1)
=
n
(
a;b
)
1
,
gdzie
n
>
1
jest
liczb¡
naturaln¡.
4.
Znale¹¢
wzór
na
na
jwi¦ksz¡
p
ot¦g¦
liczb
y
pierwszej
p
dziel¡cej
n
!
.
5.
Rozªo»y¢
na
czynniki
pierwsze
liczb
¦
100!
.
6.
Iloma
zerami
zak
o«czone
jest
rozwini¦cie
dziesi¦tne
liczb
y
1000!
?
7.
Iloma
zerami
zak
o«czone
jest
przedsta
wienie
w
systemie
szesnastk
o-
wym
liczb
y
200!
?
8.
Udo
w
o
dni¢,
»e
S
:=
1
+
1
2
+
+
1
n
;
nie
jest
liczb¡
caªk
o
wit¡
dla
n
>
1
.
1
9.
Udo
w
o
dni¢,
»e
S
:=
1
+
1
3
+
1
5
+
+
1
2
n
1
nie
jest
liczb¡
caªk
o
wit¡
dla
n
>
1
.
10.
Niec
h
a
1
,
.
.
.
,
a
n
,
n
1
,
b
¦d¡
niezero
wymi
liczbami
caªk
o
wit
ymi.
Przypu±¢m
y
,
»e
istnieje
liczba
pierwsza
p
i
do
datnia
liczba
caªk
o
wita
k
takie,
»e
p
k
j
a
i
dla
p
ewnego
i
oraz
p
k
-
a
j
dla
j
6=
i
.
Udo
w
o
dni¢,
»e
S
:=
1
a
1
+
+
1
a
n
nie
jest
liczb¡
caªk
o
wit¡.
11.
Udo
w
o
dni¢,
»e
je±li
n
jest
liczb¡
zªo»on¡,
to
n
ma
dzielnik
pierwszy
nie
przekracza
j¡cy
p
n
.
12.
Udo
w
o
dni¢,
»e
je±li
na
jmniejsza
liczba
pierwsza
p
dziel¡ca
liczb
¦
caªk
o
wit¡
do
datni¡
n
przekracza
3
p
n
,
to
n
p
=
1
lub
n
p
jest
liczb¡
pierwsz¡.
13.
Niec
h
p
b
¦dzie
liczb¡
pierwsz¡.
Udo
w
o
dni¢,
»e
p
k
liczb¡
p
o
dzieln¡
przez
p
,
dla
1
k
p
1
.
14.
Niec
h
p
b
¦dzie
liczb¡
pierwsz¡.
Udo
w
o
dni¢,
»e
p
j
np
p
n
dla
k
a»dej
liczb
y
naturalnej
n
1
.
15.
Niec
h
p
k
oznacza
k
-t¡
liczb
¦
pierwsz¡,
k
1
.
Udo
w
o
dni¢,
»e
p
k
<
2
2
k
.
W
s
k
a
z
ó
w
k
a.
Udo
w
o
dni¢,
»e
p
k
p
1
p
k
1
+
1
.
16.
Udo
w
o
dni¢,
»e
(
x
)
log(log
(
x
))
dla
x
>
1
.
17.
Udo
w
o
dni¢,
»e
p
x
2
(
x
)
.
W
s
k
a
z
ó
w
k
a.
Wyk
orzysta¢
fakt,
»e
k
a»da
liczba
naturalna
mo»e
b
y¢
przedsta
wiona
w
p
ostaci
mn
2
,
gdzie
m
jest
liczb¡
b
ezkw
adrato
w
¡.
18.
Udo
w
o
dni¢,
»e
(
x
)
log
x
2
log
2
.
19.
Udo
w
o
dni¢,
»e
(
x
)
9
x
log
2
log
x
,
dla
x
2
.
W
s
k
a
z
ó
w
k
a.
Wyk
orzysta¢
fakt,
»e
Q
n<p
2
n
p
j
2
n
n
.
2
20.
Niec
h
a
,
b
b
¦d¡
wzgl¦dnie
pierwszymi
liczbami
naturaln
ymi
takimi,
»e
ab
=
n
k
dla
p
ewn
yc
h
liczb
naturaln
yc
h
n
i
k
.
P
ok
aza¢,
»e
istniej¡
liczb
y
naturalne
d
i
e
takie,
»e
a
=
c
k
i
b
=
d
k
.
21.
Udo
w
o
dni¢,
»e
je±li
x
,
y
i
z
s¡
parami
wzgl¦dnie
pierwszymi
liczba-
mi
naturaln
ymi
b
¦d¡cymi
rozwi¡zaniem
ró
wnania
x
2
+
y
2
=
z
2
,
to
istniej¡
wzgl¦dnie
pierwsze
liczb
y
naturalne
a
i
b
,
z
któryc
h
jedna
jest
parzysta,
takie,
»e
x
=
a
2
b
2
,
y
=
2
ab
i
z
=
a
2
+
b
2
(z
dokªadno±ci¡
do
zamian
y
miejscami
liczb
x
i
y
).
22.
Udo
w
o
dni¢,
»e
ró
wnanie
x
4
+
y
4
=
z
2
nie
ma
nietrywialn
yc
h
rozwi¡-
za«
naturaln
yc
h.
23.
Udo
w
o
dni¢,
»e
ró
wnanie
x
4
y
4
=
z
2
nie
ma
nietrywialn
yc
h
rozwi¡-
za«
naturaln
yc
h.
24.
Udo
w
o
dni¢,
»e
je±li
f
jest
wielomianem
do
datniego
stopnia
o
wsp
óª-
czynnik
ac
h
caªk
o
wit
yc
h,
to
dla
niesk
o«czenie
wielu
liczb
pierwszyc
h
p
istnieje
liczba
caªk
o
wita
x
o
wªasno±ci
p
j
f
(
x
)
.
25.
Niec
h
q
b
¦dzie
liczb¡
pierwsz¡.
Udo
w
o
dni¢,
»e
istnieje
niesk
o«czenie
wiele
liczb
pierwszyc
h
o
wªasno±ci
q
j
p
1
.
26.
Niec
h
F
m
:=
2
2
m
+
1
,
m
0
,
b
¦dzie
liczb¡
F
ermata.
P
ok
aza¢,
»e
F
m
=
F
1
F
m
1
+
2
,
oraz,
»e
k
a»dy
dzielnik
pierwszy
liczb
y
F
m
jest
p
ostaci
2
m
+1
k
+
1
.
1.2
Kongruencje
27.
Udo
w
o
dni¢,
»e
liczba
10
6
1
jest
p
o
dzielna
przez
13
.
28.
Udo
w
o
dni¢,
»e
liczba
10
8
+
1
jest
p
o
dzielna
przez
17
.
29.
Udo
w
o
dni¢,
»e
liczba
10
9
+
1
jest
p
o
dzielna
przez
19
.
30.
Udo
w
o
dni¢,
»e
je±li
3
-
n
,
to
3
j
n
4
+
n
2
+
1
.
31.
Udo
w
o
dni¢,
»e
je±li
3
j
2
2
n
1
dla
k
a»dej
liczb
y
naturalnej
n
.
32.
Udo
w
o
dni¢,
»e
P
n
1
j
=1
j
0
(mo
d
n
)
wtedy
i
t
ylk
o
wtedy
,
gdy
n
jest
liczb¡
nieparzyst¡.
3
33.
Udo
w
o
dni¢,
»e
P
n
1
j
=1
j
3
0
(mo
d
n
)
wtedy
i
t
ylk
o
wtedy
,
gdy
n
6
2
(mo
d
4)
.
34.
Rozwi¡za¢
nast¦puj¡ce
k
ongruencje.
(a)
3
x
4
(mo
d
7)
(b)
27
x
25
(mo
d
256)
(c)
2
x
37
(mo
d
21)
(d)
10
x
15
(mo
d
35)
(e)
3
x
7
(mo
d
18)
35.
Rozwi¡za¢
nast¦puj¡ce
ukªady
k
ongruencji.
(a)
x
3
(mo
d
4)
,
x
2
(mo
d
7)
,
x
1
(mo
d
9)
(b)
x
2
(mo
d
3)
,
x
3
(mo
d
5)
,
x
1
(mo
d
8)
,
x
9
(mo
d
11)
(c)
2
x
1
(mo
d
3)
,
3
x
1
(mo
d
4)
,
5
x
4
(mo
d
7)
36.
W
k
oszu
zna
jduje
si¦
n
ja
jek.
Je±li
wyjm
ujem
y
z
k
osza
p
o
2
(
3
,
4
,
5
,
6
o
dp
o
wiednio)
ja
jk
a,
to
na
k
oniec
zosta
je
w
k
oszu
1
(
2
,
3
,
4
,
5
o
dp
o
wiednio)
ja
jk
o.
Je±li
wyjm
ujem
y
z
k
osza
p
o
7
ja
jek,
to
na
k
oniec
nie
zostanie
nam
ani
jedno
jak
o.
Jak
a
jest
na
jmniejsza
mo»liw
a
w
arto±¢
n
?
1.3
F
unk
cja
Eulera
37.
Wyliczy¢
'
(1000)
,
'
(125)
,
'
(180)
,
'
(360)
,
'
(1001)
.
38.
Znale¹¢
wszystkie
liczb
y
naturalne
n
,
dla
któryc
h
'
(
n
)
=
m
.
(a)
m
=
14
.
(b)
m
=
8
.
(c)
m
=
12
.
39.
Udo
w
o
dni¢,
»e
'
(
m
k
)
=
m
k
1
'
(
m
)
dla
do
w
oln
yc
h
liczb
naturaln
yc
h
m
i
k
.
40.
Udo
w
o
dni¢,
»e
'
(
n
)
jest
liczb¡
parzyst¡
dla
wszystkic
h
n
>
2
.
41.
Udo
w
o
dni¢,
»e
je±li
d
=
(
m;
n
)
dla
liczb
naturaln
yc
h
m
i
n
,
to
'
(
mn
)
=
d'
(
m
)
'
(
n
)
='
(
d
)
.
42.
Udo
w
o
dni¢,
»e
je±li
d
j
n
,
to
'
(
d
)
j
'
(
n
)
.
43.
Udo
w
o
dni¢,
»e
a
12
1
(mo
d
7)
dla
k
a»dej
liczb
y
naturalnej
a
sp
eª-
nia
j¡cej
w
arunek
(
a;
7)
=
1
.
4
44.
Udo
w
o
dni¢,
»e
a
12
1
(mo
d
65)
dla
k
a»dej
liczb
y
naturalnej
n
sp
eª-
nia
j¡cej
w
arunek
(
a;
65)
=
1
.
45.
Udo
w
o
dni¢,
»e
n
j
'
(
a
n
1)
dla
wszystkic
h
a
>
n
.
46.
Udo
w
o
dni¢,
»e
n
-
2
n
1
dla
wszystkic
h
n
>
1
.
47.
Udo
w
o
dni¢,
»e
'
(
n
)
n
=
Q
p
j
n
1
1
p
in
terpretuj¡c
lew
¡
stron¡
ja-
k
o
pra
wdop
o
dobie«st
w
o,
»e
loso
w
o
wybrana
liczb¡
ze
zbioru
f
1
;
:
:
:
;
n
g
jest
wzgl¦dnie
pierwsza
z
n
.
48.
Znale¹¢
dwie
ostatnie
cyfry
liczb
y
3
1000
.
49.
Znale¹¢
dwie
ostatnie
cyfry
liczb
y
2
1000
.
50.
Zªama¢
system
kryptograczn
y
RSA,
w
którym
n
=
9991
,
za±
ja
w-
n
ym
kluczem
szyfruj¡cym
jest
liczba
37
.
1.4
Elemen
t
y
teorii
pier±cieni
51.
Które
z
p
o
dan
yc
h
zbioró
w
s¡
pier±cieniami
ze
wzgl¦du
na
zwykªe
dziaªania
do
da
w
ania
i
mno»enia
liczb?
(a)
zbiór
liczb
naturaln
yc
h.
(b)
zbiór
liczb
caªk
o
wit
yc
h
p
o
dzieln
yc
h
przez
2
lub
3
.
(c)
zbiór
liczb
p
ostaci
a
+
b
p
2
,
gdzie
liczb
y
a
i
b
s¡
caªk
o
wite.
(d)
zbiór
liczb
p
ostaci
a
2
k
,
gdzie
liczb
y
a
i
k
s¡
caªk
o
wite,
k
0
.
(e)
zbiór
liczb
p
ostaci
a
+
b
3
p
2
,
gdzie
liczb
y
a
i
b
s¡
caªk
o
wite.
52.
Które
z
p
o
dan
yc
h
zbioró
w
funk
cji
okre±lon
yc
h
w
przedziale
[0
;
1]
i
przyjm
uj¡cyc
h
w
arto±ci
rzeczywiste
s¡
pier±cieniami
ze
wzgl¦du
na
zwykªe
dziaªania
do
da
w
ania
i
mno»enia
funk
cji?
(a)
zbiór
funk
cji
ci¡
gªyc
h
w
przedziale
[0
;
1]
.
(b)
zbiór
funk
cji
wielomiano
wyc
h,
któryc
h
wyraz
w
oln
y
jest
liczb¡
caª-
k
o
wit¡.
(c)
zbiór
funk
cji
f
,
dla
któryc
h
f
(
1
2
)
=
0
.
(d)
zbiór
funk
cji
f
,
dla
któryc
h
f
(0)
=
f
(1)
.
(e)
zbiór
funk
cji
f
,
dla
któryc
h
istnieje
liczba
caªk
o
wita
k
o
wªasno±ci
2
k
f
(0)
=
f
(1)
.
53.
Udo
w
o
dni¢,
»e
k
a»dy
sk
o«czon
y
pier±cie«
b
ez
dzielnik
ó
w
zera
jest
ciaªem.
5
54.
Wielomian
f
2
R
[
X
]
da
je
przy
dzieleniu
przez
X
2
reszt¦
1
,
za±
przy
dzieleniu
przez
X
1
reszt¦
2
.
Jak
¡
reszt¦
da
je
ten
wielomian
przy
dzieleniu
przez
(
X
1)(
X
2)
?
55.
Wyznaczy¢
na
jwi¦kszy
wsp
óln
y
dzielnik
d
wielomianó
w
f
;
g
2
R
[
X
]
oraz
wyznaczy¢
wielomian
y
u;
v
2
R
[
X
]
takie,
»e
d
=
uf
+
v
g
.
(a)
f
=
X
4
+
X
2
+
1
,
g
=
X
2
+
1
.
(b)
f
=
X
4
4
X
3
+
6
X
2
4
X
+
1
,
g
=
X
3
X
2
+
X
1
.
(c)
f
=
X
4
+
2
X
3
X
2
4
X
2
,
g
=
X
4
+
X
3
X
2
2
X
2
.
56.
Znale¹¢
elemen
t
o
dwrotn
y
do
w
arst
wy
wielomian
u
1
+
X
2
w
pier-
±cieniu
R
[
X
]
=
(
X
3
)
.
1.5
Ciaªa
sk
o«czone
57.
Wypisa¢
unormo
w
ane
wielomian
y
nierozkªadalne
stopnia
nie
wi¦k-
szego
ni»
4
nad
F
2
i
F
3
.
58.
Przedsta
wi¢
wielomian
f
w
p
ostaci
ilo
czyn
u
wielomianó
w
nierozkªa-
daln
yc
h
nad
ciaªem
F
p
.
(a)
f
=
X
16
X
,
p
=
2
.
(b)
f
=
X
9
X
,
p
=
3
.
(c)
f
=
X
27
X
,
p
=
3
.
59.
Wyznaczy¢
liczb
¦
unormo
w
an
yc
h
wielomianó
w
nierozkªadaln
yc
h
stopnia
nie
wi¦kszego
ni»
8
nad
F
2
,
F
3
i
F
5
.
60.
Przedsta
wi¢
wielomian
f
w
p
ostaci
ilo
czyn
u
wielomianó
w
nierozkªa-
daln
yc
h
nad
ciaªem
F
p
.
(a)
f
=
X
7
+
X
4
+
X
2
+
X
+
1
,
p
=
2
.
(b)
f
=
X
8
+
7
+2
X
6
+
X
2
+
X
+
2
,
p
=
3
.
(c)
f
=
X
9
+
2
X
7
+
X
6
+
3
X
5
+
X
4
+
2
X
2
+
3
X
+
3
,
p
=
5
.
61.
Czy
w
przedsta
wieniu
wielomian
u
f
w
p
ostaci
ilo
czyn
u
wielomianó
w
nierozkªadaln
yc
h
nad
F
p
k
a»dy
czynnik
wyst¦puje
w
p
ot¦dze
1
?
(a)
f
=
X
6
+
X
3
+
X
2
+
X
,
p
=
2
.
(b)
f
=
X
6
+
X
4
+
X
2
+
X
,
p
=
3
.
(c)
f
=
X
6
+
2
X
5
+
3
X
4
+
2
X
3
+
4
X
2
+
X
+
4
,
p
=
5
.
62.
W
ciele
F
q
rozwi¡za¢
ró
wnanie
f
(
x
)
=
0
.
6
(a)
f
=
X
2
+
1
,
q
=
9
.
(b)
f
=
X
2
+
X
+
2
,
q
=
9
.
(c)
f
=
X
2
+
2
X
+
3
,
q
=
25
.
63.
Niec
h
p
b
¦dzie
liczba
pierwsza
i
2
F
p
2
b
¦dzie
pierwiastkiem
wie-
lomian
u
X
2
+
aX
+
b
,
gdzie
a;
b
2
F
p
.
Udo
w
o
dni¢,
»e
je±li
62
F
p
,
to
(
c
+
d
)
p
+1
=
d
2
acd
+
bc
2
.
Wyk
orzystuj¡c
ten
fakt
p
oliczy¢
(2
+
3
i
)
101
,
gdzie
i
jest
pierwiastkiem
z
1
w
F
19
2
.
64.
Udo
w
o
dni¢,
»e
je±li
f
2
F
p
[
X
]
,
to
f
0
=
0
wtedy
i
t
ylk
o
wtedy
,
gdy
istnieje
wielomian
g
2
F
p
[
X
]
takie,
»e
f
=
g
p
.
1.6
Elemen
t
y
teorii
grup
65.
Które
z
nast¦puj¡cyc
h
zbioró
w
s¡
grupami
ze
wzgl¦du
na
do
da
w
anie
liczb?
(a)
zbiór
liczb
naturaln
yc
h.
(b)
zbiór
liczb
caªk
o
wit
yc
h.
(c)
zbiór
liczb
rzeczywist
yc
h.
(d)
zbiór
liczb
caªk
o
wit
yc
h
p
o
dzieln
yc
h
przez
ustalon¡
liczb
¦
naturaln¡
n
.
(e)
f
0
;
1
;
2
;
3
;
4
g
.
66.
Które
z
nast¦puj¡cyc
h
zbioró
w
s¡
grupami
ze
wzgl¦du
na
mno»enie
liczb?
(a)
zbiór
liczb
rzeczywist
yc
h.
(b)
zbiór
liczb
rzeczywist
yc
h
ró»n
yc
h
o
d
0
.
(c)
zbiór
liczb
rzeczywist
yc
h
wi¦kszyc
h
o
d
0
.
(d)
zbiór
liczb
caªk
o
wit
yc
h.
(e)
zbiór
liczb
zesp
olon
yc
h
o
mo
dule
1
.
67.
Wyznaczy¢
rz¦dy
elemen
tó
w
grup
F
7
,
F
8
i
F
9
.
68.
Wyliczy¢
ilo±¢
generatoró
w
grup
y
F
p
2
.
P
ok
aza¢,
»e
wielomian
X
2
+
c
jest
nierozkªadaln
y
nad
F
p
.
Niec
h
F
p
2
=
F
p
[
X
]
=
(
X
2
+
a
)
i
niec
h
b
¦dzie
w
arst
w
¡
X
w
F
p
2
.
Spra
wdzi¢
czy
elemen
t
y
,
+
1
i
2
+
1
s¡
generatorami
grup
y
F
p
2
.
Przedsta
wi¢
w
p
ostaci
a
+
b
o
dwrotno±¢
elemen
tu
2
+
3
2
F
p
2
.
(a)
p
=
3
,
c
=
1
.
(b)
p
=
5
,
c
=
3
.
7
(c)
p
=
7
,
c
=
2
.
69.
Udo
w
o
dni¢,
»e
wielomian
X
4
+
X
+
1
2
F
2
[
X
]
jest
nierozkªadaln
y
w
F
2
[
X
]
.
Niec
h
F
16
=
F
2
[
X
]
=
(
X
4
+
X
+
1)
i
niec
h
b
¦dzie
w
arst
w
a
jedynki.
Ile
generatoró
w
ma
grupa
F
16
?
Udo
w
o
dni¢,
»e
+
1
jest
generatorem
tej
grup
y
.
Znale¹¢
liczb
¦
naturaln¡
k
o
wªasno±ci
(
+
1)
k
=
i
przedsta
wi¢
w
p
ostaci
a
+
b
+
c
2
+
d
3
o
dwrotno±¢
elemen
tu
.
70.
Jakie
w
arunki
m
usz¡
sp
eªnia¢
liczb
p
i
k
,
ab
y
k
a»dy
elemen
t
grup
y
F
p
k
ró»n
y
o
d
1
b
yª
jej
generatorem?
71.
Jakie
w
arunki
m
usz¡
sp
eªnia¢
liczb
p
i
k
,
ab
y
k
a»dy
elemen
t
grup
y
F
p
k
ró»n
y
o
d
1
b
yª
jej
generatorem
lub
kw
adratem
generatora?
72.
Wyliczy¢
rz¦dy
elemen
tó
w
grup
(
Z
=
8
Z
)
,
(
Z
=
15
Z
)
i
(
Z
=
16
Z
)
.
73.
Udo
w
o
dni¢,
ze
grupa
(
Z
=p
k
Z
)
jest
cykliczna
dla
liczb
y
pierwszej
p
>
2
oraz
do
w
olnej
liczb
y
naturalnej
k
>
0
.
W
s
k
a
z
ó
w
k
a.
Niec
h
a
b
¦dzie
liczb¡
generuj¡c¡
grup
¦
F
p
.
Wtedy
jedna
z
w
arst
w
a
lub
(
p
+
1)
a
jest
generatorem
grup
y
(
Z
=p
k
Z
)
.
74.
Wyliczy¢
p
o
dgrup
y
h
6
i
,
h
10
i
i
h
6
;
10
i
w
Z
=
15
Z
.
1.7
Elemen
t
y
teorii
k
o
do
w
ania
75.
Niec
h
m
(
n;
k
)
oznacza
maksymaln¡
mo»liw
¡
ilo±¢
sªó
w
w
k
o
dzie
C
F
n
2
,
którego
minimalna
o
dlegªo±¢
jest
nie
mniejsza
ni»
k
.
Udo
w
o
dni¢
nast¦puj¡ce
wªasno±ci
sym
b
olu
m
(
n;
k
)
.
(a)
m
(3
k
;
2
k
)
=
4
.
(b)
m
(
n
+
d;
d
)
2
m
(
n;
d
)
.
(c)
m
(2
n;
d
)
(
m
(
n;
d
))
2
.
(d)
m
(
n;
d
)
2
m
(
n
1
;
d
)
.
(e)
(
P
k
i
=0
n
i
)
m
(
n;
2
k
+
1)
2
n
.
76.
Udo
w
o
dni¢,
»e
k
o
d
ISBN
jest
rozp
ozna
je
tzw.
ÿczeski
bª¡d",
p
ole-
ga
j¡cy
na
przesta
wieniu
dw
ó
c
h
k
olejn
yc
h
znak
ó
w.
8
77.
Wyznaczy¢
minimaln¡
o
dlegªo±¢
k
o
du
C
F
8
2
,
którego
macierz
k
on-
troli
parzysto±ci
H
ma
p
osta¢
H
=
2
6
6
4
1
1
0
0
1
0
0
0
0
0
1
1
0
1
0
0
1
0
1
0
0
0
1
0
0
1
0
1
0
0
0
1
3
7
7
5
:
Zakªada
j¡c,
»e
przy
przesyªaniu
o±miu
bitó
w
wyst¦puje
co
na
jwy»ej
jeden
bª¡d,
okre±li¢
jaki
ci¡
g
b
yª
przesyªan
y
,
je±li
otrzymano
ci¡
g
v
.
(a)
v
=
(1
;
0
;
0
;
0
;
1
;
0
;
1
;
0)
.
(b)
v
=
(0
;
1
;
0
;
1
;
1
;
1
;
0
;
0)
.
(c)
v
=
(0
;
0
;
0
;
1
;
1
;
1
;
0
;
1)
.
(d)
v
=
(0
;
1
;
1
;
1
;
1
;
1
;
1
;
1)
.
(e)
v
=
(0
;
0
;
1
;
0
;
1
;
1
;
0
;
0)
.
78.
Wyznaczy¢
minimaln¡
o
dlegªo±¢
k
o
du
C
F
7
2
,
którego
macierz
k
on-
troli
parzysto±ci
H
ma
p
osta¢
H
=
2
4
1
1
0
1
1
0
0
1
0
1
1
0
1
0
0
1
1
1
0
0
1
3
5
:
79.
Wyznaczy¢
minimaln¡
o
dlegªo±¢
k
o
du
C
F
5
2
,
którego
macierz
k
on-
troli
parzysto±ci
H
ma
p
osta¢
H
=
2
6
6
4
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
3
7
7
5
:
80.
Wyznaczy¢
minimalna
o
dlegªo±¢
k
o
du
C
F
8
3
,
którego
macierz
k
on-
troli
parzysto±ci
H
ma
p
osta¢
H
=
2
6
6
4
1
0
1
0
1
0
0
0
0
1
0
0
0
1
0
0
1
1
1
1
0
0
1
0
2
0
1
1
0
0
0
1
3
7
7
5
:
Znale¹¢
baz¦
linio
w
¡
k
o
du
C
nad
F
3
.
81.
Wyznaczy¢
macierz
k
on
troli
parzysto±ci
wszystkic
h
k
o
dó
w
cyklicz-
n
yc
h
dªugo±ci
n
nad
ciaªem
F
p
.
(a)
p
=
2
,
n
=
5
.
(b)
p
=
2
,
n
=
9
.
(c)
p
=
3
,
n
=
8
.
9
Rozdziaª
2
Rozwi¡zania
2.1
Liczb
y
pierwsze
1.
2
,
3
,
5
,
7
,
11
,
13
,
17
,
19
,
23
,
29
,
31
,
37
,
41
,
43
,
47
,
53
,
59
,
61
,
67
,
71
,
73
,
79
,
83
,
89
,
97
,
101
,
103
,
107
,
109
,
113
,
127
,
131
,
139
,
149
,
151
,
157
,
163
,
167
,
173
,
179
,
181
,
191
,
193
,
197
,
199
.
2.
(a)
.
d
=
1
,
p
=
21
,
q
=
8
,
gdy»
55
=
2
21
+
13
;
13
=
55
2
21
;
21
=
1
13
+
8
;
8
=
21
13
=
55
+
3
21
;
13
=
1
8
+
5
;
5
=
13
8
=
2
55
5
21
;
8
=
1
5
+
3
;
3
=
8
5
=
3
55
+
8
21
;
5
=
1
3
+
2
;
2
=
5
3
=
5
55
13
21
;
3
=
1
2
+
1
;
1
=
3
2
=
8
55
+
21
21
;
2
=
2
1
+
0
:
2.
(b)
.
d
=
3
,
p
=
20
,
q
=
1
.
2.
(c)
.
d
=
3
,
p
=
21
,
q
=
40
.
2.
(d)
.
d
=
7
,
p
=
24
,
q
=
5
.
2.
(e)
.
d
=
61
,
p
=
2
,
q
=
1
.
3.
Do
w
ó
d
b
¦dzie
induk
cyjn
y
ze
wzgl¦du
na
max(
a;
b
)
.
at
w
o
zau
w
a»y¢,
»e
teza
jest
pra
wdziw
a,
gdy
a
=
b
.
W
szczególno±ci
zac
ho
dzi
dla
max
(
a;
b
)
=
1
.
Przypu±¢m
y
zatem,
»e
max(
a;
b
)
>
1
oraz,
»e
dla
k
a»dej
pary
liczb
natural-
n
yc
h
do
datnic
h
a
0
i
b
0
o
wªasno±ci
max(
a
0
;
b
0
)
<
max(
a;
b
)
mam
y
(
n
a
0
1
;
n
b
0
1)
=
n
(
a
0
;b
0
)
1
.
Bez
strat
y
ogólno±ci
mo»em
y
zaªo»y¢,
»e
a
b
.
P
oniew
a»
10
przypadek
a
=
b
ju»
rozw
a»ali±m
y
,
wi¦c
ograniczym
y
si¦
teraz
do
sytuacji
a
>
b
.
Wtedy
n
a
=
n
a
b
(
n
b
1)
+
n
a
b
1
,
wi¦c
k
orzysta
j¡c
z
zaªo»enia
induk
cyjnego
oraz
wªasno±ci
na
jwi¦kszego
wsp
ólnego
dzielnik
a
otrzym
ujem
y
,
»e
(
n
a
1
;
n
b
1)
=
(
n
b
1
;
n
a
b
1)
=
n
(
b;a
b
)
1
=
n
(
a;b
)
1
,
gdy»
max(
b;
a
b
)
=
max
(
a;
b
)
.
4.
P
1
k
=1
b
n
p
k
c
.
5.
W
rozkªadzie
liczb
y
100!
na
czynniki
pierwsze
wyst¦puj¡
t
ylk
o
liczb
y
pierwsze
mniejsze
o
d
100
,
które
mo»em
y
wyznaczy¢
przy
p
omo
cy
sita
Era-
tostenesa.
P
onadto
k
a»da
z
nic
h
wyst¦puje
w
p
ot¦dze
opisanej
przez
wzór
z
zadania
4.
W
efek
cie
otrzym
ujem
y
100!
=
2
97
3
48
5
24
7
16
11
9
13
7
17
5
19
5
23
4
29
3
31
3
37
2
41
2
43
2
47
2
53
59
61
67
71
73
83
89
97
:
6.
Liczba
zer
k
o«cz¡cyc
h
rozwini¦cie
dziesi¦tne
liczb
y
1000!
jest
ró
wna
na
jwi¦kszej
p
ot¦dze
liczb
y
5
dziel¡cej
1000!
,
a
wi¦c
200
+
40
+
8
+
1
=
249
.
7.
Liczba
zer
k
o«cz¡cy
przesta
wienie
w
systemie
szesnastk
o
wym
liczb
y
200!
jest
ró
wna
cz¦±ci
caªk
o
witej
ilorazu
z
dzielenia
na
jwi¦kszej
p
ot¦gi
liczb
y
2
dziel¡cej
200!
przez
4
,
a
wi¦c
49
.
8.
Niec
h
k
b
¦dzie
tak
¡
liczb¡
caªk
o
wit¡,
»e
2
k
n
<
2
k
+1
,
za±
m
b
¦dzie
na
jwi¦ksza
wsp
óln¡
wielokrotno±ci¡
liczb
1
,
.
.
.
,
2
k
1
,
2
k
+1
,
.
.
.
,
n
.
Gdyb
y
S
b
yªo
liczb¡
caªk
o
wit¡,
to
mS
te»
b
yªob
y
liczb¡
caªk
o
wit¡.
Z
drugiej
stron
y
m
i
jest
liczb¡
caªk
o
wit¡
dla
i
=
1
;
:
:
:
;
n
,
i
6=
2
k
,
za±
m
2
k
nie
jest
liczb¡
caªk
o
wit¡,
co
pro
w
adzi
do
sprzeczno±ci.
9.
Wybieram
y
maksymaln¡
p
ot¦g¦
liczb
y
3
nie
wi¦ksz¡
ni»
n
i
dalej
p
ost¦pujem
y
p
o
dobnie
jak
zadaniu
8.
10.
Niec
h
m
b
¦dzie
na
jmniejsz¡
wsp
óln¡
wielokrotno±ci¡
liczb
a
1
,
.
.
.
,
a
n
.
Wtedy
p
j
m
,
zatem
gdyb
y
S
b
yªo
liczb¡
caªk
o
wit¡,
to
m
p
S
te»
b
yªob
y
liczb¡
caªk
o
wit¡.
Zau
w
a»m
y
jednak,
»e
m
p
a
j
jest
liczb¡
caªk
o
wit¡
dla
j
6=
i
oraz
m
p
a
i
nie
jest
liczb¡
caªk
o
wit¡,
co
pro
w
adzi
do
sprzeczno±ci.
11.
Wiem
y
,
»e
n
=
ab
,
gdzie
1
<
a
b
<
n
.
Wtedy
a
p
n
,
wi¦c
je±li
p
jest
liczb¡
pierwsz¡
dziel¡c¡
a
,
to
p
p
n
.
12.
Gdyb
y
n
p
b
yªo
liczb¡
zªo»on¡,
to
na
mo
cy
zadania
11
i
zaªo»e«
ist-
niaªab
y
liczba
pierwsza
q
sp
eªnia
j¡ca
w
arunki
3
p
n
<
q
q
n
p
<
6
p
n
,
co
jest
niemo»liw
e.
11
13.
Dla
1
k
p
1
liczba
pierwsza
p
nie
wyst¦puje
w
rozkªadzie
liczb
k
!
i
(
p
k
)!
.
Z
drugiej
stron
y
p
!
jest
p
o
dzielne
przez
p
,
wi¦c
teza
wynik
a
ze
wzoru
na
p
k
.
14.
Do
w
ó
d
b
¦dzie
induk
cyjn
y
ze
wzgl¦du
na
n
.
Dla
n
=
1
teza
jest
o
czywista.
Zaªó»m
y
zatem,
»e
n
>
1
oraz,
»e
p
j
np
p
p
(
n
1)
.
Mam
y
wzór
np
p
=
P
p
k
=0
p
k
np
p
p
k
,
a
wi¦c
np
p
n
=
(
np
p
p
(
n
1))
+
P
p
1
k
=1
p
k
np
p
p
k
.
Korzysta
j¡c
z
zadania
13
oraz
zaªo»enia
induk
cyjnego
otrzym
ujem
y
tez¦.
15.
P
ok
a»em
y
na
jpierw,
»e
p
k
p
1
p
k
1
+
1
dla
k
2
.
Istotnie
p
1
p
k
1
+
1
jest
liczb¡
wi¦ksz¡
o
d
1
i
(
p
1
p
k
1
+
1
;
p
i
)
=
1
dla
i
=
1
;
:
:
:
;
k
1
.
Zatem
istnieje
liczba
pierwsza
p
dziel¡ca
p
1
p
k
1
+
1
ró»na
o
d
liczb
p
i
,
i
=
1
;
:
:
:
;
k
1
.
St¡d
wynik
a,
»e
p
k
p
1
p
k
1
+
1
.
P
ok
a»em
y
teraz,
»e
p
k
<
2
2
k
.
Dla
k
=
1
teza
jest
o
czywista.
Przypu±¢m
y
zatem,
»e
k
>
1
oraz
»e
p
j
<
2
2
j
dla
j
=
1
;
:
:
:
;
k
1
.
Korzysta
j¡c
z
nieró
w-
no±ci
p
k
p
1
p
k
1
+
1
otrzym
ujem
y
wtedy
,
»e
p
k
<
2
2
1
2
2
k
1
+
1
2
2
k
,
co
k
o«czy
do
w
ó
d.
16.
F
akt,
»e
(
x
)
log(log(
x
))
dla
x
2
(1
;
3)
jest
ªat
wy
do
zw
ery-
k
o
w
ania.
Przypu±¢m
y
zatem,
»e
x
3
.
Niec
h
p
b
¦dzie
na
jmniejsz¡
liczb¡
pierwsz¡
wi¦ksz¡
o
d
x
.
Wtedy
p
<
2
2
(
x
)+1
na
mo
cy
zadania
15.
St¡d
otrzy-
m
ujem
y
,
»e
x
<
2
2
(
x
)+1
.
P
oniew
a»
(
x
)
2
dla
x
3
,
wi¦c
2
2
(
x
)+1
<
e
e
(
x
)
zatem
x
<
e
e
(
x
)
dla
x
3
.
Dwukrotnie
logarytm
uj¡c
p
o
wy»sz¡
nieró
wno±¢
otrzym
ujem
y
tez¦
zadania.
17.
Niec
h
p
1
,
.
.
.
,
p
m
b
¦d¡
wszystkimi,
parami
ró»n
ymi,
liczbami
pierw-
szymi
nie
wi¦kszymi
ni»
x
.
Wtedy
k
a»da
liczba
naturalna
n
x
mo»e
b
y¢
zapisana
w
p
ostaci
n
=
p
"
1
1
p
"
m
m
r
2
,
gdzie
"
1
;
:
:
:
;
"
m
2
f
0
;
1
g
i
r
p
x
.
St¡d
x
2
m
p
x
,
co
k
o«czy
do
w
ó
d.
18.
Wystarczy
zlogarytmo
w
a¢
nieró
wno±¢
z
zadania
17.
19.
Z
faktu,
»e
Q
n<p
2
n
p
j
2
n
n
wynik
a,
»e
P
n<p
2
n
log
p
2
n
log
2
,
gdy»
2
n
n
2
2
n
.
Niec
h
(
n
)
:=
P
p
n
log
p
.
Mam
y
zatem,
»e
(2
n
)
(
n
)
2
n
log
2
,
sk
¡d
induk
cyjnie
do
w
o
dzim
y
,
»e
(2
r
)
2
r
+1
.
Dla
x
2
wybierz-
m
y
r
takie,
»e
2
r
x
<
2
r
+1
.
Wtedy
(
x
)
4
x
log
2
.
W
szczególno±ci
P
p
x<p
x
log
p
4
x
log
2
,
co
pro
w
adzi
do
wniosku,
»e
(
x
)
(
p
x
)
8
x
log
2
log
x
.
P
oniew
a»
(
p
x
)
p
x
i
p
x
x
log
2
log
x
dla
x
10
,
wi¦c
w
t
ym
przypadku
do
w
ó
d
nieró
wno±ci
jest
zak
o«czon
y
.
Dla
x
<
10
nieró
wno±¢
mo»na
spra
wdzi¢
b
ezp
o±rednio.
12
20.
Je±li
a
=
p
1
1
p
r
r
i
b
=
q
1
1
q
s
s
s¡
przedsta
wieniami
liczb
a
i
b
w
p
ostaci
ilo
czynó
w
p
ot¦g
parami
ró»n
yc
h
liczb
pierwszyc
h,
to
z
zaªo»enia
(
a;
b
)
=
1
wynik
a,
»e
p
i
6=
q
j
dla
wszystkic
h
par
indeksó
w
i
,
j
.
W
ten
sp
osób
otrzym
ujem
y
ró
wno±¢
n
k
=
ab
=
p
1
1
p
r
r
q
1
1
q
s
s
.
Z
t
wierdzenia
o
jed-
noznaczno±ci
przedsta
wienia
liczb
y
naturalnej
w
p
ostaci
ilo
czyn
u
p
ot¦g
liczb
pierwszyc
h
wynik
a,
»e
w
rozkªadzie
liczb
y
n
wyst¦puj¡
t
ylk
o
liczb
y
pierwsze
p
1
,
.
.
.
,
p
r
i
q
1
,
.
.
.
,
q
s
.
Zatem
n
=
p
1
1
p
r
r
q
1
1
q
s
s
dla
p
ewn
yc
h
natural-
n
yc
h
liczb
do
datnic
h
1
,
.
.
.
,
r
i
1
,
.
.
.
,
s
.
Z
ró
wno±ci
n
k
=
ab
i
t
wierdzenia
o
jednoznaczno±ci
przedsta
wienia
liczb
y
naturalnej
w
p
ostaci
ilo
czyn
u
p
ot¦g
liczb
pierwszyc
h
otrzym
ujem
y
,
»e
i
=
k
i
dla
i
=
1
;
:
:
:
;
r
i
j
=
k
j
dla
j
=
1
;
:
:
:
;
s
.
Zatem
c
=
p
1
1
p
r
r
i
d
=
q
1
1
q
s
s
sp
eªnia
j¡
w
arunki
zadania.
21.
P
oniew
a»
liczb
y
x
i
y
s¡
wzgl¦dnie
pierwsze,
wi¦c
nie
mog¡
b
y¢
obie
jedno
cze±nie
parzyste.
Gdyb
y
obie
b
yªy
nieparzyste,
to
z
2
2
(mo
d
4)
,
co
jest
niemo»liw
e.
Zatem
b
ez
strat
y
ogólno±ci
mo»em
y
zaªo»y¢,
»e
x
jest
liczb¡
parzyst¡,
za±
y
nieparzyst¡.
Wtedy
tak»e
z
jest
liczb¡
nieparzyst¡.
P
onadto
(
x
2
)
2
=
z
+
y
2
z
y
2
.
Wyk
orzystuj¡c
zaªo»enie
o
wzgl¦dnej
pierwszo±ci
liczb
x
,
y
i
z
wnioskujem
y
,
»e
(
z
+
y
2
;
z
y
2
)
=
1
,
i
k
orzysta
j¡c
z
zadania
20
otrzym
ujem
y
,
»e
z
+
y
2
=
a
2
i
z
y
2
=
b
2
dla
p
ewn
yc
h
wzgl¦dnie
pierwszyc
h
liczb
naturaln
yc
h
a
i
b
.
Ostatecznie
x
=
2
ab
,
y
=
a
2
b
2
i
z
=
a
2
+
b
2
,
przy
czym
jedna
z
liczb
a
i
b
jest
parzysta,
gdy»
y
nie
jest
liczb¡
parzyst¡.
22.
Przypu±¢m
y
,
»e
ró
wnanie
x
4
+
y
4
=
z
2
ma
nietrywialne
rozwi¡zanie
i
wybierzm
y
takie
rozwi¡zanie
o
na
jmniejszej
w
arto±ci
z
.
Wtedy
o
czywi±cie
liczb
y
x
2
,
y
2
i
z
s¡
parami
wzgl¦dnie
pierwsze,
wi¦c
z
zadania
21
wiem
y
,
»e
x
2
=
2
ab
,
y
2
=
a
2
b
2
i
z
=
a
2
+
b
2
dla
p
ewn
yc
h
parami
wzgl¦dnie
pierwszyc
h
liczb
a
i
b
,
z
któryc
h
jedna
jest
liczb¡
parzyst¡.
Gdyb
y
a
b
yªo
parzyste,
to
y
2
3
(mo
d
4)
,
co
jest
niemo»liw
e.
Zatem
b
jest
liczb¡
parzyst¡
i
b
=
2
c
dla
p
ewnej
liczb
y
naturalnej
c
.
P
oniew
a»
x
2
=
4
ac
i
(
a;
c
)
=
1
,
wi¦c
a
=
m
2
i
c
=
n
2
dla
p
ewn
yc
h
wzgl¦dnie
pierwszyc
h
liczb
naturaln
yc
h
m
i
n
na
mo
cy
zadania
20.
Wtedy
(2
n
2
)
2
+
y
2
=
(
m
2
)
2
,
przy
czym
(2
n
2
;
y
)
=
(
y
;
m
2
)
=
(2
n
2
;
m
2
)
=
1
.
Z
zadania
21
wynik
a
zatem,
»e
istniej¡
parami
wzgl¦dnie
pierwsze
liczb
y
naturalne
i
,
z
któryc
h
jedna
jest
p
o
dzielna
przez
2
,
takie,
»e
n
2
=
,
y
=
2
2
i
m
2
=
2
+
2
.
Z
ró
wno±ci
n
2
=
i
zadania
20
wnioskujem
y
,
»e
istniej¡
liczb
y
naturalne
p
i
q
takie,
»e
=
p
2
i
=
q
2
,
co
da
je
nam
ró
wno±ci
p
4
+
q
4
=
m
2
,
co
przeczy
minimalno±ci
z
.
23.
Wybierzm
y
nietrywialne
rozwi¡zanie
ró
wnanie
x
4
=
z
2
+
y
4
o
mi-
nimalnej
w
arto±ci
x
.
Z
zadania
21
wynik
a,
»e
x
m
usi
b
y¢
liczb¡
nieparzyst¡.
Przypu±¢m
y
na
jpierw,
»e
tak»e
y
jest
liczb¡
nieparzyst¡.
Wtedy
z
=
2
ab
,
y
2
=
a
2
b
2
i
x
2
=
a
2
+
b
2
dla
p
ewn
yc
h
wzgl¦dnie
pierwszyc
h
liczb
natural-
n
yc
h
a
i
b
.
Wtedy
a
4
=
(
xy
)
2
+
b
4
i
a
<
x
,
co
przeczy
zaªo»eniu
o
minimalno±ci
13
x
.
Zaªó»m
y
teraz,
»e
y
jest
liczb¡
parzyst¡.
Wtedy
y
2
=
2
ab
,
z
=
a
2
b
2
i
x
2
=
a
2
+
b
2
,
dla
wzgl¦dnie
pierwszyc
h
liczb
a
i
b
,
z
któryc
h
jedna
jest
pa-
rzysta.
Je±li
a
jest
liczb¡
parzyst¡,
to
na
mo
cy
zadania
20
2
a
=
s
2
i
b
=
t
2
dla
p
ewn
yc
h
liczb
naturaln
yc
h
s
i
t
.
Wtedy
s
te»
jest
liczb¡
parzyst¡,
wi¦c
a
=
2
u
2
.
St¡d
x
2
=
(2
u
2
)
2
+
(
t
2
)
2
,
wi¦c
2
u
2
=
2
v
w
,
t
2
=
v
2
w
2
,
x
=
v
2
+
w
2
dla
wzgl¦dnie
pierwszyc
h
liczb
naturaln
yc
h
v
i
w
.
P
onadto
v
=
c
2
i
w
=
d
2
i
c
4
=
t
2
+
d
4
,
przy
czym
c
<
x
,
co
pro
w
adzi
do
sprzeczno±ci.
P
o
dobnie
do
c
ho
dzim
y
do
sprzeczno±ci
przy
zaªo»eniu,
»e
b
jest
liczb¡
parzyst¡.
24.
Je±li
f
(0)
=
0
,
to
teza
jest
o
czywista.
Przypu±¢m
y
zatem,
»e
a
=
f
(0)
6=
0
i
niec
h
p
1
,
.
.
.
,
p
k
b
¦d¡
wszystkimi
liczbami
pierwszymi
p
,
dla
któ-
ryc
h
istniej¡
rozwi¡zania
k
ongruencji
f
(
x
)
0
(mo
d
p
)
.
Niec
h
m
:=
p
1
p
k
i
g
(
x
)
:=
f
(
amx
)
a
.
Je±li
istnieje
rozwi¡zanie
k
ongruencji
g
(
x
)
0
(mo
d
p
)
dla
p
ewnej
liczb
y
pierwszej
p
,
to
p
=
p
i
dla
p
ewnego
i
.
Z
drugiej
stron
y
g
(
x
)
1
(mo
d
p
i
)
dla
wszystkic
h
x
2
Z
i
i
=
1
;
:
:
:
;
k
,
sk
¡d
wynik
a,
»e
wielomian
g
przyjm
uje
jedynie
w
arto±ci
1
i
1
,
co
jest
niemo»liw
e.
25.
Niec
h
f
(
x
)
:=
1
+
x
+
+
x
q
1
.
Przypu±¢m
y
,
»e
p
jest
tak
¡
liczb¡
pierwsz¡,
»e
istnieje
liczba
caªk
o
wita
x
tak
a,
»e
p
j
f
(
x
)
.
Je±li
x
1
(mo
d
p
)
,
to
p
=
q
,
za±
w
przeciwn
ym
wypadku
otrzym
ujem
y
,
»e
x
q
1
(mo
d
p
)
,
wi¦c
q
j
p
1
,
gdy»
x
p
1
1
(mo
d
p
)
i
q
jest
liczb¡
pierwsz¡.
T
o
k
o«czy
rozwi¡zanie
na
mo
cy
zadania
24.
26.
Udo
w
o
dnienie
wzoru
F
m
=
F
1
F
m
1
+
2
jest
prost
ym
¢wiczeniem
na
induk
cj¦
matemat
yczn¡.
Niec
h
p
b
¦dzie
dzielnikiem
pierwszym
liczb
y
2
2
n
+
1
.
Wtedy
2
2
n
+1
1
(mo
d
p
)
.
Niec
h
l
b
¦dzie
na
jmniejsz¡
liczb¡
caªk
o
wit¡
do
datni¡
tak
¡,
»e
2
l
1
(mo
d
p
)
.
Wtedy
l
j
2
n
+1
,
wi¦c
l
=
2
m
dla
p
ewnej
liczb
y
caªk
o
witej
do
datniej
m
n
+
1
.
Gdyb
y
m
n
,
to
2
2
n
1
(mo
d
p
)
,
co
jest
sprzeczne
z
zaªo»eniem,
»e
p
j
2
2
n
+
1
.
St¡d
l
=
2
n
+1
.
P
oniew
a»
z
t
wierdzenia
Eulera
2
p
1
1
(mo
d
p
)
,
wynik
a
st¡d,
»e
2
n
+1
j
p
1
,
co
k
o«czy
do
w
ó
d.
2.2
Kongruencje
27.
Zau
w
a»m
y
,
»e
10
2
9
(mo
d
13)
.
St¡d
10
3
1
(mo
d
13)
,
a
wi¦c
10
6
1
(mo
d
13)
.
28.
P
o
dobnie
jak
zadanie
27.
29.
P
o
dobnie
jak
zadanie
27.
14
30.
P
oniew
a»
3
-
n
,
wi¦c
n
2
1
(mo
d
3)
i
n
4
1
(mo
d
3)
,
sk
¡d
n
4
+
n
2
+
1
0
(mo
d
3)
.
31.
P
oniew
a»
2
2
1
(mo
d
3)
,
wi¦c
2
2
n
1
(mo
d
3)
.
32.
Wiadomo,
»e
P
n
1
j
=1
j
=
n
n
1
2
,
zatem
n
j
P
n
1
j
=1
j
wtedy
i
t
ylk
o
wtedy
,
gdy
2
j
n
1
.
33.
Wiadomo,
»e
P
n
1
j
=1
j
3
=
n
n
(
n
1)
2
4
,
zatem
n
j
P
n
1
j
=1
j
3
wtedy
i
t
ylk
o
wtedy
,
gdy
4
j
n
(
n
1)
2
.
T
o
jest
mo»liw
e
t
ylk
o,
gdy
4
j
n
lub
2
j
n
1
.
34.
(a)
.
Wyk
orzystuj¡c
algorytm
Euklidesa
wiem
y
,
»e
(3
;
7)
=
1
=
7
2
3
.
St¡d
mno»¡c
stronami
wyj±cio
w
¡
k
ongruencj¦
przez
2
otrzym
ujem
y
,
»e
6
x
8
(mo
d
7)
.
P
oniew
a»
6
1
(mo
d
7)
oraz
8
6
(mo
d
7)
,
wi¦c
ostatecznie
mam
y
x
6
(mo
d
7)
.
34.
(b)
.
x
19
(mo
d
256)
.
34.
(c)
.
x
8
(mo
d
21)
.
34.
(d)
.
P
oniew
a»
(10
;
35)
=
5
j
15
,
wi¦c
k
ongruencja
p
osiada
rozwi¡za-
nie.
Mam
y
5
rozwi¡za«
mo
dulo
35
.
Jedno
z
nic
h
otrzym
ujem
y
rozwi¡zuj¡c
k
ongruencj¦
2
x
3
(mo
d
35)
,
sk
¡d
dosta
jem
y
,
»e
x
19
(mo
d
35)
.
P
ozo-
staªe
rozwi¡zania
otrzym
ujem
y
do
da
j¡c
wielokrotno±ci
7
,
a
wi¦c
ostatecznie
mam
y
x
5
;
12
;
19
;
26
;
33
(mo
d
35)
.
34.
(e)
.
P
oniew
a»
(18
;
3)
=
3
-
7
,
wi¦c
k
ongruencja
nie
p
osiada
rozwi¡-
zania.
35.
(a)
.
Mam
y
m
1
:=
4
,
m
2
:=
7
,
m
3
:=
9
,
m
:=
4
7
9
=
252
,
n
1
:=
7
9
=
63
,
n
2
:=
4
9
=
36
i
n
3
:=
4
7
=
28
.
Wyk
orzystuj¡c
algorytm
Euklidesa
szuk
am
y
liczb
y
e
1
sp
eªnia
j¡cej
w
arunki
e
1
1
(mo
d
4)
i
e
1
0
(mo
d
63)
.
P
oniew
a»
(4
;
63)
=
1
=
16
4
63
,
wiec
przyjm
ujem
y
e
1
:=
63
.
P
o
dobnie
wyliczam
y
e
2
:=
36
i
e
3
:=
28
.
Wtedy
mam
y
rozwi¡zanie
p
ostaci
x
3
e
1
+
2
e
2
+
e
3
(mo
d
252)
,
sk
¡d
wynik
a,
»e
x
163
(mo
d
252)
.
35.
(b)
.
x
713
(mo
d
1320)
.
35.
(c)
.
Rozw
a»an
y
ukªad
k
ongruencji
mo»na
spro
w
adzi¢
do
ukªadu
x
2
(mo
d
3)
,
x
3
(mo
d
4)
i
x
5
(mo
d
7)
,
którego
rozwi¡zaniem
s¡
x
47
(mo
d
84)
.
36.
Rozwi¡zanie
tego
zadania
p
olega
na
znalezieniu
na
jmniejszego
roz-
wi¡zania
ukªadu
k
ongruencji
x
1
(mo
d
2)
,
x
2
(mo
d
3)
,
x
3
(mo
d
4)
,
x
4
(mo
d
5)
,
x
5
(mo
d
6)
i
x
0
(mo
d
7)
,
sk
¡d
wynik
a,
»e
n
=
119
.
15
2.3
F
unk
cja
Eulera
37.
'
(1000)
=
'
(2
3
5
3
)
=
(2
1)
2
2
(5
1)
5
2
=
400
,
'
(125)
=
100
,
'
(180)
=
48
,
'
(360)
=
96
i
'
(1001)
=
720
.
38.
(a)
.
x
2
;
.
38.
(b)
.
x
=
15
;
16
;
20
;
24
;
30
.
38.
(c)
.
x
=
13
;
21
;
26
;
28
;
36
;
42
.
39.
Wzór
ten
jest
b
ezp
o±redni¡
k
onsekw
encj¡
wzoru
na
funk
cj¦
Eulera.
40.
Je±li
istnieje
liczba
pierwsza
p
>
2
,
która
dzieli
n
,
to
'
(
n
)
jest
p
o-
dzielne
przez
p
1
,
które
jest
liczb¡
parzyst¡.
W
przeciwn
ym
wypadku
n
=
2
m
i
'
(
n
)
=
2
m
1
,
przy
czym
m
>
1
.
41.
Mam
y
m
=
p
1
1
p
k
k
q
1
1
q
s
s
oraz
n
=
p
1
1
p
k
k
q
s
+1
s
+1
q
s
+
r
s
+
r
,
gdzie
k
;
r
;
s
0
,
p
1
,
.
.
.
,
p
k
,
q
1
,
.
.
.
,
q
r
+
s
s¡
parami
ró»n
ymi
liczbami
pierw-
szymi
oraz
1
,
.
.
.
,
k
,
1
,
.
.
.
,
k
,
1
,
.
.
.
,
r
+
s
s¡
do
datnimi
liczbami
natu-
raln
ymi.
P
oniew
a»
d
=
p
min
(
1
;
1
)
1
p
min
(
k
;
k
)
k
,
wi¦c
teza
jest
k
onsekw
encj¡
wzoru
na
funk
cj¦
Eulera.
42.
Niec
h
d
=
p
1
1
p
k
k
b
¦dzie
przedsta
wieniem
liczb
y
d
w
p
ostaci
ilo
czyn
u
p
ot¦g
parami
ró»n
yc
h
liczb
pierwszyc
h.
Wtedy
n
=
p
1
1
p
k
k
m
,
gdzie
i
i
oraz
p
i
-
m
dla
i
=
1
;
:
:
:
;
k
.
Zatem
'
(
n
)
=
'
(
p
1
1
p
k
k
)
'
(
m
)
=
'
(
d
)
p
1
1
1
p
k
k
k
'
(
m
)
.
43.
Na
mo
cy
t
wierdzenia
Eulera
a
6
1
(mo
d
7)
.
P
o
dnosz¡c
t¦
nieró
w-
no±¢
stronami
do
kw
adratu
otrzym
ujem
y
tez¦.
44.
Kongruencja
a
12
1
(mo
d
65)
zac
ho
dzi
wtedy
i
t
ylk
o
wtedy
,
gdy
zac
ho
dz¡
k
ongruencje
a
12
1
(mo
d
5)
i
a
12
1
(mo
d
13)
.
Korzysta
j¡c
z
w
arunku
(
a;
65)
=
1
wnioskujem
y
,
»e
(
a;
5)
=
1
i
(
a;
13)
=
1
.
Z
t
wierdzenia
Eulera
wynik
a,
»e
a
12
1
(mo
d
13)
i
a
4
1
(mo
d
5)
.
P
o
dnosz¡c
drug¡
z
k
ongruencji
stronami
do
trzeciej
p
ot¦gi
otrzym
ujem
y
,
»e
a
12
1
(mo
d
5)
,
co
k
o«czy
rozwi¡zanie.
45.
P
oniew
a»
n
jest
na
jmniejsz¡
p
ot¦g¡
naturaln¡
k
,
dla
której
a
k
1
(mo
d
(
a
n
1))
oraz
a
'
(
a
n
1)
1
(mo
d
(
a
n
1))
na
mo
cy
t
wierdzenia
Eulera,
wi¦c
n
mo
d
'
(
a
n
1)
.
16
46.
Przypu±¢m
y
,
»e
n
jest
na
jmniejsz¡
liczb¡
naturaln¡
n
>
1
tak
¡,
»e
n
j
2
n
1
.
Oczywi±cie
n
j
2
'
(
n
)
1
.
Zatem
je±li
d
=
(
n;
'
(
n
))
,
to
wyk
orzystuj¡c
zadanie
3
otrzym
ujem
y
,
»e
n
j
2
d
1
.
P
oniew
a»
n
>
1
,
wi¦c
oznacza
to
w
szczególno±ci,
»e
d
>
1
.
Ale,
to
przeczy
minimalno±ci
liczb
y
n
,
gdy»
d
j
2
d
1
.
47.
P
oszczególne
czynniki
wyst¦puj¡ce
p
o
pra
w
ej
stronie
mo»na
in
ter-
preto
w
a¢
jak
o
pra
wdop
o
dobie«st
w
o,
»e
loso
w
o
wybrana
liczba
sp
o±ró
d
liczb
1
,
.
.
.
,
n
nie
jest
p
o
dzielna
przez
p
.
48.
Z
t
wierdzenia
Eulera
3
40
1
(mo
d
100)
,
wi¦c
dwie
ostatnie
cyfry
liczb
y
3
1000
to
01
.
49.
Z
t
wierdzenia
Eulera
wynik
a,
»e
2
1000
1
(mo
d
25)
.
Oczywi±cie
ma-
m
y
,
te»
2
1000
0
(mo
d
4)
.
Rozwi¡zuj¡c
ukªad
k
ongruencji
x
1
(mo
d
25)
i
x
0
(mo
d
4)
otrzym
ujem
y
,
»e
2
1000
76
(mo
d
100)
.
2.4
Elemen
t
y
teorii
pier±cieni
51.
(a)
.
Nie,
gdy»
nie
jest
to
zbiór
zamkni¦t
y
ze
wzgl¦du
na
o
dejmo
w
a-
nie.
51.
(b)
.
Nie,
gdy»
1
nie
nale»y
do
tego
zbioru.
51.
(c)
.
T
ak.
51.
(d)
.
T
ak.
51.
(e)
.
Nie,
gdy»
nie
jest
to
zbiór
zamkni¦t
y
ze
wzgl¦du
na
mno»enie.
52.
(a)
.
T
ak.
52.
(b)
.
T
ak.
52.
(c)
.
Nie,
gdy»
funk
cja
to»samo±cio
w
o
ró
wna
1
nie
nale»y
do
tego
zbioru.
52.
(d)
.
T
ak.
52.
(e)
.
Nie,
gdy»
nie
jest
to
zbiór
zamkni¦t
y
ze
wzgl¦du
na
do
da
w
anie
funk
cji.
17
53.
Niec
h
R
b
¦dzie
sk
o«czon
ym
pier±cieniem
b
ez
dzielnik
ó
w
zera.
T
rzeba
p
ok
aza¢,
»e
dla
k
a»dego
elemen
tu
a
2
R
,
a
6=
0
,
istnieje
elemen
t
b
2
R
o
wªasno±ci
ab
=
1
.
Ustalm
y
a
2
R
,
a
6=
0
.
Rozw
a»m
y
funk
cj¦
f
:
R
!
R
dan¡
wzorem
f
(
x
)
=
ax
dla
x
2
R
.
Wtedy
funk
cja
f
jest
ró»no
w
arto±cio
w
a.
Istotnie,
je±li
f
(
x
1
)
=
f
(
x
2
)
dla
x
1
;
x
2
2
R
,
to
a
(
x
1
x
2
)
=
ax
1
ax
2
=
f
(
x
1
)
f
(
x
2
)
=
0
.
P
oniew
a»
w
pier±cieniu
R
nie
ma
dzielnik
ó
w
zera
i
a
6=
0
,
wi¦c
x
1
x
2
=
0
,
co
oznacza,
»e
x
1
=
x
2
i
k
o«czy
do
w
ó
d
ró»no
w
arto±cio
w
o±ci
funk
cji
f
.
Wyk
orzystuj¡c
zaªo»enie,
»e
pier±cie«
R
jest
sk
o«czon
y
,
oraz
fakt,
»e
k
a»da
funk
cja
ró»no
w
arto±cio
w
a
na
zbiorze
sk
o«czon
ym
jest
funk
cj¡
ÿna",
wnioskujem
y
,
»e
funk
cja
f
jest
ÿna".
W
szczególno±ci
istnieje
elemen
t
b
2
R
taki,
»e
f
(
b
)
=
1
,
tzn.
ab
=
1
.
54.
Wiem
y
,
»e
f
=
q
(
X
1)(
X
2)
+
h
dla
p
ewn
yc
h
wielomianó
w
q
;
h
2
R
[
X
]
,
przy
czym
h
=
aX
+
b
dla
a;
b
2
R
.
Wyk
orzystuj¡c
zaªo»enia
wiem
y
,
»e
h
(1)
=
f
(1)
=
2
i
h
(2)
=
f
(2)
=
1
,
sk
¡d
otrzym
ujem
y
ukªad
ró
wna«
a
+
b
=
2
2
a
+
b
=
1
:
Rozwi¡zuj¡c
p
o
wy»szy
ukªad
ró
wna«
dosta
jem
y
a
=
1
i
b
=
3
,
zatem
reszta
z
dzielenia
wielomian
u
f
przez
(
X
1)(
X
2)
jest
ró
wna
X
+
3
.
55.
(a)
.
d
=
1
,
u
=
1
,
v
=
X
2
.
55.
(b)
.
d
=
X
1
,
u
=
1
4
X
+
1
4
,
v
=
1
4
X
2
X
+
1
.
55.
(c)
.
d
=
X
2
2
,
u
=
X
1
,
v
=
X
+
2
.
56.
Znalezienie
o
dwrotno±ci
do
w
arst
wy
wielomian
u
1
+
X
2
w
R
[
X
]
=
(
X
3
)
jest
ró
wno
w
a»ne
znalezieniu
wielomian
u
f
2
R
[
X
]
sp
eªnia
j¡cego
w
arunek
f
(1
+
X
2
)
=
1
(mo
d
X
3
)
.
Korzysta
j¡c
z
algorytm
u
Euklidesa
otrzym
ujem
y
,
»e
(1
+
X
2
;
X
3
)
=
1
oraz
1
=
(1
X
2
)(1
+
X
2
)
+
X
X
3
;
a
wi¦c
mo»em
y
przyj¡¢
f
=
1
X
2
.
Zatem
o
dwrotno±ci¡
do
w
arst
wy
wielo-
mian
u
1
+
X
2
w
R
[
X
]
=
(
X
3
)
jest
w
arst
w
a
wielomian
u
1
X
2
.
2.5
Ciaªa
sk
o«czone
57.
F
2
:
X
,
X
+
1
,
X
2
+
X
+
1
,
X
3
+
X
+
1
,
X
3
+
X
2
+
1
,
X
4
+
X
+
1
,
X
4
+
X
3
+
1
,
X
4
+
x
3
+
X
2
+
X
+
1
.
18
F
3
:
X
,
X
+
1
,
X
+
2
,
X
2
+
1
,
X
2
+
X
+
2
,
X
2
+
2
X
+
2
,
X
3
+
2
X
+
1
,
X
3
+
2
X
+
2
,
X
3
+
X
2
+
2
,
X
3
+
X
2
+
X
+
2
,
X
3
+
X
2
+
2
X
+
1
,
X
3
+
2
X
2
+
1
,
X
3
+
2
X
2
+
X
+
1
,
X
3
+
2
X
2
+
2
X
+
2
,
X
4
+
X
+
2
,
X
4
+
2
X
+
2
,
X
4
+
X
2
+
2
,
X
4
+
X
2
+
2
X
+
1
,
X
4
+
2
X
2
+
2
,
X
4
+
X
3
+
2
,
X
4
+
X
3
+
2
X
+
1
,
X
4
+
X
3
+
X
2
+
1
,
X
4
+
X
3
+
X
2
+
X
+
1
,
X
4
+
X
3
+
X
2
+
2
X
+
2
,
X
4
+
X
3
+
2
X
2
+
2
X
+
2
,
X
4
+
2
X
3
+
2
,
X
4
+
2
X
3
+
X
+
1
,
X
4
+
2
X
3
+
X
2
+
1
,
X
4
+
2
X
3
+
X
2
+
X
+
2
,
X
4
+
2
X
3
+
X
2
+
2
X
+
1
,
X
4
+
2
X
3
+
2
X
2
+
X
+
2
.
58.
(a)
.
X
16
X
=
X
(
X
+
1)(
X
2
+
X
+
1)(
X
4
+
X
+
1)(
X
4
+
X
3
+
1)(
X
4
+
X
3
+
X
2
+
X
+
1)
.
58.
(b)
.
X
9
X
=
X
(
X
+
1)(
X
+
2)(
X
2
+
1)(
X
2
+
X
+
2)(
X
2
+
2
X
+
2)
.
58.
(c)
.
X
27
X
=
X
(
X
+
1)(
X
+
2)(
X
3
+
2
X
+
1)(
X
3
+
2
X
+
2)(
X
3
+
X
2
+
2)(
X
3
+
X
2
+
X
+
2)(
X
3
+
X
2
+
2
X
+
1)(
X
3
+
2
X
2
+
1)(
X
3
+
2
X
2
+
X
+
1)(
X
3
+
2
X
2
+
2
X
+
2)
.
59.
Je±li
k
n;p
oznacza
liczb
¦
unormo
w
an
yc
h
wielomianó
w
nierozkªadal-
n
yc
h
stopnia
n
nad
ciaªem
F
p
,
to
k
orzysta
j¡c
ze
wzoru
in
w
ersyjnego
M
obiusa
mam
y
k
n;p
=
1
n
P
d
j
p
(
d
)
p
n
d
,
gdzie
jest
funk
cj¡
M
obiusa.
St¡d
k
1
;
2
=
2
,
k
2
;
2
=
1
,
k
3
;
2
=
2
,
k
4
;
2
=
3
,
k
5
;
2
=
6
,
k
6
;
2
=
9
,
k
7
;
2
=
18
,
k
8
;
2
=
30
,
k
1
;
3
=
3
,
k
2
;
3
=
3
,
k
3
;
3
=
8
,
k
4
;
3
=
18
,
k
5
;
3
=
48
,
k
6
;
3
=
116
,
k
7
;
3
=
312
,
k
8
;
3
=
810
.
60.
(a)
.
(
f
;
f
0
)
=
X
4
+
X
2
+
1
=
(
X
2
+
X
+
1)
2
,
wi¦c
f
=
(
X
2
+
X
+
1)
2
(
X
3
+
X
+
1)
.
60.
(b)
.
(
f
;
f
0
)
=
X
6
+
1
=
(
X
2
+
1)
3
,
wi¦c
f
=
(
X
2
+
1)
2
(
X
2
+
X
+
2)
.
60.
(c)
.
(
f
;
f
0
)
=
X
4
+
4
X
2
+
4
=
(
X
2
+
2)
2
,
wi¦c
f
=
(
X
2
+
2)
3
(
X
3
+
X
+
1)
.
61.
(a)
.
Nie,
gdy»
(
f
;
f
0
)
6=
1
.
61.
(b)
.
T
ak,
gdy»
(
f
;
f
0
)
=
1
.
61.
(c)
.
T
ak,
gdy»
(
f
;
f
0
)
=
1
.
62.
(a)
.
P
oniew
a»
wielomian
x
2
+
1
nie
p
osiada
pierwiastk
ó
w
w
ciele
F
3
,
wi¦c
F
9
:=
F
3
[
X
]
=
(
X
2
+
1)
.
Oznaczm
y
przez
w
arst
w
¦
wielomian
u
X
w
ciele
F
9
.
Wtedy
pierwiastk
ami
wielomian
u
f
s¡
i
2
.
62.
(b)
.
Pierwiastk
ami
wielomian
u
f
s¡
i
2
+
2
,
gdzie
jest
w
arst
w
¡
wielomian
u
X
w
ciele
F
9
:=
F
3
[
X
]
=
(
X
2
+
X
+
2)
.
19
62.
(c)
.
Pierwiastk
ami
wielomian
u
f
s¡
i
3
+
4
,
gdzie
jest
w
arst
w
¡
wielomian
u
X
w
ciele
F
2
5
:=
F
5
[
X
]
=
(
X
2
+
2
X
+
3)
.
63.
P
oniew
a»
62
F
p
,
wi¦c
p
6=
.
Z
drugiej
stron
y
a
p
=
a
i
b
p
=
b
.
St¡d
(
p
)
2
+
p
a
+
b
=
(
2
)
p
+
(
a
)
p
+
b
p
=
(
2
+
a
+
b
)
p
=
0
,
a
wi¦c
p
jest
drugim
pierwiastkiem
wielomian
u
X
2
+
aX
+
b
,
zatem
+
p
=
a
i
p
+1
=
b
.
Z
p
o
wy»szyc
h
ró
wno±ci
wynik
a,
»e
(
c
+
d
)
p
(
c
+
d
)
=
(
c
p
+
d
)(
c
+
d
)
=
c
2
p
+1
+
cd
(
p
+
)
+
d
2
=
c
2
b
cda
+
d
2
,
co
b
yªo
do
udo
w
o
dnienia.
(2
+
3
i
)
101
=
((2
+
3
i
)
20
)
5
(2
+
3
i
)
=
9
+
4
i
.
64.
Je±li
f
=
g
p
,
to
f
0
=
pg
p
1
g
0
=
0
.
Z
drugiej
stron
y
,
gdy
f
=
P
i
a
i
X
i
oraz
f
0
=
0
,
to
a
i
6=
0
t
ylk
o,
gdy
p
j
i
.
P
oniew
a»
a
p
=
a
dla
a
2
F
p
,
wi¦c
otrzym
ujem
y
w
ten
sp
osób,
»e
f
=
P
j
a
p
pj
X
pj
=
(
P
j
a
pj
X
j
)
p
,
co
k
o«czy
do
w
ó
d.
2.6
Elemen
t
y
teorii
grup
65.
(a)
.
Nie,
gdy»
nie
jest
to
zbiór
zamkni¦t
y
ze
wzgl¦du
na
o
dejmo
w
a-
nie.
65.
(b)
.
T
ak.
65.
(c)
.
T
ak.
65.
(d)
.
T
ak.
65.
(e)
.
Nie,
gdy»
nie
jest
to
zbiór
zamkni¦t
y
ze
wzgl¦du
na
do
da
w
anie.
66.
(a)
.
Nie,
gdy»
nie
istnieje
elemen
t
o
dwrotn
y
do
0
.
66.
(b)
.
T
ak.
66.
(c)
.
T
ak.
66.
(d)
.
Nie,
gdy»
nie
istniej¡
liczb
y
caªk
o
wite
o
dwrotne
do
liczb
caªk
o-
wit
yc
h
ró»n
yc
h
o
d
1
i
1
.
66.
(e)
.
T
ak.
67.
F
7
:
r
(1)
=
1
,
r
(2)
=
r
(4)
=
r
(6)
=
2
,
r
(3)
=
r
(5)
=
6
.
F
8
:=
F
2
[
X
]
=
(
X
3
+
X
+
1)
,
:=
w
arst
w
a
X
:
r
(1)
=
1
,
r
(
)
=
r
(
+
1)
=
r
(
2
)
=
r
(
2
+
1)
=
r
(
2
+
)
=
r
(
2
+
+
1)
=
7
.
F
9
:=
F
3
[
X
]
=
(
X
2
+
1)
,
:=
w
arst
w
a
X
:
r
(1)
=
1
,
r
(2)
=
2
,
r
(
)
=
r
(2
)
=
4
,
r
(
+
1)
=
r
(
+
2)
=
r
(2
+
1)
=
r
(2
+
2)
=
8
.
20
68.
(a)
.
Ilo±¢
generatoró
w
grup
y
F
q
jest
ró
wna
'
(
q
1)
,
zatem
ilo±¢
generatoró
w
grup
y
F
9
jest
ró
wna
4
.
nie
jest
generatorem
grup
y
F
9
,
b
o
4
=
1
,
za±
+
1
,
2
+
1
s¡
generatorami
grup
y
F
9
.
2
1
=
2
.
68.
(b)
.
'
(24)
=
8
,
,
+
1
{
nie,
gdy»
8
=
1
i
(
+
1)
12
=
1
,
2
+
1
{
tak.
(2
+
3
)
1
=
1
2
3
(2
+
3
)(2
3
)
=
2
3
.
68.
(c)
.
'
(48)
=
16
,
,
2
+
1
{
nie,
gdy»
6
=
1
i
(2
+
1)
24
=
1
,
+
1
{
tak.
(2
+
3
)
1
=
2
3
.
69.
'
(15)
=
10
,
(
+
1)
3
=
3
+
2
+
+
1
i
(
+
1)
5
=
2
+
,
=
(
+
1)
4
,
1
=
(
+
1)
15
4
=
(
+
1)
4
2
(
+
1)
3
=
3
+
1
.
70.
p
=
2
i
2
k
1
liczba
pierwsza.
71.
p
=
2
i
2
k
1
liczba
pierwsza
lub
p
=
3
i
3
p
1
2
liczba
pierwsza.
72.
(
Z
=
8
Z
)
:
r
(1)
=
1
,
r
(3)
=
r
(5)
=
r
(7)
=
2
.
(
Z
=
15
Z
)
:
r
(1)
=
1
,
r
(4)
=
r
(11)
=
r
(14)
=
2
,
r
(2)
=
r
(7)
=
r
(8)
=
r
(13)
=
4
.
(
Z
=
16
Z
)
:
r
(1)
=
1
,
r
(7)
=
r
(9)
=
r
(15)
=
2
,
r
(3)
=
r
(5)
=
r
(11)
=
r
(13)
=
4
.
73.
Bez
strat
y
ogólno±ci
mo»em
y
zaªo»y¢,
»e
k
2
.
Przypu±¢m
y
,
»e
a
p
1
1
(mo
d
p
2
)
.
Wtedy
((
p
+
1)
a
)
p
1
6
1
(mo
d
p
2
)
.
Zatem
istnieje
elemen
t
b
2
(
Z
=p
k
Z
)
o
wªasno±ci
b
p
1
6
1
(mo
d
p
2
)
.
P
onadto
b
p
1
6
1
(mo
d
p
)
,
wi¦c
istnieje
liczba
caªk
o
wita
c
tak
a,
»e
b
=
1
+
cp
,
przy
czym
(
c;
p
)
=
1
.
Gdy
b
i
1
(mo
d
p
k
)
,
to
p
1
j
i
,
a
wi¦c
i
=
(
p
1)
j
dla
p
ewnego
j
.
Wtedy
(1
+
cp
)
j
1
mo
d
p
k
.
Niec
h
p
l
b
¦dzie
na
jwi¦ksz¡
p
ot¦g¡
liczb
y
p
dziel¡c¡
j
.
Gdyb
y
l
+
2
k
,
to
(1
+
cp
)
j
1
(mo
d
p
l
+2
)
.
Z
drugiej
stron
y
p
l
+2
j
j
m
p
m
dla
m
2
,
sk
¡d
(1
+
cp
)
j
1
(mo
d
p
l
+2
)
.
P
oniew
a»
(
c;
p
)
=
1
,
wi¦c
pro
w
adzi
to
do
wniosku,
»e
p
l
+1
j
j
,
a
wi¦c
do
sprzeczno±ci.
Zatem
l
+
2
>
k
,
czyli
p
k
1
j
j
.
Ostatecznie
(
p
1)
p
k
1
j
i
,
co
k
o«czy
do
w
ó
d.
74.
h
6
i
=
h
(6
;
15)
i
=
h
3
i
=
f
0
;
3
;
6
;
9
;
12
g
.
h
10
i
=
h
(10
;
15)
i
=
h
5
i
=
f
0
;
5
;
10
g
.
h
6
;
10
i
=
h
(6
;
10
;
15)
i
=
h
1
i
=
Z
=
15
Z
.
21
2.7
Elemen
t
y
teorii
k
o
do
w
ania
75.
(b)
.
Niec
h
C
F
n
2
b
¦dzie
k
o
dem
o
o
dlegªo±ci
minimalnej
nie
mniej-
szej
ni»
d
.
Deniujem
y
k
o
d
C
0
F
n
+
d
2
nast¦puj¡cym
wzorem
C
0
=
C
f
(0
;
:
:
:
;
0)
;
(1
;
:
:
:
;
1)
g
.
Wtedy
j
C
0
j
=
2
j
C
j
oraz
d
min
(
C
0
)
=
j
(
d
min
(
C
)
;
d
)
=
d
.
75.
(c)
.
Niec
h
C
F
n
2
b
¦dzie
k
o
dem
o
o
dlegªo±ci
minimalnej
nie
mniej-
szej
ni»
d
.
Deniujem
y
k
o
d
C
0
F
2
n
2
wzorem
C
0
:=
C
C
.
Wtedy
j
C
j
=
j
C
0
j
2
oraz
d
min
(
C
)
=
d
min
(
C
0
)
d
.
75.
(d)
.
Niec
h
C
F
n
2
b
¦dzie
k
o
dem
o
o
dlegªo±ci
minimalnej
nie
mniej-
szej
ni»
d
.
Deniujem
y
k
o
dy
C
1
;
C
2
F
n
1
2
wzorami
C
1
:=
f
w
2
F
n
1
2
j
(
w
;
0)
2
C
oraz
C
2
:=
f
w
2
F
n
1
2
j
(
w
;
1)
2
C
g
.
Wtedy
d
min
(
C
1
)
;
d
min
(
C
2
)
d
oraz
min
(
j
C
1
j
;
j
C
2
j
)
j
C
j
2
.
75.
(e)
.
Niec
h
C
F
n
2
b
¦dzie
k
o
dem
o
o
dlegªo±ci
minimalnej
nie
mniej-
szej
ni»
d
.
Dla
k
a»dego
ci¡
gu
w
2
C
okre±lam
y
zbiór
B
w
(
k
)
wzorem
B
w
(
k
)
:=
f
v
2
F
n
2
j
d
(
w
;
v
)
k
g
.
Wtedy
j
B
w
(
k
)
j
=
P
k
i
=0
k
i
dla
k
a»dego
w
2
C
oraz
B
w
1
(
k
)
\
B
w
2
(
k
)
=
;
dla
w
1
6=
w
2
.
St¡d
(
P
k
i
=0
n
i
)
j
C
j
2
n
,
co
k
o«czy
do
w
ó
d.
76.
Przypu±¢m
y
,
»e
d
=
(
d
1
;
:
:
:
;
d
10
)
jest
p
opra
wn
ym
k
o
dem
ISBN.
P
ok
a»em
y
,
»e
wtedy
d
0
=
(
d
1
;
:
:
:
;
d
i
1
;
d
i
+1
;
d
i
;
d
i
+2
;
:
:
:
;
d
10
)
jest
p
opra
w-
n
ym
k
o
dem
ISBN
wtedy
i
t
ylk
o
wtedy
,
gdy
d
i
+1
=
d
i
.
Mam
y
n
:=
1
d
1
+
+
(
i
1)
d
i
1
+
id
i
+1
+
(
i
+
1)
d
i
1
+
(
i
+
2)
d
i
+2
+
+
10
d
10
=
1
d
1
+
10
d
10
+
d
i
+1
d
i
d
i
+1
d
i
(mo
d
11)
.
Zatem
n
0
(mo
d
11)
wtedy
i
t
ylk
o
wtedy
,
gdy
d
i
=
d
i
+1
,
gdy»
d
i
;
d
i
+1
2
f
0
;
:
:
:
;
10
g
.
77.
d
min
(
C
)
=
3
.
77.
(a)
.
H
v
T
=
0
,
wi¦c
wysªano
v
.
77.
(b)
.
H
v
T
=
0
,
wi¦c
wysªano
v
.
77.
(c)
.
H
v
T
=
(1
;
0
;
0
;
0)
T
,
który
jest
5.
k
olumn¡
macierzy
H
,
a
wi¦c
bª¡d
wyst¡
piª
na
5.
miejscu,
zatem
wysªano
(0
;
0
;
0
;
1
;
0
;
1
;
0
;
1)
.
77.
(d)
.
H
v
T
=
(0
;
1
;
0
;
1)
T
,
a
wi¦c
wysªano
(0
;
1
;
1
;
0
;
1
;
1
;
1
;
1)
.
77.
(e)
.
H
v
T
=
(1
;
0
;
1
;
0)
T
,
a
wi¦c
wysªano
(0
;
0
;
1
;
1
;
1
;
1
;
0
;
0)
.
78.
d
min
(
C
)
=
3
.
79.
d
min
(
C
)
=
5
.
22
80.
d
min
(
C
)
=
3
.
Baza
linio
w
¡
k
o
du
C
s¡
w
ektory:
(1
;
0
;
0
;
0
;
2
;
0
;
2
;
1)
,
(0
;
1
;
0
;
0
;
0
;
2
;
2
;
0)
,
(0
;
0
;
1
;
0
;
2
;
0
;
2
;
2)
i
(0
;
0
;
0
;
1
;
0
;
0
;
2
;
2)
.
81.
(a)
.
X
5
1
=
(
X
+
1)(
X
4
+
X
3
+
X
2
+
X
+
1)
,
wi¦c
mam
y
2
nietrywialne
k
o
dy
cykliczne
dªugo±ci
5
nad
F
2
o
nast¦puj¡cyc
h
macierzac
h
k
on
troli
parzysto±ci:
2
6
6
4
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
3
7
7
5
;
1
1
1
1
1
:
81.
(b)
.
X
9
1
=
(
X
+
1)(
X
2
+
X
+
1)(
X
6
+
X
3
+
1)
,
wi¦c
mam
y
6
nietry-
wialn
yc
h
k
o
dó
w
cykliczn
yc
h
dªugo±ci
9
nad
F
2
o
nast¦puj¡cyc
h
macierzac
h
k
on
troli
parzysto±ci:
2
6
6
6
6
6
6
6
6
6
6
4
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
3
7
7
7
7
7
7
7
7
7
7
5
;
2
6
6
6
6
6
6
6
6
4
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
3
7
7
7
7
7
7
7
7
5
;
2
6
6
6
6
6
6
4
1
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
1
3
7
7
7
7
7
7
5
;
2
4
1
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
1
3
5
;
1
1
0
1
1
0
1
1
0
0
1
1
0
1
1
0
1
1
;
1
1
1
1
1
1
1
1
1
:
81.
(c)
.
X
8
1
=
(
X
+
1)(
X
+
2)(
X
2
+
1)(
X
2
+
X
+
2)(
X
2
+
2
X
+
2)
,
wi¦c
mam
y
30
nietrywialn
yc
h
k
o
dó
w
cykliczn
yc
h
dªugo±ci
9
nad
F
2
o
nast¦puj¡cyc
h
macierzac
h
k
on
troli
parzysto±ci:
2
6
6
6
6
6
6
6
6
4
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
3
7
7
7
7
7
7
7
7
5
;
2
6
6
6
6
6
6
6
6
4
1
2
0
0
0
0
0
0
0
1
2
0
0
0
0
0
0
0
1
2
0
0
0
0
0
0
0
1
2
0
0
0
0
0
0
0
1
2
0
0
0
0
0
0
0
1
2
0
0
0
0
0
0
0
1
2
3
7
7
7
7
7
7
7
7
5
;
23
2
6
6
6
6
6
6
4
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
3
7
7
7
7
7
7
5
;
2
6
6
6
6
6
6
4
1
0
2
0
0
0
0
0
0
1
0
2
0
0
0
0
0
0
1
0
2
0
0
0
0
0
0
1
0
2
0
0
0
0
0
0
1
0
2
0
0
0
0
0
0
1
0
2
3
7
7
7
7
7
7
5
;
2
6
6
6
6
6
6
4
1
1
2
0
0
0
0
0
0
1
1
2
0
0
0
0
0
0
1
1
2
0
0
0
0
0
0
1
1
2
0
0
0
0
0
0
1
1
2
0
0
0
0
0
0
1
1
2
3
7
7
7
7
7
7
5
;
2
6
6
6
6
6
6
4
1
2
2
0
0
0
0
0
0
1
2
2
0
0
0
0
0
0
1
2
2
0
0
0
0
0
0
1
2
2
0
0
0
0
0
0
1
2
2
0
0
0
0
0
0
1
2
2
3
7
7
7
7
7
7
5
;
2
6
6
6
6
4
1
0
1
1
0
0
0
0
0
1
0
1
1
0
0
0
0
0
1
0
1
1
0
0
0
0
0
1
0
1
1
0
0
0
0
0
1
0
1
1
3
7
7
7
7
5
;
2
6
6
6
6
4
1
0
1
2
0
0
0
0
0
1
0
1
2
0
0
0
0
0
1
0
1
2
0
0
0
0
0
1
0
1
2
0
0
0
0
0
1
0
1
2
3
7
7
7
7
5
;
2
6
6
6
6
4
1
1
0
1
0
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
0
1
3
7
7
7
7
5
;
2
6
6
6
6
4
1
1
1
1
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
1
1
1
3
7
7
7
7
5
;
2
6
6
6
6
4
1
2
0
2
0
0
0
0
0
1
2
0
2
0
0
0
0
0
1
2
0
2
0
0
0
0
0
1
2
0
2
0
0
0
0
0
1
2
0
2
3
7
7
7
7
5
;
2
6
6
6
6
4
1
2
1
2
0
0
0
0
0
1
2
1
2
0
0
0
0
0
1
2
1
2
0
0
0
0
0
1
2
1
2
0
0
0
0
0
1
2
1
2
3
7
7
7
7
5
;
2
6
6
4
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
3
7
7
5
;
2
6
6
4
1
0
0
0
2
0
0
0
0
1
0
0
0
2
0
0
0
0
1
0
0
0
2
0
0
0
0
1
0
0
0
2
3
7
7
5
;
2
6
6
4
1
1
0
1
2
0
0
0
0
1
1
0
1
2
0
0
0
0
1
1
0
1
2
0
0
0
0
1
1
0
1
2
3
7
7
5
;
2
6
6
4
1
1
1
2
1
0
0
0
0
1
1
1
2
1
0
0
0
0
1
1
1
2
1
0
0
0
0
1
1
1
2
1
3
7
7
5
;
2
6
6
4
1
2
0
2
2
0
0
0
0
1
2
0
2
2
0
0
0
0
1
2
0
2
2
0
0
0
0
1
2
0
2
2
3
7
7
5
;
2
6
6
4
1
2
1
1
1
0
0
0
0
1
2
1
1
1
0
0
0
0
1
2
1
1
1
0
0
0
0
1
2
1
1
1
3
7
7
5
;
24
2
4
1
0
2
1
1
1
0
0
0
1
0
2
1
1
1
0
0
0
1
0
2
1
1
1
3
5
;
2
4
1
0
2
2
1
2
0
0
0
1
0
2
2
1
2
0
0
0
1
0
2
2
1
2
3
5
;
2
4
1
1
0
0
1
1
0
0
0
1
1
0
0
1
1
0
0
0
1
1
0
0
1
1
3
5
;
2
4
1
1
1
2
0
1
0
0
0
1
1
1
2
0
1
0
0
0
1
1
1
2
0
1
3
5
;
2
4
1
2
0
0
1
2
0
0
0
1
2
0
0
1
2
0
0
0
1
2
0
0
1
2
3
5
;
2
4
1
2
1
1
0
2
0
0
0
1
2
1
1
0
2
0
0
0
1
2
1
1
0
2
3
5
;
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
;
1
0
2
0
1
0
2
0
0
1
0
2
0
1
0
2
;
1
1
2
0
2
2
1
0
0
1
1
2
0
2
2
1
;
1
2
2
0
2
1
1
0
0
1
2
2
0
2
1
1
;
1
1
1
1
1
1
1
1
;
1
2
1
2
1
2
1
2
:
25