ELEMENTY TEORII LICZB

Definicja

Dla dowolnej liczby rzeczywistej

x

funkcją „podłoga” nazywamy

funkcję

 

 

x

x

Z

R

a

,

:

→

, przyporządkowującą liczbie

jej zaokrąglenie w dół do najbliższej liczby całkowitej.

Np.

 

 









3

75

2

5

5

4

6

4

3

3

−

=

−

−

=

−

=

=

,

,

,

,

,

Definicja

Dla dowolnej liczby rzeczywistej

x

funkcją „podłoga” nazywamy

funkcję

 

 

x

x

Z

R

a

,

:

→

, przyporządkowującą liczbie

jej zaokrąglenie w górę do najbliższej liczby całkowitej.

Np.

 

 

 





2

75

2

5

5

5

6

4

3

3

−

=

−

−

=

−

=

=

,

,

,

,

,

Twierdzenie

Dla dowolnych liczb naturalnych

b

a ,

istnieje dokładnie jedna para

liczb naturalnych

r

q,

spełniająca warunki:

1.

r

bq

a

+

=

,

2.

b

r

<

≤

0

,

gdzie

b

nazywamy ilorazem całkowitoliczbowym

a

przez

b

, zaś

r

- resztą z dzielenia.

Uwaga: Z twierdzenia wynika wprost, że









=

b

a

q

.

Resztę z dzielenia

a

przez

b

oznaczać będziemy

b

a mod

.

Definicja

Mówimy, że liczba całkowita

0

≠

a

dzieli liczbę całkowitą

b

,

jeżeli istnieje liczba całkowita

z

taka, że

az

b

=

.

Fakt ten oznaczamy

b

a |

, a liczbę

a

nazywamy dzielnikiem liczby

b

.

Oczywiście, jeśli

b

a |

, to

0

=

a

b mod

.

Twierdzenie

Jeżeli

b

a |

oraz

c

a |

, to

(

)

c

b

a

+

|

oraz

(

)

c

b

a

−

|

Definicja

Liczbą pierwszą nazywamy liczbę naturalną, której jedynymi

podzielnikami są ona sama i liczba 1.

Definicja

Liczby

a

i

b

nazywamy względnie pierwszymi, jeżeli jedynym ich

wspólnym dzielnikiem jest liczba 1.

Definicja

Niech

m

będzie dowolną liczbą naturalną. Dwie liczby całkowite

a

i

b

nazywać będziemy przystającymi modulo m, jeżeli

(

)

b

a

m

−

|

.

Piszemy wówczas

(

)

m

b

a

mod

≡

Tak określoną relację nazywamy relacją przystawania modulo m

lub relacją kongruencji.

Twierdzenie

Relacja kongruencji jest relacją równoważności, tzn. spełnia

warunki:

1. dla

każdego

Z

a

∈

zachodzi

)

(mod m

a

a

≡

2. dla

każdego

Z

b

a

∈

,

, jeżeli

(

)

m

b

a

mod

≡

, to

(

)

m

a

b

mod

≡

,

3. dla

każdego

Z

c

b

a

∈

,

,

, jeżeli

(

)

m

b

a

mod

≡

i

(

)

m

c

b

mod

≡

, to

(

)

m

c

a

mod

≡

.

Twierdzenie

Jeżeli

(

)

m

b

a

mod

≡

oraz

(

)

m

d

c

mod

≡

, to

1.

(

)

m

d

b

c

a

mod

+

≡

+

2.

(

)

m

c

b

c

a

mod

−

≡

−

3.

(

)

m

d

b

c

a

mod

⋅

≡

⋅

Przykład

Udowodnić, że liczba

1

9

3

91

91

+

+

jest podzielna przez 13.

Rozważmy relację przystawania modulo m dla pewnej liczby

naturalnej

m

. Dla dowolnej liczby całkowitej

p

definiujemy jej

klasę abstrakcji następująco:

[ ]

{

}

)

(mod

:

m

p

q

Z

q

p

≡

∈

=

Przykład

Dla

4

=

m

mamy cztery klasy abstrakcji

[ ]

{

} {

}

,...

,

,

,

,

...,

:

8

4

0

4

8

4

0

−

−

=

∈

∧

=

∈

=

Z

k

k

q

Z

q

[ ]

{

} {

}

,...

,

,

,

,

...,

:

9

5

1

3

7

1

4

1

−

−

=

∈

∧

+

=

∈

=

Z

k

k

q

Z

q

[ ]

{

} {

}

,...

,

,

,

,

...,

:

10

6

2

2

6

2

4

2

−

−

=

∈

∧

+

=

∈

=

Z

k

k

q

Z

q

[ ]

{

} {

}

,...

,

,

,

,

...,

:

11

7

3

1

5

3

4

3

−

−

=

∈

∧

+

=

∈

=

Z

k

k

q

Z

q

Dla dowolnej liczby naturalnej

m

mamy

m

klas abstrakcji relacji

modulo m .Są to klasy

[ ] [ ] [ ] [

]

1

2

1

0

−

m

,...,

,

,

W zbiorze tych klas wprowadzamy działania

[ ] [ ] [

]

y

x

y

x

+

=

+

[ ] [ ] [

]

y

x

y

x

−

=

−

[ ] [ ] [

]

y

x

y

x

⋅

=

⋅

Twierdzenie

Jeżeli

[ ] [ ]

y

x

=

oraz

[ ] [ ]

w

u

=

, to

[

] [

]

w

y

u

x

+

=

+

[

] [

]

w

y

u

x

−

=

−

[ ] [

]

w

y

u

x

⋅

=

⋅

Definicja

Dla dwóch liczb całkowitych

a

i

b

, największym wspólnym

dzielnikiem (NWD) nazywamy największą liczbę całkowitą, która

dzieli

a

i

b

.

Twierdzenie

Jeżeli liczby

a

oraz

b

są całkowite i

a

b

≤

<

0

, to wspólne

dzielniki liczb

a

oraz

b

są takie same jak wspólne dzielniki liczb

b

oraz

b

a

mod

, czyli gdy

( )

(

)

b

a

b

NWD

b

a

NWD

mod

,

,

=

Dowód:

Zauważmy najpierw, że liczbę

a

możemy przedstawić w postaci

(

)





b

a

b

b

a

a

mod

:

+

⋅

=

.

Jeżeli liczba r jest wspólnym dzielnikiem pary

b

a

,

, to

r

dzieli

także resztę

b

a

mod

, czyli

r

jest wspólnym dzielnikiem pary

(

)

b

b

a

,

mod

. Na odwrót, jeżeli liczba

r

jest wspólnym dzielnikiem

pary

(

)

b

b

a

,

mod

, to

r

dzieli także

a

, czyli

r

jest wspólnym

dzielnikiem pary

b

a

,

.

Algorytm Euklidesa

Aby obliczyć

( )

b

a

NWD

,

stosujemy następujący algorytm:

1. dopóki

0

≠

⋅ b

a

wykonuj

jeżeli

b

a

≥

, to

b

a

a

mod

:

=

,

w przeciwnym razie

a

b

b

mod

:

=

2.

b

a

NWD

+

=

:

Przykład

Obliczyć

(

)

15

36,

NWD

a

b

36 15

6 15

0 3

0 3

Zatem

(

)

3

15

36

=

,

NWD

Zbiór klas abstrakcji relacji równoważności modulo

m

wraz z

działaniami dodawania i mnożenia klas tworzy pierścień

przemienny z jedynką oznaczany

m

Z

.

Uporządkowaną trójkę (P,+,*), gdzie P jest niepustym zbiorem P

wyposażonym w dwa działania wewnętrzne oznaczone przez + i * nazywamy

pierścieniem jeżeli

1.(P,+) jest grupą abelową,

2.(P,*) jest półgrupą tzn. jest to zbiór P z działaniem łącznym,

drugie działanie jest rozdzielne względem pierwszego

Element

m

Z

a

∈

nazywamy odwracalnym w pierścieniu

m

Z

, jeśli

istnieje element

m

Z

b

∈

taki, że

)

(mod m

b

a

1

=

⋅

. Wówczas

element

b

nazywamy elementem odwrotnym do elementu

a

i oznaczamy

1

−

a

.

Twierdzenie

Liczba

m

Z

a

∈

jest odwracalna wtedy i tylko wtedy, gdy

(

)

1

=

m

a

NWD ,

.

Twierdzenie

Jeżeli liczba

m

jest pierwsza, to każdy element

0

≠

∈

a

Z

a

m

,

jest

odwracalny.

Funkcją liniową w pierścieniu

m

Z

nazywamy funkcję postaci

m

Z

x

m

b

ax

x

f

∈

+

=

),

(mod

)

(

Twierdzenie

Jeżeli

1

=

)

,

( m

a

NWD

, to funkcja

)

(mod

)

(

m

b

ax

x

f

+

=

jest

wzajemnie jednoznaczna.

W oparciu o powyższe twierdzenie można tworzyć szyfry liniowe.

Aby tego dokonać przypisujemy literom z alfabetu łacińskiego

liczby ze zbioru {0,1,2,...,25} w następujący sposób:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Teraz wybieramy dwie liczby

26

,

Z

b

a

∈

takie, że

1

)

,

(

=

b

a

NWD

i szyfrujemy litera po literze wg wzoru:

)

26

(mod

)

(

b

ax

x

C

+

=

Wówczas funkcja deszyfrująca jest postaci:

)

26

(mod

)

(

1

1

b

a

y

a

y

D

−

−

+

=

Przykład

Zaszyfrować słowo MATEMATYKA za pomocą funkcji

)

26

(mod

20

23

)

(

+

=

x

x

C

LITERA M A T E Y K

x 12 0 19

4 24 10

C(x) 10 20 15

8 0 16

SZYFR K U P I A Q

MATEMATYKA = KUPIKUPAQU

Przykład

Odszyfrować słowo ICXUKWN za pomocą funkcji

)

26

(mod

20

23

)

(

+

=

x

x

C

Funkcja deszyfrująca ma postać

)

26

(mod

20

23

23

)

(

1

1

⋅

+

=

−

−

y

y

D

Zauważamy najpierw, że

)

26

(mod

17

23

1

=

−

, bo

)

26

(mod

1

1

26

15

391

17

23

=

+

⋅

=

=

⋅

Ostatecznie funkcja deszyfrująca ma postać

)

26

(mod

2

17

2

26

13

17

20

17

17

)

(

+

=

+

⋅

+

=

⋅

+

=

y

y

y

y

D

Zatem otrzymujemy tabelę

SZYFR

I C X U K W N

Y 8

2 23 20 10 22 13

D(y)

4

)

26

(mod

2

8

17

=

+

⋅

LITERA

E

Po uzupełnieniu otrzymujemy

SZYFR

I C X U K W N

Y 8

2 23 20 10 22 13

D(y)

4

)

26

(mod

2

8

17

=

+

⋅

LITERA

E G Z A M I N