Dyskretna II

1. Rozwiąż kongruencję

a) 3x ≡ 4(mod12)

x = 3^-1(mod12) * 4

NWD(12, 3) = 3

12 / 3 = 4 r. 0

Brak rozwiązania ponieważ 3 nie jest podzielne przez 4

b) 9x ≡ 12(mod21)

9x ≡ 12(mod21) / :3
3x ≡ 4(mod7)
x = 3^-1(mod7) * 4

NWD(7, 3) = 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

c) 103x ≡ 612(mod676)

x = 103^-1(mod676) * 612

NWD(676, 103) = 1

676 / 103 = 6 r. 58
103 / 58 = 1 r. 45
58 / 45 = 1 r. 13
45 / 13 = 3 r. 6
13 / 6 = 12 r. 1
6 / 1 = 6 r. 0

1 =
13 - 2 * 6 =
13 - 2 * (45 - 13 * 3) =
13 - 2 * 45 + 6 * 13 =
7 * 13 - 2 * 45 =
7 * (58 - 45) - 2 * 45 =
7 * 58 - 7 * 45 - 2 * 45 =
7 * 58 - 9 * 45 =
7 * 58 - 9 * (103 - 58) =
7 * 58 - 9 * 103 + 9 * 58 =
16 * 58 - 9 * 103 =
16 * (676 - 103 * 6) - 9 * 103 =
16 * 676 - 96 * 103 - 9 * 103 =
16 * 676 - 105 * 103

103^-1(mod676) = -105(mod676) = 571

x = 571 * 612 = 349452 = 516 * 676 + 636
x = 676k + 636

d) 27x ≡ 25(mod256)

x = 27^-1(mod256) * 25

NWD(256, 27) = 1

256 / 27 = 9 r. 13
27 / 13 = 2 r. 1
13 / 1 = 13 r. 0

1 =
27 - 2 * 13 =
27 - 2 * (256 - 9 * 27) =
27 - 2 * 256 + 18 * 27 =
19 * 27 - 2 * 256

27^-1(mod7) = 19(mod7) = 5

x = 5 * 25 = 125 = 17 * 7 + 6
x = 7k + 6

2a. Znajdź najmniejszą liczbę całkowitą dodatnią spełniającą układ kongruencji: - to na pewno będzie na kolokwium

{ x ≡ 12(mod31)
{ x ≡ 87(mod127)
{ x ≡ 91(mod255)

M₁ = 32385
M₂ = 7905
M₃ = 3937

N₁ = 32385^-1(mod31) = 3
N₂ = 7905^-1(mod127) = 41
N₃ = 3937^-1(mod255) = 148

m = 1003935

NWD(32385, 31) = 1

32385 / 31 = 1044 r. 21
31121 = 1 r. 10
21 / 10 = 2 r. 1
10 / 1 = 10 r. 0

NWD(7905, 127) = 1

7905 / 127 = 62 r. 31
127 / 31 = 4 r. 3
31 / 3 = 10 r. 1
3 / 1 = 3 r. 0

NWD (3937, 255) = 1

3937 / 255 = 15 r. 112
255 / 112 = 2 r. 31
112 / 31 = 3 r. 19
31 / 19 = 1 r. 12
19 / 12 = 1 r. 7
12 / 7 = 1 r. 5
7 / 5 = 1 r. 2
5 / 2 = 2 r. 1
2 / 1 = 2 r. 0

1 =
21 - 2 * 10 =
21 - 2 * (31 - 21) =
21 - 2 * 31 + 2 * 21 =
3 * 21 - 2 * 31 =
3 * (32385 - 1044 * 31) - 2 * 31 =
3 * 32385 - 3132 * 31 - 2 *31 =
3 * 32385 - 3134 * 31

1 =
31 - 10 * 3 =
31 - 10 * (127 - 4 * 31) =
31 - 10 * 127 + 40 * 31 =
41 * 31 - 10 * 127 =
41 * (7905 - 62 * 127) - 10 * 127 =
41 * 7905 - 2542 * 127 - 10 * 127 =
41 * 7905 - 2552 * 127

1 =
2 - 1 =
2 - (5 - 2 * 2) =
2 - 5 + 2 * 2 =
3 * 2 - 5 =
3 * (7 - 5) - 5 =
3 * 7 - 3 * 5 - 5 =
3 * 7 - 4 * 5 =
3 * 7 - 4 * (12 - 7) =
3 * 7 - 4 * 12 + 4 * 7 =
7 * 7 - 4 * 12 =
7 * (19 - 12) - 4 * 12 =
7 * 19 - 7 * 12 - 4 * 12 =
7 * 19 - 11 * 12 =
7 * 19 - 11 * (31 - 19) =
7 * 19 - 11 * 31 + 11 * 19 =
18 * 19 - 11 * 31 =
18 * (112 - 3 * 31) - 11 * 31 =
18 * 112 - 54 * 31 - 11 * 31 =
18 * 112 - 65 * 31 =
18 * 112 - 65 * (255 - 2 * 112) =
18 * 112 - 65 * 255 + 130 * 112 =
148 * 112 - 65 * 255 =
148 * (3937 - 15 * 255) - 65 * 255 =
148 * 3937 - 2220 * 255 - 65 * 255 =
148 * 3937 - 2285 * 255

X = 12 * 32385 * 3 + 87 * 7905 * 41 + 91 * 3937 * 148 = 82386511 ≡ 63841(mod1003935)

2b. Znajdź najmniejszą liczbę całkowitą dodatnią spełniającą układ kongruencji: - to na pewno będzie na kolokwium

{ x ≡ 2(mod3)
{ x ≡ 3(mod5)
{ x ≡ 4(mod11)
{ x ≡ 5(mod16)

M₁ = 880
M₂ = 528
M₃ = 240
M₄ = 165

N₁ = 880^-1(mod3) = 1
N₂ = 528^-1(mod5) = 2
N₃ = 240^-1(mod11) = 5
N₄ = 165^-1(mod16) = - 3

m = 2640

1 =
1 * 880 - 3 * 293

1 =
3 - 2 =
3 - (5 - 3) =
2 * 3 - 5 =
2 * (528 - 105 * 5 ) - 5 =
2 * 528 - 210 * 5 - 5 =
2 * 528 - 211 * 5

1 =
9 - 4 * 2 =
9 - 4 * (11 - 9) =
9 - 4 * 11 + 4 * 9 =
5 * 9 - 4 * 11 =
5 * (240 - 21 * 11) - 4 * 11 =
5 * 240 - 105 * 11 - 4 * 11 =
5 * 240 - 109 * 11

1 =
16 - 3 * 5 =
16 - 3 * (165 - 10 * 16) =
16 - 3 * 165 + 30 * 16 =
31 * 16 - 3 * 165

X = 2 * 880 * 1 + 3 * 528 * 2 + 4 * 240 * 5 + 5 * 165 * -3 = 7253 ≡ 1973(mod2640)

3. Znajdź wartość funkcji Eulera: φ(42), φ(56), φ(75), φ(90) - tego nie będzie na kolokwium

42 = 2 * 21 = 2 * 3 * 7

Sposób I - φ(42) = 42 * (1 - 1/2) * (1 - 1/3) * (1 - 1/7) = 42 * 1/2 * 2/3 * 6/7 = 42 * 12/42 = 12
Sposób II - φ(42) = (2 - 1)2^1-1 * (3 - 1)3^1-1 * (7 - 1)7^1-1 = 1 * 1 * 2 * 1 * 6 * 1 = 12

56 = 2 * 28 = 2 * 2 * 14 = 2 * 2 * 2 * 7

φ(56) = 56 * (1- 1/2) * (1 - 1/7) = 56 * 1/2 * 6/7 = 56 * 6/14 = 24
φ(56) = (2 - 1)2^3-1 * (7 - 1)7^1-1 = 1 * 4 * 6 * 1 = 24

75 = 3 * 25 = 3 * 5 * 5

φ(75) = 75 * (1 - 1/3) * (1 - 1/5) = 75 * 2/3 * 4/5 = 75 * 8/15 = 40
φ(75) = (3 - 1)3^1-1 * (5 - 1)5^2-1 = 2 * 1 * 4 * 5 = 40

90 = 2 * 45 = 2 * 3 * 15 = 2 * 3 * 3 * 5

φ(90) = 90 * (1 - 1/2) * (1 - 1/3) * (1 - 1/5) = 90 * 1/2 * 2/3 * 4/5 = 90 * 8/30 = 24
φ(90) = (2 - 1)2^1-1 * (3 - 1)3^2-1 * (5 - 1)5^1-1 = 1 * 1 * 2 * 3 * 4 * 1 = 24

---