Zadania - mat. dyskretna

[kona]

Witam
czy ktos jest w stanie rozwiązać mi te zadania? niestety, jestem z tego kompletnie zielony i to nie moja branża.
Bardzo dziękuję za pomoc.

1. Oblicz NWD(133; 84), NWD(221; 169), NWD(97; 41).
2. Za pomoc¡ rozszerzonego algorytmu Euklidesa znajd¹ x; y speªniaj¡ce
równanie xm+yn = NWD(m; n) dla par liczb m; n z poprzedniego zadania.
3. Niech fn b¦dzie ci¡giem Fibonacciego tzn f0 = f1 = 1 i fn+2 = fn+1+fn.
Poka», »e NWD(fn+1; fn) = 1 dla ka»dego n. Wsk. Poka», »e fn¡1 jest reszt¡
z dzielenia fn+1 przez fn.
4. Niech (xnxn¡1 : : : x1x0) b¦dzie reprezentacj¡ liczby x w ukªadzie dziesi¦tnym.
Poka», »e xmod9 = (xn + ¢ ¢ ¢ + x0)mod9.
5. Wykonaj dziaªania ¡45mod7, 45 ¢ 34mod7, 734mod5, 6125mod8.
6. Uªó» tabelk¦ mno»enia dla reszt z dzielenia przez 5 i korzystaj¡c z niej
znajd¹ elementy odwrotne do 2 i 3 (tzn. (2 ¢ x)mod5 = 1, (3 ¢ x)mod5 = 1).
7. Oblicz '(28); '(36); '(3528). Oblicz '(2k) dla kolejnych k naturalnych.
Funkcja ' jest funkcj¡ Eulera, która liczy ile jest liczb naturalnych wzgl¦dnie
pierwszych z zadan¡.
8. Za pomoc¡ algorytmu RSA zaprezentowanego na wykªadzie zaszyfruj (i
odszyfruj) wyraz BAZA.

[irena]

1.
a)
\(133=84+49\\84=49+35\\49=35+14\\35=2\cdot14+7\\14=2\cdot7+0\\NWD(133,\ 84)=7\)

[irena]

b)
\(221=169+52\\169=3\cdot52+13\\52=4\cdot13+0\\NWD(221,\ 169)=13\)

[irena]

c)
\(97=2\cdot41+15\\41=2\cdot15+11\\15=11+4\\11=2\cdot4+3\\4=3+1\\3=3\cdot1+0\\NWD(97,\ 41)=1\)

[ewelawwy]

7.
28=2*2*7
\('(28)=28\cdot (1-\frac 12)\cdot (1-\frac 17)=28\cdot \frac 12 \cdot \frac 67 = 12\)
36=2*2*3*3
\('(36)=36\cdot(1-\frac 12)\cdot (1-\frac 13)=36\cdot \frac 12\cdot \frac 23=12\)
3528=2*2*2*3*3*7*7
\('(3528)=3528\cdot (\frac 12)\cdot (\frac 23)\cdot (\frac 67)=3528\cdot \frac 12\cdot \frac 23\cdot \frac 67=1008\)

[irena]

3.
Treść trochę nieczytelna. Ale spróbuję:
Masz pokazać, że:
\(NWD(f_{n+1},\ f_n)=1\)

Niech:
\(NWD(f_{n+1};\ f_n)=d\)

Wtedy: \(d|\ (f_{n+1}-f_n)=f_{n-1}\ \Rightarrow \ d|f_{n-1}\ \Rightarrow \ d|\ (f_n-f_{n-1})=f_{n-2}\ \Rightarrow \ ...\ \Rightarrow \ d|f_1=1\ \Rightarrow d=1\)

[irena]

2.
a)
\(7=x\cdot84+x\cdot133\)

\(7=35-2\cdot14=35-2(49-35)=3\cdot35-2\cdot49=3(84-49)-2\cdot49=3\cdot84-5\cdot49=\\=3\cdot84-5(133-84)=3\cdot84-5\cdot133+5\cdot84=\\8\cdot84-5\cdot133\)

\(7=8\cdot84-5\cdot133\)

[irena]

b)
\(13=169-3\cdot52=169-3(221-169)=4\cdot169-3\cdot221\)

\(13=4\cdot169-3\cdot221\)

[irena]

c)
\(1=4-3=4-(11-2\cdot4)=3\cdot4-11=3(15-11)-11=3\cdot15-4\cdot11=3\cdot15-4(41-2\cdot15)=\\=11\cdot15-4\cdot41=11(97-2\cdot41)-4\cdot41=\\=11\cdot97-26\cdot41\)

\(1=11\cdot97-26\cdot41\)

[irena]

4. i 5. nieczytelne
6.
\(2\cdot3=1_{(mod\ 5)}\)
\(3\cdot2=1_{(mod\ 5)}\)

[kona]

6. Wykonaj działania -45mod7, 45 * 34mod7, 7^34mod5, 6^125mod8

7. Oblicz omega(28); omega(36); omega(3528). Oblicz omega(2^k) dla kolejnych k naturalnych.
Funkcja omega jest funkcją Eulera, która liczy ile jest liczb naturalnych względnie
pierwszych z zadaną.

[irena]

6.
\(-45_{(mod7)}=4_{(mod7)}\)

\(45\cdot34_{(mod7)}=3\cdot(-1)_{mod7)}=-3_{(mod7)}=4_{(mod7)}\)

\(7^{34}_{(mod5)}=2^{34}_{(mod5)}=4^{17}_{(mod5)}=(-1)^{17}_{(mod5)}=-1_{(mod5)}=4_{(mod5)}\)

\(6^{125}_{(mod8)}=(3^{125}\cdot2^{125})_{(mod8)}=(2^3\cdot2^{122}\cdot3^{125})_{(mod8)}=8\cdot(2^{122}\cdot3^{125})_{(mod8)}=0_{(mod8)}\)

[kona]

tresci

[ewelawwy]

7 masz wyżej zrobione

[irena]

4.
Nie wiem, czy dobrze Ci zapiszę, ale oznacza to, że:
\(x=x_n\cdot10^n+x_{n-1}\cdot10^{n-1}+...+x_1\cdot10+x_0\cdot1\\10_{(mod9)}=1_{(mod9)}\\10^k_{(mod9)}=1_{(mod9)}\ \ dla\ \ k\in\ N\\x_{(mod9)}=(x_n\cdot1+x_{n-1}\cdot1+...+x_1\cdot1+x_0\cdot1)_{(mod9)}=(x_n+x_{n-1}+...+x_1+x_0)_{(mod9)}\)