Matemaattisia pähkinöitä
klo 11:54 | 12.12.2007
A. Mikä on luvun 14^427 viimeinen numero?
B. Laske 5^500 (mod 13).
C. Määritä Eukleideen algoritmia käyttäen a^-1 kun a = 103 (kuuluu joukkoon Z_115) ja a = 79 (kuuluu joukkoon Z_249)
D. Luvut n, x = 2(n-1)/3, y = 2(x-1)/3, ja z = 2(y-1)/3 ovat positiivisia kokonaislukuja ja z [size=150:1jx8jjot]=[/size:1jx8jjot] 1 (mod 3). Mikä on pienin mahdollinen luvun n arvo?
Tummennettuihin kohtiin kaivattaisiin erikoismerkkejä.
Jospa tekisit kotitehtäväsi itse...
Oleppa hyvä.
"ℤ" ja "≡".
Tein jo sen verran mihin kykenin. Ei ole vastauksia saatavilla, joten varmistuksia kaipailen. D-kohtaan toki selvennystä muutenkin.
jos vastauksia kaipailet, niin nopeasti pahkaillen ne ovat tassa:
A. viimeinen numero on 4
B. 5^500 (mod 13) = 10
C. ? eukleideen algoritmi on keino jolla voidaan selvittaa kahden kokonaisluvun suurin yhteinen tekija, en ymmarra tehtavaa.
D. pienin n = 160
(aukeaa moduloilla kun lahdetaan kaymaan lapi z.sta)
.,jos kaipaat laskuvaiheita, vastaa ensin omat ratkaisuyrityksesi. taalla ei tehda toisten koulutehtavia.
B. 5^500 (mod 13) = 1
C. jos x=a^{-1} mod b, ax=1 mod b ja ax-1=bc jollain kokonaisluvulla c kun a ja b keskenään jaottomia. Tämä ratkeaa Eukleideen algoritmilla.
Kieltämättä lähestymistapani oli hieman väärä, kiitoksia kuitenkin avusta.
A. 14^n (mod) 10 ==> parittomilla eksponenteilla jakojäännös on 4 (parillisilla 6)
B. 5^2 (mod 13) = -1 ==> 5^500(mod 13) = 1
C. ax-by=1
115x-103y=1
Eukleideen algoritmillä x=43, y= 48
Tämä tehtävä on muuten vielä vähän epäselvä. Mitä esim. tuo joukko Z(115) tarkoittaa?
Luulisin, että tässä Z(n) tarkoittaa n:n muodostamaa jäännösluokkaa {0, 1, 2, ..., n-1} ja varsinaisessa tehtävässä oikeastaan pyydetään ratkaisemaan kongruenssi
ax ≡ 1 (mod n)
a^(-1) on siis alkion a käänteisalkio joukossa Z(n). Tässä tapauksessa käänteisalkio lienee olemassa (ja kongruenssilla siten ratkaisu), sillä äkkiseltään näyttäisi, että syt(a,n) = 1 molemmissa esittämissäsi tapauksissa.
Käänteisalkion saat ratkaistua Eukleideen algoritmilla, kun kuljet saman prosessin takaisinpäin (eli etsit kokonaisluvut u,v siten, että syt(a,n) = 1 = au + vn). Suoraan kongruenssin määritelmästä seuraa, että
1 = au + vn ≡ au (mod n),
joten u = a^(-1)