Kongruencje
m n(mod p) mMODp = nMODp
Relację (mod p) nazywamy relacją kongruencji modulo p
6 1 (mod 5) ;
12 2 (mod 5)
;
14 4 (mod 5)
Kongruencje nie zmieniają swoich właściwości przy obustronnym
podnoszeniu do potęgi (pierwiastkowaniu) oraz przy mnożeniu i
dzieleniu przez inne kongruencje
6 1 (mod 5) / 6
36 6 (mod 5) 1 (mod 5)
6 1 (mod 5) / * (12 2 (mod 5))
72 2 (mod 5)
1
7. Kongruencje
Definicja „przystawania do siebie nodulo n”. Właściwości kongruencji. Cechy
podzielności. Systemy liczbowe. Schemat Hornera. Zastosowania w algorytmach
sprawdzania podzielności liczb naturalnych oraz algorytmach szybkiego
potęgowania
.
2
Raz jeszcze o kongruencji (przystawaniu)
Utożsamimy ze sobą liczby różniące się o wielokrotność ustalonej liczby n, a
więc będziemy traktować identycznie liczby mające taką samą resztę z
dzielenia przez n. Taką relację między liczbami nazywa się przystawaniem
bądź kongruencją.
Liczba a przystaje do b modulo n, jeżeli różnica a − b jest wielokrotnością
liczby n, co
zapisuje się
.
Na przykład,
ponieważ 33 − 9 = 24 jest podzielne
przez 24;
ponieważ 15 − 1 = 14 jest podzielne przez
7;
ponieważ − 1 − 23 = − 24 jest podzielne przez
24.
Zastosowania – sprawdzanie podzielności liczb
Wyznacz największe x 3
15
podzielne przez 17
3
3
= 27 10 (mod 17)
27 10 (mod 17) / * 27 10 (mod 17)
3
6
100 (mod 17) 15 (mod 17)
3
6
15 (mod 17) / * 3
6
15 (mod 17)
3
12
225 (mod 17) 4 (mod 17)
3
12
4 (mod 17) / *3
3
10 (mod 17)
3
15
40 (mod 17) 6 (mod 17)
Zatem
3
15
– 6 0 (mod 17) bo 0 (mod 17) 17 (mod 17) 34
(mod 17), itd
x = 3
15
– 6
3
Na jaką cyfrę kończy się liczba 2
100
?
2
10
4 (mod 10)
1024 4 (mod 10)
2
10
4 (mod 10) /
2
2
20
16 (mod 10) 6 (mod 10)
2
20
6 (mod 10) /
2
2
40
36 (mod 10) 6 (mod 10)
2
40
6 (mod 10) /
2
2
80
36 (mod 10) 6 (mod 10
2
80
6 (mod 10) / (2
20
6 (mod 10) )
2
100
36 (mod 10) 6 (mod 10)
2
100
6 (mod 10)
Zatem 2
100
kończy się cyfrą 6.
4
Schemat Hornera
Schemat Hornera służy do obliczania wartości wielomianów wyższych
stopni.
Wielomian stopnia n postaci:
można przekształcić rozpoczynając od wyłączenia x ze wszystkich wyrazów,
w których występuje po czym otrzymujemy:
Kontynuując to postępowanie otrzymujemy:
Stąd wynika, że wielomian stopnia n można zapisać następującej postaci:
5
0
1
1
1
1
0
...
)
(
a
x
a
x
a
x
a
x
W
n
n
n
n
n
n
n
n
n
a
x
a
x
a
x
a
x
W
1
2
1
1
0
...
)
(
n
n
n
n
n
n
a
x
a
x
a
x
a
x
a
x
W
1
2
3
1
2
0
...
)
(
n
n
n
n
a
x
a
x
a
x
a
x
a
x
W
1
2
1
0
...
...
)
(
n
n
n
a
x
x
W
a
x
W
)
(
)
(
1
0
1
0
n
n
6
Przykład 1
Dana jest reprezentacja liczby M w systemie przy podstawie 10.
Oblicz jej postać w systemie dwójkowym, trójkowym i ósemkowym.
M = (45)
10
= 4*10
1
+ 5*10
0
(101101)
2
= 1*2
5
+ 0*2
4
+ 1*2
3
+1*2
2
+ 0*2
1
+ 1*2
0
=
32 + 0 + 8 + 4 + 0 + 1 = (45)
10
= 1*2
5
+ 1*2
=3
+1*2
2
+ 1*2
0
=
32 8 4 1 = (45)
10
= 1*2
5
+ 1*2
=3
+ 1*2
2
+ 1*2
0
=
= (100000)
2
+ (1000)
2
+ (100)
2
+ (1)
2
= (101101)
2
I jeszcze inaczej:
(101101)
2
=
= ((((1*2
+ 0)2
+ 1)2
+1)2 + 0)2+
1 =
=((((1*2
)2
+1)2
+1)2)2+
1 =
= (((5) 2 +1)2)2+1 =
= ((11)2)2+1 = 44 + 1 = 45
7
M = (45)
10
= 4*10
1
+ 5*10
0
(X)
3
= __*3
5
+ __*3
4
+ __*3
3
+ __*3
2
+ __*3
1
+ __*3
0
=
__*243 + __*81 + __*27 + __*9 + __*3 + __*1 =
(X)
10
_0_*243 + _0_*81 + _1_*27 + _2_*9 + _0_*3 + _0_*1 =
(45)
10
= (0)
3
+ (0)
3
+ (1000)
3
+ (200)
3
+ (0)
3
+ (0)
3
= (1200)
3
(X)
8
= __*8
5
+ __*8
4
+ __*8
3
+ __*8
2
+ __*8
1
+ __*8
0
=
__* 8
5
+ __* 8
4
+ __* 8
3
+ __*64 + __*8 + __*1 =
(X)
10
_0_* 8
5
+ _0_* 8
4
+ _0_* 8
3
+ _0_*64 + _5_*8 + _5_*1 =
(45)
10
= (0)
8
+ (0)
8
+ (0)
8
+ (0)
8
+ (50)
8
+ (5)
8
= (55)
8
8
2
0
2
1
...a
a
a
a
n
n
n
0
1
i
i
a
a
n
i
0
0
1
1
1
1
0
2
...
2
2
a
a
a
a
a
n
n
n
n
n
n
n
a
a
a
a
a
W
a
2
2
...
2
2
...
)
2
(
1
2
1
0
11
1
2
8
2
*
1
2
*
1
2
*
0
2
*
1
1011
0
1
2
3
2
Przykład 2
Liczba a zapisana w systemie binarnym ma postać
gdzie
dla
.
W systemie dziesiętnym liczba a ma
wartość
czyli
Korzystając ze schematu Hornera:
Najszybszy sposób obliczania potęgi x
n
.
Niech n = 45.
Zatem x
45
= x
((((1*2 + 0)2 + 1)2 +1)2 + 0)2+ 1
= (((((x
2
)
2
x)
2
)x)
2
)
2
x
Pamiętając że:
x*x = x
2
; x
2
x
2
= x
2+2
;
(x
2
)
3
= x
2*3
Dokonujemy sprawdzenia:
x
((((1*2 + 0)2 + 1)2 +1)2 + 0)2+ 1
= (x
((((1*2 + 0)2 + 1)2 +1)2 + 0)2
)x =
= (x
(((1*2 + 0)2 + 1)2 +1)2
)
2
x =
= ((x
((1*2 + 0)2 + 1)2 +1
)
2
)
2
x =
= (((x
((1*2 + 0)2 + 1)2
)x)
2
)
2
x =
= (((((x
(1*2 + 0)2
)x)
2
)x)
2
)
2
x =
= (((((x
(1*2 + 0)
)
2
x)
2
)x)
2
)
2
x =
= (((((x
(1*2)
)
2
x)
2
)x)
2
)
2
x =
= (((((x
2
)
2
x)
2
)x)
2
)
2
x
9
Raz jeszcze - obliczmy wartości x
22
.
Binarną postać wykładnika potęgi ;
zamieniamy na system dziesiętny
10
2
10110
n
22
0
2
*
1
2
*
1
2
*
0
2
*
1
2
*
0
2
*
1
2
*
1
2
*
0
2
*
1
10110
0
1
2
3
4
2
22
2
10
2
2
5
2
2
4
2
2
2
2
0
2
*
1
2
*
1
2
*
0
2
*
1
10110
2
x
x
x
x
x
x
x
x
x
x
x
x
x
;
11
ZADANIA
1. Określ liczbę podzielną przez 7, która leży najbliżej liczby 10
100 000
.
2. Podaj postać dziesiętnej liczby 43 w systemach o podstawie t = 2, 8 i 16.
W przypadku systemu o podstawie 16, przyjmij następujące oznaczenia
dla
jego „cyfr” większych od 9: 10 = A, 11 = B, 12 = C, 13 = D, 14 = E ,
15 = F.
3. Ile najmniej mnożeń należy wykonać, aby obliczyć wartość potęgi: x
6
, x
22
, x
42
.
4. Na jaką cyfrę kończą się liczby 2
80
?, 3
20
, 11
15
, 7
30
?
5. Na jakie dwie ostatnie cyfry kończą się liczby 3
30
?, 4
20
, 12
15
, 6
30
?
6. Które z poniższych kongruencji są prawdziwe:
10 1(mod 9) ; -5 31(mod 7) ; 23 71(mod 11) ; -26 44 (mod 10)
7. Rozwiąż następujące kongruencje:
3x + 2 1(mod 5) ; 25x 12(mod 7) ; 3x 1(mod 6)
Można pokazać, że kongruencja ax b(mod n) ma rozwiązanie wtedy i tylko wtedy
gdy NWD(a,n)|b
Document Outline