Luku 2^47 jaetaan luvulla 23 ja tästä pitäisi laskea jakojäännös. Miten tämä käytännössä onnistuu? Lisäksi luku 13^674503 pitäis jakaa luvulla 37 ja laskea siitä edelleen jakojäännös. Miten nämä hoituvat? Ensimmäinen vielä menee pienellä säädöllä mutta toinen tuottaa jo liikaa ongelmia
Jakojäännös
jakojäännöksiä lasketaan
1820
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 1
Vanhimmat
2^47=2*2^46=2*(2^23)^2
Fermat pikkulause sanoo, että
a^p=a modulo p, kun p alkuluku (a^(p-1)=1 kun p alkuluku ja a ei jaollinen p). 23 on alkuluku.
Joten 2^47=2*(2^23)^2=2*2^2=8 modulo 23.
Jakojäännös on siis 8.
Vastaavasti jälkimmäinen (37 alkuluku)
13^36=1 modulo 37
13^674503=13^(36*18736 7)=(13^36)^18736*13^7=1^18736*13^7=13^7 modulo 37
13^7=62748517=32 modulo 37
Jakojäännös on 32