Zadania
z
matemat
yki
dyskretnej
-
zesta
w
1.
1.
Algorytm
Euklidesa
przykªady
,
przedsta
wianie
(
a;
b
)
=
ax
+
by
.
2.
Sito
Eratostenesa
wypisyw
anie
liczb
pierwszyc
h
do
100.
3.
Udo
w
o
dni¢
nieró
wno±ci
b
x
c
+
b
y
c
b
x
+
y
c
b
x
c
+
b
y
c
+
1
:
4.
W
yliczy¢
sum¦
b
x
c
+
b
x
c
.
5.
Zbada¢
czy
b
p
b
x
c
c
=
b
p
x
c
:
6.
Udo
w
o
dni¢
ró
wno±¢
b
x
+
m
n
c
=
b
b
x
c
+
m
n
c
.
7.
Nie
k
orzysta
j¡c
z
rozkªadu
na
czynniki
pierwsze
udo
w
o
dni¢
ró
wno±ci
(
ma;
mb
)
=
m
(
a;
b
)
,
a
(
a;b
)
;
b
(
a;b
)
=
1
.
8.
Udo
w
o
dni¢
ró
wno±¢
(
n
a
1
;
n
b
1)
=
n
(
a;b
)
1
:
1
Zadania
z
matemat
yki
dyskretnej
-
zesta
w
2.
1.
Iloma
zerami
jest
zak
o«czone
rozwini¦cie
dziesi¦tne
liczb
y
1000!?
2.
Rozªo»y¢
na
czynniki
pierwsze
liczb
¦
99!.
3.
ZnaleȢ
na
jwi¦ksz¡
p
ot¦g¦
liczb
y
pierwszej
p
dziel¡c¡
n
!
.
4.
P
ok
aza¢,
»e
dla
x
2
N
zac
ho
dzi
nieró
wno±¢
p
x
<
2
(
x
)
.
(
W
sk
azó
wk
a:
k
a»da
liczba
naturalna
da
je
si¦
zapisa¢
w
p
ostaci
sr
2
,
gdzie
liczba
s
jest
b
ezkw
adrato
w
a,
tj.
nie
dzieli
si¦
przez
kw
adrat
»adnej
liczb
y
pierwszej.)
W
ywniosk
o
w
a¢
st¡d
nieró
wno±¢
(
x
)
log
x
2
log
2
:
5.
Niec
h
p
2
P
.
Udo
w
o
dni¢,
»e
dla
k
a»dego
k
2
f
1
;
:
:
:
;
p
1
g
sym
b
ol
Newtona
p
k
jest
p
o
dzieln
y
przez
p
.
6.
Udo
w
o
dni¢,
»e
liczba
2
n
n
jest
p
o
dzielna
przez
ilo
czyn
Q
n<p<
2
n
p
wszystkic
h
liczb
pierw-
szyc
h
za
w
art
yc
h
mi¦dzy
n
a
2
n
.
W
ywniosk
o
w
a¢,
»e
dla
k
a»dego
caªk
o
witego
x
2
zac
ho
dzi
nieró
wno±¢
(
x
)
9
x
log
2
log
x
:
7.
Niec
h
a;
b
2
Z
.
P
ok
aza¢,
»e
je±li
(
a;
b
)
=
1
i
liczba
ab
jest
kw
adratem
liczb
y
naturalnej,
to
ró
wnie»
a
i
b
s¡
kw
adratami
liczb
naturaln
yc
h.
8.
P
ok
aza¢,
»e
je±li
na
jmniejsza
liczba
pierwsza
p
dziel¡ca
liczb
¦
naturaln¡
n
jest
wi¦ksza
o
d
3
p
n
,
to
n
=
p
lub
liczba
n=p
jest
pierwsza.
9.
Udo
w
o
dni¢,
»e
dla
»adnego
n
>
1
liczba
1
+
1
=
2
+
:
:
:
+
1
=n
nie
jest
liczb¡
caªk
o
wit¡.
10.
Udo
w
o
dni¢,
»e
dla
»adnego
n
>
1
liczba
1
+
1
=
3
+
1
=
5
+
:
:
:
+
1
=
(2
n
1)
nie
jest
liczb¡
caªk
o
wit¡.
11.
Udo
w
o
dni¢,
»e
'
(
n
)
n
=
Y
p
j
n
1
1
p
;
in
terpretuj¡c
lew
¡
stron¦
jak
o
pra
wdop
o
dobie«st
w
o,
»e
loso
w
o
wybrana
liczba
ze
zbioru
f
1
;
:
:
:
;
n
g
jest
wzgl¦dnie
pierwsza
z
n
.
12.
ZnaleȢ
dwie
ostatnie
cyfry
liczb
y
2
1999
.
13.
ZnaleȢ
dwie
ostatnie
cyfry
liczb
y
3
1999
.
14.
Niec
h
f
(
x
)
b
¦dzie
wielomianem
o
wsp
óªczynnik
ac
h
caªk
o
wit
yc
h,
ró»n
ym
o
d
staªej.
P
o-
k
aza¢,
»e
k
ongruencja
f
(
x
)
0
(mo
d
p
)
ma
rozwi¡zanie
dla
niesk
o«czenie
wielu
liczb
pierwszyc
h
p
.
1
15.
Niec
h
q
2
P
.
P
ok
aza¢,
»e
istnieje
niesk
o«czenie
wiele
takic
h
liczb
pierwszyc
h
p
,
»e
p
1
(mo
d
q
)
.
16.
Zna
jd¹
wszystkie
rozwi¡zania
nast¦puj¡cyc
h
k
ongruencji:
(a)
3
x
4
(mo
d
7)
;
(b)
27
x
25
(mo
d
256)
.
17.
Zna
jd¹
na
jmniejsze
nieujemne
rozwi¡zania
nast¦puj¡cyc
h
ukªadó
w
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)
2
Zadania
z
matemat
yki
dyskretnej
-
zesta
w
3.
1.
Niec
h
(
a;
b;
c
)
oznacza
na
jwi¦ksz¡
liczb
¦
naturaln¡
dziel¡c¡
k
a»d¡
z
liczb
a;
b;
c
.
Udo
w
o
d-
ni¢,
»e
(
a;
b;
c
)
=
(
a;
(
b;
c
))
.
2.
Niec
h
a
=
p
i
1
1
:
:
:
p
i
n
n
i
b
=
p
j
1
1
:
:
:
p
j
n
n
b
¦d¡
przedsta
wieniami
liczb
a
i
b
w
p
ostaci
ilo
czyn
u
p
ot¦g
ró»n
yc
h
liczb
pierwszyc
h.
W
yliczy¢
na
jwi¦kszy
wsp
óln
y
dzielnik
i
na
jmniejsz¡
wsp
óln¡
wielokrotno±¢
liczb
a;
b
.
3.
Napisa¢
algorytm,
który
dla
danej
pary
liczb
a;
b
2
Z
wylicza
ic
h
na
jwi¦kszy
wsp
óln
y
dzielnik
d
oraz
zna
jduje
takie
liczb
y
x;
y
2
Z
,
»e
d
=
ax
+
by
.
4.
Napisa¢
algorytm
zna
jduj¡cy
wszystkie
rozwi¡zania
ró
wnania
ax
+
by
=
c
.
5.
Udo
w
o
dni¢,
»e
liczba
10
9
+
1
jest
p
o
dzielna
przez
19
.
6.
Udo
w
o
dni¢,
»e
liczba
zapisana
w
systemie
dziesi¦tn
ym
jak
o
abcabc
jest
p
o
dzielna
przez
7
;
11
i
13
.
7.
Udo
w
o
dni¢,
»e
je±li
3
nie
dzieli
n
to
3
dzieli
n
4
+
n
2
+
1
.
8.
Udo
w
o
dni¢,
»e
liczba
10
6
1
jest
p
o
dzielna
przez
13
.
9.
Udo
w
o
dni¢,
»e
liczba
10
8
+
1
jest
p
o
dzielna
przez
17
.
10.
Udo
w
o
dni¢,
»e
je±li
liczba
n
nie
jest
p
o
dzielna
przez
5
,
to
liczba
n
4
+
64
nie
jest
liczb¡
pierwsz¡.
11.
Udo
w
o
dni¢,
»e
liczba
2
1000
+
5
nie
jest
liczb¡
pierwsz¡.
12.
Udo
w
o
dni¢,
»e
dla
n
>
0
liczba
2
2
n
1
jest
p
o
dzielna
przez
3
.
13.
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¡.
14.
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)
.
15.
Udo
w
o
dni¢,
»e
dla
wszystkic
h
a;
b;
n
2
N
liczba
a
2
n
+1
+
b
2
n
+1
jest
p
o
dzielna
przez
a
+
b
.
16.
Rozªo»y¢
na
czynniki
liczb
¦
2
32
1
.
17.
Dla
k
a»dego
z
p
oni»szyc
h
st
wierdze«
p
o
da
j
do
w
ó
d
lub
k
on
trprzykªad.
(a)
Je±li
a
2
b
2
(mo
d
n
)
,
to
a
b
(mo
d
n
)
.
(b)
Je±li
a
2
b
2
(mo
d
n
)
,
to
a
b
(mo
d
n
)
.
(c)
Je±li
p
jest
liczb¡
pierwsz¡
i
a
2
b
2
(mo
d
p
)
,
to
a
b
(mo
d
p
)
.
18.
P
ok
aza¢,
»e
je±li
a
b
(mo
d
m
)
i
a
b
(mo
d
n
)
,
to
a
b
(mo
d
N
W
W
(
m;
n
))
.
19.
Rozwi¡za¢
nast¦puj¡ce
k
ongruencje:
(a)
2
x
37
(mo
d
21)
,
1
(b)
5
x
15
(mo
d
25)
,
(c)
3
x
7
(mo
d
18)
.
20.
W
yliczy¢:
(a)
'
(1000)
,
(b)
'
(180)
,
(c)
'
(1001)
.
21.
Znale¹¢
wszystkie
liczb
y
n
dla
któryc
h
'
(
n
)
=
20
.
22.
Znale¹¢
wszystkie
liczb
y
n
dla
któryc
h
'
(
n
)
=
24
.
23.
Udo
w
o
dni¢,
»e
dla
wszystkic
h
m;
2
N
zac
ho
dzi
'
(
m
)
=
m
1
'
(
m
)
.
24.
Udo
w
o
dni¢,
»e
'
(
n
)
jest
liczb¡
parzyst¡
dla
wszystkic
h
n
>
2
.
25.
P
ok
aza¢,
»e
'
(2
m
)
jest
ró
wne
'
(
m
)
lub
2
'
(
m
)
,
opisa¢
kiedy
zac
ho
dzi
k
a»da
z
t
yc
h
mo»-
liw
o±ci.
26.
Udo
w
o
dni¢,
»e
je±li
d
=
(
a;
b
)
,
to
'
(
ab
)
=
d'
(
a
)
'
(
b
)
='
(
d
)
.
27.
Udo
w
o
dni¢,
»e
'
(
mn
)
=
'
((
m;
n
))
'
([
m;
n
])
.
28.
Udo
w
o
dni¢,
»e
je±li
d
j
n
,
to
'
(
d
)
j
'
(
n
)
.
29.
Znale¹¢
wszystkie
liczb
y
n
2
N
dla
któryc
h
'
(
n
)
=
2
a
dla
p
ewnego
a
2
N
.
30.
P
ok
aza¢,
»e
je±li
liczba
n
jest
zªo»ona
i
'
(
n
)
j
n
,
to
n
jest
b
ezkw
adrato
w
a
(tj.
nie
jest
p
o
dzielna
przez
kw
adrat
»adnej
liczb
y
pierwszej).
2