Dyskretna I

1. Rozłóż na czynniki liczby a, b oraz znajdź NWD(a, b) i NWW(a, b)

a) a = 38571, b = 35217

a = 38571 = 3 * 12857 = 3 * 13 * 989 = 3 * 13 * 23 * 43
b = 35217 = 3 * 11739 = 3 * 3 * 3913 = 3 * 3 * 7 * 559 = 3 * 3 * 7 * 13 * 43

NWD(a, b) = 3 * 13 * 43 = 1677
NWW(a, b) = 3 * 13 * 43 * 23 * 3 * 7 = 809991

Sprawdzenie:
NWW(a, b) = (a * b) / NWD(a, b)
(38571 * 35217) / 1677 = 1358354907 / 1677 = 809991 = NWW(a, b)

b) a = 9620, b = 31365

a = 9620 = 2 * 4810 = 2 * 2 * 2405 = 2 * 2 * 5 * 481 = 2 * 2 * 5 * 13 * 37
b = 31365 = 3 * 10455 = 3 * 3 * 3485 = 3 * 3 * 5 * 697 = 3 * 3 * 5 * 17 * 41

NWD(a, b) = 5
NWW(a, b) = 5 * 2 * 2 * 13 * 37 * 3 * 3 * 17 *41 = 60346260
NWW(a, b) = (a * b) / 5 = 60346260

c) a = 6138, b = 4872

a = 6138 = 2 * 3069 = 2 * 3 * 1023 = 2 * 3 * 3 * 341 = 2 * 3 * 3 * 11 * 31
b = 4872 = 2 * 2436 = 2 * 2 * 1218 = 2 * 2 * 2 * 609 = 2 * 2 * 2 * 3 * 203 = 2 * 2 * 2 * 3 * 7 * 29

NWD(a, b) = 2 * 3 = 6
NWW(a, b) = (a * b) / 6 = 4984056

NWD(6138, 4872) algorytmem Euklidesa

Metoda 1 - Reszta dodatnia

6138 / 4872 = 1 r. 1266
4872 / 1266 = 3 r. 1074
1266 / 1074 = 1 r. 192
1074 / 192 = 5 r. 114
192 / 114 = 1 r. 78
114 / 78 = 1 r. 36
78 / 36 = 2 r. 6
36 / 6 = 6 r. 0

Metoda 2 - Reszta ujemna, nie większa od b

6138 / 4872 = 1 r. 1266
4872 / 1266 = 4 r. -192
1266 / 192 = 7 r. -78
192 / 78 = 2 r. 36
78 / 36 = 2 r. 6
36 / 6 = 6 r. 0

NWD(6138, 4872) = 6

2. Oblicz NWD(4321, 1234) stosując algorytm Euklidesa, a następnie wyraź go jako kombinacje liniową.

Metoda 1 - Reszta dodatnia

4321 / 1234 = 3 r. 619
1234 / 619 = 1 r. 615
619 / 615 = 1 r. 4
615 / 4 = 153 r. 3
4 / 3 = 1 r. 1
3 / 1 = 3 r. 0

Metoda 2 - Reszta ujemna, nie większa od b

4321 / 1234 = 4 r. -615
1234 / 615 = 2 r. 4
615 / 4 = 154 r. -1
4 / 1 = 4 r. 0

Metoda 3

NWD(4321, 1234) = NWD(4321, 617) = NWD(3704, 617) = NWD(1852, 617) = NWD(926, 617) =
NWD(463, 617) = NWD(617, 463) = NWD(154, 463) = NWD(463, 154) = NWD(463, 77) = NWD(386, 77) = NWD(193, 77) = NWD(116, 77) = NWD(58, 77) = NWD(77, 58) = NWD(77, 29) = NWD(48, 29) =
NWD(24, 29) = NWD(29, 24) = NWD(29, 12) = NWD(29, 6) = NWD(29, 3) = NWD(26, 3) = NWD(13, 3) = NWD(10, 3) = NWD(5, 3) = NWD(2, 3) = NWD(3, 2) = NWD(3, 1) = NWD(2, 1) = NWD(1, 1) = 1

NWD(4321, 1234) = 1 ponieważ są to liczby względnie pierwsze nie posiadające wspólnych czynników.

Sprawdzenie
a = 4321 = 29 * 149
b = 1234 = 2 * 617

Kombinacja liniowa (4321, 1234)

1 =
4 - 3 =
4 - (615 - 4 * 153) =
4 - 615 + 4 * 153 =
619 - 615 - 615 + 4 * 153 =
619 - 2 * 615 + 4 * 153 =
619 - 2 * (1234 - 619) + 4 * 153 =
619 - 2 * 1234 + 2 * 619 + 4 * 153 =
3 * 619 - 2 * 1234 + 4 * 153 =
3 * (4321 - 3 * 1234) - 2 * 1234 + 4 * 153 =
3 * 4321 - 9 * 1234 - 2 * 1234 + 4 * 153 =
3 * 4321 - 11 * 1234 + 4 * 153

3. Znajdź

a) 49^-1(mod65)

NWD(49, 65) = 1

65 / 49 = 1 r. 16
49 / 16 = 3 r. 1
16 / 1 = 16 r. 0

1 =
49 - 3 * 16 =
49 - 3 * (65 - 49) =
49 - 3 * 65 + 3 * 49 =
4 * 49 - 3 * 65

49^-1(mod65) = 4

b) 145^-1(mod321)

NWD(145, 321) = 1

321 / 145 = 2 r. 31
145 / 31 = 4 r. 21
31 / 21 = 1 r. 10
21 / 10 = 2 r. 1
10 / 1 = 10 r. 0

1 =
21 - 2 * 10 =
21 - 2 * (31 - 21) =
21 - 2 * 31 + 2 * 21 =
3 * 21 - 2 * 31 =
3 * (145 - 4 * 31) - 2 * 31 =
3 * 145 - 12 * 31 - 2 * 31 =
3 * 145 - 14 * 31 =
3 * 145 - 14 * (321 - 2 * 145) =
3 * 145 - 14 * 321 + 28 * 145 =
31 * 145 - 14 * 321

145^-1(mod321) = 31

c) 156^-1(mod427)

NWD(156, 427) = 1

427 / 156 = 2 r. 115
156 / 115 = 1 r. 41
115 / 41 = 2 r. 33
41 / 33 = 1 r. 8
33 / 8 = 4 r. 1
8 / 1 = 8 r. 0

1 =
33 - 4 * 8 =
33 - 4 * (41 - 33) =
33 - 4 * 41 + 4 * 33 =
5 * 33 - 4 * 41 =
5 * (115 - 2 * 41) - 4 * 41 =
5 * 115 - 2 * 41 - 4 * 41 =
5 * 115 - 6 * 41 =
5 * 115 - 6 * (156 - 115) =
5 * 115 - 6 * 156 + 6 * 115 =
11 * 115 - 6 * 156 =
11 * (427 - 2 * 156) - 6 * 156 =
11 * 427 - 22 * 156 - 6 * 156 =
11 * 427 - 28 * 156

156^-1(mod427) = - 28

4. Rozwiąż kongruencję

a) 3x ≡ 4(mod7)

x ≡ 3^-1 * 4(mod7)
x ≡ 3^-1(mod7) * 4

NWD(3, 7) = 1

7 / 3 = 2 r. 1
3 / 1 = 3 r. 0

1 =
7 - 2 * 3

3^-1(mod7) = - 2(mod7) = 5

x = 5 * 4 = 20 = 2 * 7 + 6
x = 7k + 6

b) 12x ≡ 18(mod42)

x ≡ 12^-1 * 18(mod42)
x ≡ 12^-1(mod42) * 18

NWD(12, 42) = 6

42 / 12 = 3 r. 6
12 / 6 = 2 r. 0

12x ≡ 18(mod42) / :6
2x ≡ 3(mod7)
x ≡ 2^-1(mod7) * 3

NWD(2, 7) = 1

7 / 2 = 3 r. 1
2 / 1 = 2 r. 0

1 =
7 - 3 * 2

2^-1(mod7) = -3(mod7) = 4

x = 4 * 3 = 12 = 7 + 5
x = 7k +5

c) 15x ≡ 38(mod43)

x ≡ 15^-1 * 38(mod43)
x ≡ 15^-1(mod43) * 38

NWD(15, 43) = 1

43 / 15 = 2 r. 13
15 / 13 = 1 r. 2
13 / 2 = 6 r. 1
2 / 1 = 2 r. 0

1 =
13 - 6 * 2 =
13 - 6 * (15 - 13) =
13 - 6 * 15 + 6 * 13 =
7 * 13 - 6 * 15 =
7 * (43 - 2 * 15) - 6 * 15 =
7 * 43 - 14 * 15 - 6 * 15 =
7 * 43 - 20 * 15

15^-1(mod43) = - 20(mod43) = 23

x = 23 * 38 = 874 = 20 * 43 + 14
x = 43k + 14

5a. Znaleźć najmniejsza liczbę całkowitą dodatnią spełniającą układ kongruencji:

M_k = m / m_k

N_l = M_k^-1(mod m_l)

{ x ≡ 1(mod11)
{ x ≡ 2(mod12)
{ x ≡ 3(mod13)

M₁ = 12 * 13 = 156
M₂ = 11 * 13 = 143
M₃ = 11 * 12 = 132

N₁ = 156^-1(mod11) = - 5
N₂ = 143^-1(mod12) = - 1
N₃ = 132^-1(mod13) = - 6

m = 11 * 12 * 13 = 1716

NWD(156, 11) = 1

156 / 11 = 14 r. 2
11 / 2 = 5 r. 1
2 / 1 = 2 r. 0

1 =
11 - 5 * 2 =
11 - 5 * (156 - 14 * 11) =
11 - 5 * 156 + 70 * 11 =
71 * 11 - 5 * 156

NWD(143, 12) = 1

143 / 12 = 11 r. 11
12 / 11 = 1 r. 1
11 / 1 = 11 r. 0

1 =
12 - 11 =
12 - (143 - 11 * 12) =
12 - 143 + 11 * 12 =
12 * 12 - 143=
12 * 12 - 1 * 143

NWD(132, 13) = 1

132 / 13 = 10 r. 2
13 / 2 = 6 r. 1
2 / 1 = 2 r. 0

1 =
13 - 6 * 2 =
13 - 6 * (132 - 10 * 13) =
13 - 6 * 132 + 60 * 13 =
61 * 13 - 6 * 132

X = a₁ * M₁ * N₁ + a₂ * M₂ * N₂ + a₃ * M₃ * N₃

X = 1 * 156 * -5 + 2 * 143 * -1 + 3 * 132 * - 6 = -780 - 286 - 2376 = -3442 ≡ 1706(mod1716)

5b. Znaleźć najmniejsza liczbę całkowitą dodatnią spełniającą układ kongruencji:

M_k = M / m_k

N_l = M_k^-1(mod m_l)

{ x ≡ 3(mod7)
{ x ≡ 5(mod9)
{ x ≡ 2(mod11)

M₁ = 9 * 11 = 99
M₂ = 7 * 11 = 77
M₃ = 7 * 9 = 63

N₁ = 99^-1(mod7) = 1
N₂ = 77^-1(mod9) = 2
N₃ = 63^-1(mod11) = - 4

m = 7 * 9 * 11 = 693

NWD(99, 7) = 1

99 / 7 = 14 r. 1
7 / 1 = 7 r. 0

1 =
99 - 7 * 14 =
1 * 99 - 7 * 14

NWD(77, 9) = 1

77 / 9 = 8 r. 5
9 / 5 = 1 r. 4
5 / 4 = 1 r. 1
4 / 1 = 4 r. 0

1 =
5 - 4 =
5 - (9 - 5) =
2 * 5 - 9 =
2 * (77 - 8 * 9) - 9 =
2 * 77 - 16 * 9 - 9 =
2 * 77 - 17 * 9

NWD(63, 11) = 1

63 / 11 = 5 r. 8
11 / 8 = 1 r. 3
8 / 3 = 2 r. 2
3 / 2 = 1 r. 1
2 / 1 = 2 r. 0

1 =
3 - 2 =
3 - (8 - 2 * 3) =
3 - 8 + 2 * 3 =
3 * 3 - 8 =
3 * (11 - 8) - 8 =
3 * 11 - 3 * 8 - 8 =
3 * 11 - 4 * 8 =
3 * 11 - 4 * (63 - 5 * 11) =
3 * 11 - 4 * 63 + 20 * 11 =
23 * 11 - 4 * 63

X = 3 * 99 * 1 + 5 * 77 * 2 + 2 * 63 * - 4 = 563 ≡ 563(mod693)

---