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