Daszkiewicz A Matematyka dyskretna Zbiór zadań

background image

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

background image

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

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

background image

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

parami

wzgl¦dnie

pierwszymi

liczba-

mi

naturaln

ymi

b

¦d¡cymi

rozwi¡zaniem

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

wnanie

x

4

+

y

4

=

z

2

nie

ma

nietrywialn

yc

h

rozwi¡-

za«

naturaln

yc

h.

23.

Udo

w

o

dni¢,

»e

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

background image

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

background image

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

kryptogra czn

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

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

caªk

o

wite.

(d)

zbiór

liczb

p

ostaci

a

2

k

,

gdzie

liczb

y

a

i

k

caªk

o

wite,

k



0

.

(e)

zbiór

liczb

p

ostaci

a

+

b

3

p

2

,

gdzie

liczb

y

a

i

b

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

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

background image

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¢

wnanie

f

(

x

)

=

0

.

6

background image

(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

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

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

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

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

background image

(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

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

jej

generatorem

lub

kw

adratem

generatora?

72.

Wyliczy¢

rz¦dy

elemen

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

background image

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

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

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

background image

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

10

background image

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

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

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

background image

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



(

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

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

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



(

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

background image

20.

Je±li

a

=

p

1

1







p

r

r

i

b

=

q

1

1







q

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

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

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

w

arunki

zadania.

21.

P

oniew

liczb

y

x

i

y

wzgl¦dnie

pierwsze,

wi¦c

nie

mog¡

b

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

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

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

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

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

wno±ci

p

4

+

q

4

=

m

2

,

co

przeczy

minimalno±ci

z

.

23.

Wybierzm

y

nietrywialne

rozwi¡zanie

wnanie

x

4

=

z

2

+

y

4

o

mi-

nimalnej

w

arto±ci

x

.

Z

zadania

21

wynik

a,

»e

x

m

usi

b

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

background image

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

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

background image

30.

P

oniew

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

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

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

(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

(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

(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

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

background image

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

parami

ró»n

ymi

liczbami

pierw-

szymi

oraz

1

,

.

.

.

,

k

,

1

,

.

.

.

,

k

,

1

,

.

.

.

,

r

+

s

do

datnimi

liczbami

natu-

raln

ymi.

P

oniew

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

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

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

background image

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

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

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

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

background image

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

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

wna«



a

+

b

=

2

2

a

+

b

=

1

:

Rozwi¡zuj¡c

p

o

wy»szy

ukªad

wna«

dosta

jem

y

a

=

1

i

b

=

3

,

zatem

reszta

z

dzielenia

wielomian

u

f

przez

(

X

1)(

X

2)

jest

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

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

background image

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

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

i

2

.

62.

(b)

.

Pierwiastk

ami

wielomian

u

f

i

2

+

2

,

gdzie

jest

w

arst

w

¡

wielomian

u

X

w

ciele

F

9

:=

F

3

[

X

]

=

(

X

2

+

X

+

2)

.

19

background image

62.

(c)

.

Pierwiastk

ami

wielomian

u

f

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

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

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

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

background image

68.

(a)

.

Ilo±¢

generatoró

w

grup

y

F



q

jest

wna

'

(

q

1)

,

zatem

ilo±¢

generatoró

w

grup

y

F



9

jest

wna

4

.

nie

jest

generatorem

grup

y

F



9

,

b

o

4

=

1

,

za±

+

1

,

2

+

1

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

(

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

background image

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

.

De niujem

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

.

De niujem

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

.

De niujem

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

background image

80.

d

min

(

C

)

=

3

.

Baza

linio

w

¡

k

o

du

C

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

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

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

background image

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

background image

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


Wyszukiwarka

Podobne podstrony:
G Bobiński Matematyka Dyskretna I Zbiór Zadań
Bobiński G Matematyka dyskretna I Zbiór zadań
Bobiński Grzegorz Matematyka Dyskretna I Zbiór Zadań
Daszkiewicz A Matematyka Dyskretna I '2003
Matematyka Europejczyka Zbior zadan dla szkol ponadgimnazjalnych Zakres podstawowy i rozszerzony Kla
Matematyka Europejczyka Zbior zadan dla gimnazjum Klasa 1

więcej podobnych podstron