Osaisiko joku kertoa, miten tällainen tehtävä ratkaistaan?
Luku 19^18 korotetaan potenssiin 17^16. Mitkä ovat näin saadun luvun kuusi viimeistä numeroa 7-kantaisessa lukujärjestelmässä?
Ja, please, laskuvaiheet näkyviin, ei pelkkää tietokoneohjelmien tai laskimien antamaa lopputulosta.
Luku 19^18 korotetaan potenssiin 17^16. Mitkä ovat näin saadun luvun kuusi viimeistä numeroa 7-kantaisessa lukujärjestelmässä?
Ja, please, laskuvaiheet näkyviin, ei pelkkää tietokoneohjelmien tai laskimien antamaa lopputulosta.
Vastaukset 7
Vanhimmat
Vinkki. Tuossa pitää laskea (19^18)^(17^16) mod 7^6. Vaikuttaa vähän työläältä vääntää käsin. Tietokoneellakin joutuu vähän miettimään laskujärjestystä, ettei tule liian isoja lukuja.
Tosiaan kuten onkin jo mainittu, niin täytyy laskea (19^18)^(17^16) mod 7^6. Tähän voi käyttää Eulerin lausetta, jonka mukaan a^(phi(n)) = 1 mod n, kun syt(a,n)=1.
Nyt phi(7^6) = 7^6-7^5 = 2*3*7^5 = 100842
---------------------------------------------------
Koska a^(b k*c) = a^b * (a^c)^k = a^b, jos a^c=1 mod n, niin eksponentista voidaan erottaa kaikki c:n monikerrat ja jäljelle jää vain jakojäännös jaettaessa c:llä (eli phi(7^6):lla tässä tapauksessa). Siis:
---------------------------------------------------
A = (19^18)^(17^16) = 19 ^(18*17^16) = 19^(18*17^16 mod 100842) mod 7^6.
Tuon eksponentti on jo laskettavissa laskimella (ota modulo aina 17:lla kertomisen jälkeen, niin ei kasva liian isoksi) ja siitä tulee 89910. Siis
A = 19^89910 = 19^(2 * 3 ^ 5 * 5 * 37) = 19^2 * (19^3)^5 * 19^5 * 19^37 mod 7^6
Tämänkin voi nyt laskea osissa ja ottamassa aina välissä modulon. Tuon ison exponentin 37 voi vielä tehdä nopealla potenssiinkorotuksella eli oikeassa järjestyksessä (37:n binääriesityksen mukaisesti) korotat toiseen tai kerrot 19:lla. Tästä kuitenkin tulee, että
A = 361 * 34299 * 5470 * 83025 = 110428.
---
Tämä kun nyt muutetaan 7 järjestelmään saadaan ne kuusi viimeistä numeroa eli (jos ei virheitä tullut, niin) 636643.
Eipä taida Nokikanan lasku olla ihan kunnossa. Virhe näyttäisi tulevan loppuvaiheessa.
Voisiko Nokikana esim. täsmentää, minkä laskuopin mukaan
19^(2 * 3 ^ 5 * 5 * 37) = 19^2 * (19^3)^5 * 19^5 * 19^37
?
Taetaa olla sitä Nokikana-laskentoo.
Joo, sori, nyt tuli pahemman luokan virhe tuossa potenssin laskusäännössä.... ;()
Ei kai siinä auta sitten muu kuin laskea tuo 19^89910 mod 7^6 siltäsenään. Siinä voi käyttää sitä nopeaa potenssiinkorotusta, niin ei se niin kovin pitkä lasku ole.
(89910_10 = 10101111100110110_2, joten kuusitoista kierrosta toiseen korotusta taitaa tulla.)
https://en.wikipedia.org/wiki/Exponentiation_by_squaring
Saadaan 56253_10 eli seitsemän-järjestelmässä 323001_7.
No sitähän se :D