Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!
Moduláris hatványozás
kaatikaa
kérdése
1041
Adjon meg olyan 10000-nél nagyobb pozitív egész számot, melynek
a, 11-dik hatványa 4 maradékot ad 91-gyel osztva;
b, 17-dik hatványa 3 maradékot ad 143-mal osztva!
A tananyagban sajnos csak olyan van, ahol a maradékot kell keresni. Úgyhogy ha valaki tudná, akkor legyen szíves elmagyarázni, köszönöm!
Jelenleg 1 felhasználó nézi ezt a kérdést.
kongurencia, moduláris, hatványozás, Matematika
0
Felsőoktatás / Matematika
Válaszok
1
bongolo{ }
megoldása
`x^11 ≡ 4\ ("mod " 91)`
Tudjuk, hogy `91=7*13`, tehát ezek is igazak kell legyenek:
`x^11 ≡ 4\ ("mod " 7)`
`x^11 ≡ 4\ ("mod " 13)`
Nézzük a mod 7-et. A kis Fermat-tétel szerint:
`x^6 ≡ 1\ ("mod "7)`
aminek a négyzete:
`x^12 ≡ 1\ ("mod "7)`
Mivel `x^12 = x·x^11 ≡ x·4\ ("mod "7)`, ezért
`4x ≡ 1\ ("mod "7)`
Ez a lineáris kongruencia megoldható és egy megoldása van (mivel a 7 prím). Ha nagy számok lennének, akkor a kiterjesztett euklideszi algoritmussal lehetne megoldani, de most kevés próbálkozással (`4·2=8=1·7+1`) is kijön, hogy
`x ≡ 2\ ("mod "7)`
Hasonlóképpen a 13-as maradékosztályban:
`x^12 ≡ 1\ ("mod "13)`
ezért
`x^11·x ≡ 4x ≡ 1\ ("mod " 13)`
aminek a megoldása `4·10=3·13+1` miatt:
`x ≡ 10\ ("mod "13)`
Lett tehát ez az egyenletrendszerünk:
`x ≡ 2\ ("mod "7)`
`x ≡ 10\ ("mod "13)`
ami a kínai maradéktétellel megoldható: (2·7-1·13=1, tehát `e_1=-13`. -1·13+2·7=1, tehát `e_2=14`.)
`x≡2·(-13)+10·14=113≡23\ ("mod "7·13)`
Most egyébként egyszerűek a számok, néhány próbálkozással is kijön, hogy `1·13+10=3·7+2` a megoldás a 91-es maradékosztályban.
A 10000-nél nagyobb megoldás lehet mondjuk ez: 91·1000+23
---
A másikat próbáld meg hasonlóan. Én nem próbáltam még, remélem, megy az is így.
1
kaatikaa:
Nagyon szépen köszönöm, sokat segített!
5 éve0