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