#1 31. 12. 2012 14:57
- speedex505
- Zelenáč
- Příspěvky: 11
- Škola: CVUT FIT
- Pozice: student
- Reputace: 0
Kongruence
Zdravim, neví někdo jak se počítají tyhle dva příklady?
Na ten první by se mela použít malá Fernatova věta a ten druhy vubec nevím.
Offline
#3 01. 01. 2013 16:42 — Editoval speedex505 (01. 01. 2013 16:51)
- speedex505
- Zelenáč
- Příspěvky: 11
- Škola: CVUT FIT
- Pozice: student
- Reputace: 0
Re: Kongruence
Já to nakonec počítal takto:
135^135(mod17) = 16^135(mod17)
16^(16*8)*16^{\7 } = 1^8*16^7
nakonec tedy staci zjistit 16^7 modulo 17 a to jde jeste rozkladat.
Ale jeste mame řešit když v tom modulu není prvočíslo což by se melo dělat eulerovou funkcí.
A to druhé se řeší přes rozšířený euklidův algoritmus a jeden vzorec. Ale díky za pomoc :)
Offline
#5 01. 01. 2013 17:09
- speedex505
- Zelenáč
- Příspěvky: 11
- Škola: CVUT FIT
- Pozice: student
- Reputace: 0
Re: Kongruence
Netušim jaký má název, ale když se označí ten příklad takto:
ax=b(mod n)
Pak je báze řešení {A*(b/gcd(a,n) + k*(n/gcd(a,n)}, kde k je z celých čísel a gcd je nejvetší společný dělitel.
A zjistíme kdyz si napíšem A*a + B*n = gcd(a,n)
Offline