Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

modulo i kongruencija
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Elementarna matematika 1 i 2
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
niki
Gost





PostPostano: 11:11 sub, 27. 11. 2004    Naslov: modulo i kongruencija Citirajte i odgovorite

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. Jedan dio postupka
sam skužio, ali ne mogu skužiti cijeli. 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.
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. Jedan dio postupka
sam skužio, ali ne mogu skužiti cijeli. 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.


[Vrh]
veky
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 09. 12. 2002. (19:59:43)
Postovi: (5B0)16
Sarma = la pohva - posuda
22 = 24 - 2
Lokacija: negdje daleko...

PostPostano: 11:46 sub, 27. 11. 2004    Naslov: Re: modulo i kongruencija Citirajte i odgovorite

[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" Smile , 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,


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
niki
Gost





PostPostano: 14:52 sub, 27. 11. 2004    Naslov: Citirajte i odgovorite

Hvala Veky . Sve sam skužio !
Hvala Veky . Sve sam skužio !


[Vrh]
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Elementarna matematika 1 i 2 Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan