Jak vymyslet vzorec?

Ahoj, prosím o radu. Mám dvě periody jedna je dlouhá 25znaků a druhá perioda je dlouhá 17znaků. Po kolika znacích se sesynchronizují pokud první periodě zbývá do začátku nové periody 17znaků a druhé periodě do začátku nové periody zbývá 8 znaků? Umím to jen vypočítat, když začínají naráz to si spočtu nejmenší společný násobek u offsetu vůbec netuším :(. Dokážu si to i namalovat, ale na velký čísla to nemám šanci vypočítat :-(. Díky moc za radu Jirka

✓   Téma bylo vyřešeno.
Jiří R.

Jiří R.

10. 11. 2016   10:21

5 odpovědí

Tomáš B.
Tomáš B.
08.11.2016 17:50:21

Jirko, protože neuvádíš, o jaké úrovni matematiky mluvíme, nebudu používat konečné okruhy, ale jenom selský rozum.

Sestavím si rovnice podle zadání a upravím je postupně do hezčí podoby, kde bude řešení vidět od pohledu.

17 + 25p = 8 + 17q / +8 25 + 25p = 16 + 17q 25(p + 1) = 17 + 17q - 1 25(p + 1) = 17(q + 1) - 1

Protože perioda 17 je o 8 prvků kratší a 25 - 1 = 8 * 3, musí být koeficient na pravé straně 3 = q + 1.

Pak je jasné, že na levé straně platí p + 1 = 2.

p = 1, q = 2 je tedy řešením.

Kontrola:

první perioda je 17 + 1 * 25 = 42

druhá perioda je 8 + 2 * 17 = 42

Pokud bych chtěl místo takhle jednoduchého příkladu získat obecné řešení, musím to udělat jinak.

Pro periody P a Q (P > Q) se zbývajícími prvky K a L sestavím rovnici na konečném okruhu modulo P.

Řešením je potom (K - L) * Q^-1 (mod P), to spočítáme pomocí rozšířeného Euklidova algoritmu

Kontrola:

q = (17 - 8) * 17^-1 (mod 25) = 9 * 3 = 2

Jiří R.
Jiří R.
08.11.2016 21:47:57

Děkuji moc, budu to používat na velký čísla tak se to pokusím řešit pomocí Euklidova algoritmu.

Jiří R.
Jiří R.
09.11.2016 10:34:26

Ahoj nějak nechápu ten Euklidův algoritmus :( v tý kontrole máš 9 * 3 = 2? Jinak modulo nemam na kalkulačce tak sem se to snažil napsat v c ale nechce mě to vzít tvar vzorce q=(K-L)*Q^-1%P to modulo má být u té -1 v mocnině nebo na celou rovnici požít modulo? Díky za rady :))

Tomáš B.
Tomáš B.
09.11.2016 11:40:17

Modulus platí na celou rovnici, když to rozepíšu:

q = (17 - 8) * 17^-1 (mod 25)

q = 9 * 3 (mod 25)

q = 2 (mod 25)

Jestli to chceš naprogramovat v C, budeš si to muset všechno napsat ručně.

V příloze je kompletní výpočet, tohle musíš převést do C.

Navíc to bude fungovat jen pro případy, kdy jsou P a Q nesoudělné.

Já tam tyhle podmínky mám kontrolované implicitně díky euklidově algoritmu.

Pokud jsou soudělné, musíš zkontrolovat, jestli řešení neexistuje nebo existuje na zkráceném okruhu a pak dopočítat původní řešení.

Na závěr tě asi nepotěším, počkej s tím, až za sebou budeš mít základy algebry.

Diofantické rovnice nejsou jednoduché a potřebuješ na ně cit a trochu pokročilejší matematiku.

Jiří R.
Jiří R.
10.11.2016 10:21:43

Díky moc, stejně to nějak nechápu :D, ale díky za snahu implementuji to cyklama, jen to nebude tak efektivní bohužel.

Pro napsání komentáře se musíte přihlásit.