Matematyka dyskretna, rekurencje, tw. Eulera, kombinatoryka arcteryx98: Witam. Mam wielką prośbę. Jutro mam kolokwium, ale nie rozumiem poszczególnych zadań z matematyki dyskretnej. Czy ktoś mógłby je rozwiązać oraz mi wytłumaczyć o co w tym chodzi po kolei. Odpowiedzi sa podane nizej 1.Ile ciągów ternarnych (tj. złożonych z cyfr 0,1,2) spełnia tę własność, że po żadnej jedynce nie wystepuje ani 2 ani0? Wyprowadz odpowiednie rownanie rekurencyjne z warunkami poczatkowymi i rozwiaz je Odpowiedz: sn = 2ⁿ+1 −1 2.Ile jest roznych liczb pieciocyfrowych niepodzielnych przez zadna z liczb 6,21,35? Odp: 71 142 3. Ile jest roznych liczb szesciocyfrowych zapisanych w systemie osiemnastkowym takich, ze a) wszystkie cygry sa rozne i liczba jest parzysta b) cyfry sa rozne i iloczyn liczb trzeciej i czwartej jest podzielny przez 3? Odp a) 6 333 600 b) 7 442 870 4)Oblicz a) fi(868 175) TW Eulera b) 23⁸88 111 mod 72 odp a) 528 000 b) 71

wredulus_pospolitus: 1. skoro mamy mieć spełniony warunek że po żadnej '1' nie może być ani 0 ani 2 ... to znaczy, że musi być '1' Tak więc, rozpatrujemy wszystkie takie ciągi które mają do pewnego momentu 0 lub 2 (w dowolnej kolejności), ale jak już się trafi '1' to później są same '1'

wredulus_pospolitus: 2. Tyle samo co wszystkie pięciocyfrówki minus te które są podzielne przez 6, 21 lub 35

wredulus_pospolitus: 3. A tutaj z czym masz problem ?

wredulus_pospolitus: 4. no i tutaj w czym problem

chichi: Co to jest za zapis: 23⁸88 111 mod 72?

Mila: 1) n=1 0,1,2− 3 ciągi a₁=3 n=2 (0,0),(1,1), (2,2),(0,1),(0,2), (2,0) (2,1)− 7ciągów a₂=7 a_n=2a_n−1+1 Może? Wtedy: x−2=0 x=2 2)Postać jawna: a_n=A*2ⁿ+B a₁=3=A*2¹+B a₂=7=A*2²+B 2A+B=3 i 4A+B=7 A=2 i B=−1 a_n=2*2ⁿ−1⇔ a_n=2ⁿ⁺¹−1 Może aktualny student z forum sprawdzi.

arcteryx98: Przepraszam, w 4b ma być ta 8 do potęgi zwykłą liczbą, a konkretniej 4) b)23888 111 mod 72

chichi: Wtedy nie prawda, że odp. to 71

arcteryx98: Od tej nauki troszkę pomieszałem sprawy, ma być 23⁸88 111 mod 72

arcteryx98: W sensie do potęgi trzy ósemki i trzy jedynki, nie wiem dlaczego źle mi się zapisuje

Mila: 23⁸⁸⁸¹¹¹ mod72 tak? Czyli podstawa potęgi to 23 a wykładnik : 888111 Piszesz znak do potęgi i po tym znaku {888111}

chichi: Teraz wynik się zgadza

Mila: 4) a) φ(868175) ? ma być ?

Mila: Funkcja Eulera− tocjent 868175=5²*7*11²*41

	1		1		1		1
1) φ(868175)=868175*(1−		)*(1−		)*(1−		)*(1−		)=
	5		7		11		41

	4		6		10		40
=52*7*112*41*		*		*		*		=528000
	5		7		11		41

2) 72=2³*3²

	1		1
φ(72)=72*(1−		)*(1−		)=24
	2		3

23²⁴=1(mod 72) dalej sam?

arcteryx98: Tak, dokladnie 23⁸88111 Mam pytanie, skad się wzięło 72*(1−1/2) * (1−1/3) ? Oraz 23²4 = 1(mod72)?

Mila: POczytaj w notatkach o funkcji Eulera. 23 jest względnie pierwsze z liczbą 72 23⊥72 1) Jeżeli p jest liczbą pierwszą natomiast a jest taką liczbą całkowitą, że a i p są względnie pierwsze to a^p−1=1(mod p) Przykład: NWD(6,5)=1 6⁴=1(mod5) 2) NWD(23,72)=1 23^φ(72)=1 (mod n) Jest wzór na obliczanie wartości funkcji φ.

arcteryx98: Dziękuje. Mam jeszcze jedno zadanie nad którym się borykam 7. Czy któraś z poniższych par może być kluczem prywatnym w algorytmie RSA? Odpowiedź uzasadnij. W przypadku odpowiedzi pozytywnej podaj klucz publiczny. (323, 12) (667, 61) Odpowiedź: Pierwsza para nie, nieprawidłowe d. Druga – tak, klucz publiczny (667, 101).

Mila: Tego nie wiem. Może ktoś inny Ci pomoże.

Mila: 1) 90000:6=15000 4285 podzielnych przez 21 2572 podzielnych przez35 NWW(6,21)=42, 2142−podzielnych przez 42 NWW(21,35)=105 , 857 NWW(6,35)=210 NWW(6,21,35)=210 ,428 |A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C| 90000−(15000+4285+2572−2142−857−428+428)=71142

Adamm: @Mila nie wiem jak mam sprawdzać skoro Ty nie piszesz oryginalnych podpunktów...

Mila: Do Adamm. Rzeczywiście nie napisałam którego zadania dotyczy wpis. 18:20 to propozycja rozwiązania zadania 1)

Min. Edukacji: Już dawno po kolokwium😂

Mila: Ministrze, tu chodzi o prawdę

Min. Edukacji: Każdy ma swoja prawde