ELEMENTY TEORII LICZB
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