|
[quote="niki"]Pozdrav !
Da li mi netko može reći kako bi riješio ovaj zadatak:
Odredite koji ostatak daje broj:
250^239 + 2^19 * 15^18 pri djeljenju sa 31.
Pronašao sam na internetu riješenje i postupak.[/quote]
Internet je divna stvar, ali smijem li pitati zašto nisi pogledao u bilješke s vježbi?
[quote] Jedan dio postupka
sam skužio, ali ne mogu skužiti cijeli.[/quote]
Bilo bi također jako lijepo (za ubuduće) da napišeš koji dio postupka si skužio.
[quote] Da li bi netko mogao izračunati taj zadatak (kompletno objasniti postupak ) i staviti ga na internet.
Pod ovim "kompletno" mislim na sva objašnjenja koja se vežu na taj zadatak.[/quote]
Da vidimo.
Treba odrediti ostatak pri dijeljenju broja a+b s 31 ( a:=250^239 , b:=2^19*15^18 ). Teorija kongruencijâ nam kaže da ako s a',b' označimo ostatke pri dijeljenju a,b s 31 , rješenje mogu dobiti kao (a'+b')mod31 . Dakle, odredimo a' i b' .
a'=250^239mod31 . Opet, po teoremu po kojem kongruencije čuvaju množenje, a'=(250*250*...*250)mod31=(250'*250'*...*250')mod31=250'^239mod31
(s 250' je označen ostatak pri dijeljenju 250 s 31 : ). 250'=250mod31 . 3*8=24 , pa je 31*8=248=250-2 , odnosno 250=31*8+2 -- 250'=2 . So, a'=2^239mod31 .
Primijetimo da 239 ne možemo na isti način zamijeniti s 239'=239mod31 ("reducirati ga modulo 31 "), jer je u eksponentu, a kongruencije općenito ne čuvaju potenciranje: recimo, iako je 4mod3=1 , 2^4mod3 nije 2^1mod5 . Jer je 31 prost, možemo doduše iskoristiti mali Fermatov teorem, koji kaže da je onda 2^30mod31=1 , pa vidimo da možemo reducirati eksponent modulo _30_. No u ovom zadatku možemo i modulo puno manje: 2^5 je već 32 , dakle 1 modulo 31 . Što nam to govori? 2^(5k)=(2^5)^k=32^k , a vidjeli smo da bazu možemo reducirati, pa to modulo 31 iznosi 1^k , odnosno 1 .
Dakle, 2^(5k+l)=(2^5)^k*2^l=32^k*2^l . 2^(5k+l)mod31=((32^k)mod31*2^lmod31)mod31=(1*2^lmod31)mod31=2^lmod31 . Odnosno, dovoljno nam je reducirati eksponent modulo _5_ ( l može biti njegov ostatak pri dijeljenju s 5 ). To je previše pisanja "mod31" :-) , pa se često kraće piše samo lanac kongruencijâ (i jednakostî), s tim da se na kraju naznači modulo. Dakle
(250^239==2^239==2^(239mod5)==2^4=16)(mod31) . Odnosno a'=16 .
Za b' , primijetimo da također možemo lukavo dobiti bazu koju možemo lako potencirati (gore 1 , ovdje -1 ) -- ako pomnožimo 2 i 15 , dobijemo 30 , što je -1 modulo 31 :
(2^19*15^18=2*2^18*15^18=2*(2*15)^18=2*30^18==2*(-1)^18=2*1=2)(mod31) . Odnosno b'=2 .
I sad, naš rezultat je a'+b' mod 31 , odnosno 16+2=18 .
HTH,
| niki (napisa): | Pozdrav !
Da li mi netko može reći kako bi riješio ovaj zadatak:
Odredite koji ostatak daje broj:
250^239 + 2^19 * 15^18 pri djeljenju sa 31.
Pronašao sam na internetu riješenje i postupak. |
Internet je divna stvar, ali smijem li pitati zašto nisi pogledao u bilješke s vježbi?
| Citat: | Jedan dio postupka
sam skužio, ali ne mogu skužiti cijeli. |
Bilo bi također jako lijepo (za ubuduće) da napišeš koji dio postupka si skužio.
| Citat: | Da li bi netko mogao izračunati taj zadatak (kompletno objasniti postupak ) i staviti ga na internet.
Pod ovim "kompletno" mislim na sva objašnjenja koja se vežu na taj zadatak. |
Da vidimo.
Treba odrediti ostatak pri dijeljenju broja a+b s 31 ( a:=250^239 , b:=2^19*15^18 ). Teorija kongruencijâ nam kaže da ako s a',b' označimo ostatke pri dijeljenju a,b s 31 , rješenje mogu dobiti kao (a'+b')mod31 . Dakle, odredimo a' i b' .
a'=250^239mod31 . Opet, po teoremu po kojem kongruencije čuvaju množenje, a'=(250*250*...*250)mod31=(250'*250'*...*250')mod31=250'^239mod31
(s 250' je označen ostatak pri dijeljenju 250 s 31 : ). 250'=250mod31 . 3*8=24 , pa je 31*8=248=250-2 , odnosno 250=31*8+2 – 250'=2 . So, a'=2^239mod31 .
Primijetimo da 239 ne možemo na isti način zamijeniti s 239'=239mod31 ("reducirati ga modulo 31 "), jer je u eksponentu, a kongruencije općenito ne čuvaju potenciranje: recimo, iako je 4mod3=1 , 2^4mod3 nije 2^1mod5 . Jer je 31 prost, možemo doduše iskoristiti mali Fermatov teorem, koji kaže da je onda 2^30mod31=1 , pa vidimo da možemo reducirati eksponent modulo _30_. No u ovom zadatku možemo i modulo puno manje: 2^5 je već 32 , dakle 1 modulo 31 . Što nam to govori? 2^(5k)=(2^5)^k=32^k , a vidjeli smo da bazu možemo reducirati, pa to modulo 31 iznosi 1^k , odnosno 1 .
Dakle, 2^(5k+l)=(2^5)^k*2^l=32^k*2^l . 2^(5k+l)mod31=((32^k)mod31*2^lmod31)mod31=(1*2^lmod31)mod31=2^lmod31 . Odnosno, dovoljno nam je reducirati eksponent modulo _5_ ( l može biti njegov ostatak pri dijeljenju s 5 ). To je previše pisanja "mod31"  , pa se često kraće piše samo lanac kongruencijâ (i jednakostî), s tim da se na kraju naznači modulo. Dakle
(250^239==2^239==2^(239mod5)==2^4=16)(mod31) . Odnosno a'=16 .
Za b' , primijetimo da također možemo lukavo dobiti bazu koju možemo lako potencirati (gore 1 , ovdje -1 ) – ako pomnožimo 2 i 15 , dobijemo 30 , što je -1 modulo 31 :
(2^19*15^18=2*2^18*15^18=2*(2*15)^18=2*30^18==2*(-1)^18=2*1=2)(mod31) . Odnosno b'=2 .
I sad, naš rezultat je a'+b' mod 31 , odnosno 16+2=18 .
HTH,
|
