Keresés


Toplista

Toplista
  • betöltés...

Magántanár kereső

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

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
`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