| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
vinko
Forumaš(ica)
Pridružen/a: 26. 08. 2006. (23:08:00)
Postovi: (1A8)16
Spol: 
Lokacija: PMF-MO 214
|
 Postano: 15:23 pet, 10. 11. 2006 Naslov: Nađite zadnje dvije znamenke broja 3^400 i 7^279. |
    |
|
|
Rješenje toga zadatka možete vidjeti u skripti prof.Dujelle ( http://web.math.hr/~duje/utb/utblink.pdf ), Primjer 2.5.
Zadatak smo mogli riješiti i da izračunamo Phi(100)=40, te stoga zaključiti i da je 3^40 = 1 = 3^400 (mod 100).
Međutim, pitanje na vježbama je bilo što da broj 3^400 (mod 25) ili 3^400 (mod 4) nije bio 1. Stoga promotrimo drugi zadatak:
Odredite zadnje dvije znamenke broja 7^279.
Dakle, traži se 7^279 mod 100. Budući je gcd(7,100)=1, (i znamo rastaviti 100 na proste faktore), možemo primjeniti Eulerov teorem (u protivnom bi takav zadatak rješavali binarnim potenciranjem i eventualno primjenili algoritam Montgomerijevog potenciranja (da je modul kompliciraniji) što je opisano u skripti prof. Dujelle - Teorija brojeva u kriptografiji http://web.math.hr/~duje/tbkript/tbkriptlink.pdf , poglavlje 2.5).
Zbog 100=4*25, izračunamo phi(4)=2 i phi(25)=20.
7^279 = 7^(279 mod phi(4)) (mod 4) = 7^1 (mod 4) = 3 (mod 4)
7^279 = 7^(279 mod phi(25)) (mod 25) = 7^19 (mod 25) = 18 (mod 25)
Promotrimo sustav kongruencija: x=3 (mod 4) i x=18 (mod 25). Pomoću Kineskog teorema lako dobijemo x=43 (mod 100). Pa zaključujemo da su zadnje dvije znamenke broja 7^279 jednake 43.
P.S. Računanje 7^19 (mod 25)
Možemo uočiti da je 19=-1 (mod phi(25)=20), pa 7^19 (mod 25) shvatiti kao 7^-1 (mod 25), te to izračunati Euklidovim algoritmom tražeći rješenje kongruencije 7x=1 (mod 25) i dobiti rješenje 18.
Rješenje toga zadatka možete vidjeti u skripti prof.Dujelle ( http://web.math.hr/~duje/utb/utblink.pdf ), Primjer 2.5.
Zadatak smo mogli riješiti i da izračunamo Phi(100)=40, te stoga zaključiti i da je 3^40 = 1 = 3^400 (mod 100).
Međutim, pitanje na vježbama je bilo što da broj 3^400 (mod 25) ili 3^400 (mod 4) nije bio 1. Stoga promotrimo drugi zadatak:
Odredite zadnje dvije znamenke broja 7^279.
Dakle, traži se 7^279 mod 100. Budući je gcd(7,100)=1, (i znamo rastaviti 100 na proste faktore), možemo primjeniti Eulerov teorem (u protivnom bi takav zadatak rješavali binarnim potenciranjem i eventualno primjenili algoritam Montgomerijevog potenciranja (da je modul kompliciraniji) što je opisano u skripti prof. Dujelle - Teorija brojeva u kriptografiji http://web.math.hr/~duje/tbkript/tbkriptlink.pdf , poglavlje 2.5).
Zbog 100=4*25, izračunamo phi(4)=2 i phi(25)=20.
7^279 = 7^(279 mod phi(4)) (mod 4) = 7^1 (mod 4) = 3 (mod 4)
7^279 = 7^(279 mod phi(25)) (mod 25) = 7^19 (mod 25) = 18 (mod 25)
Promotrimo sustav kongruencija: x=3 (mod 4) i x=18 (mod 25). Pomoću Kineskog teorema lako dobijemo x=43 (mod 100). Pa zaključujemo da su zadnje dvije znamenke broja 7^279 jednake 43.
P.S. Računanje 7^19 (mod 25)
Možemo uočiti da je 19=-1 (mod phi(25)=20), pa 7^19 (mod 25) shvatiti kao 7^-1 (mod 25), te to izračunati Euklidovim algoritmom tražeći rješenje kongruencije 7x=1 (mod 25) i dobiti rješenje 18.
|
|
| [Vrh] |
|
vinko
Forumaš(ica)
Pridružen/a: 26. 08. 2006. (23:08:00)
Postovi: (1A8)16
Spol:
Lokacija: PMF-MO 214
|
| Postano: 21:54 pet, 10. 11. 2006 Naslov: Re: Nađite zadnje dvije znamenke broja 3^400 i 7^279. |
|
|
|
[quote="vinko"]
P.S. Računanje 7^19 (mod 25)
Možemo uočiti da je 19=-1 (mod phi(25)=20), pa 7^19 (mod 25) shvatiti kao 7^-1 (mod 25), te to izračunati Euklidovim algoritmom tražeći rješenje kongruencije 7x=1 (mod 25) i dobiti rješenje 18.[/quote]
Računanje 7^279 (mod 100)
Sada kada ponovo gledam ovaj zadatak, vidim da je 279=39=-1 (mod 40=phi(100)), pa smo umjesto 7^279 mod 100 mogli racunati 7^-1 mod 100, odnosno naci rjesenje kongruencije 7x=1 (mod 100).
I to je dakako rjesenje zadatka (naravno isto broj 43), ali onda ne bi imali pricu s kineskim teoremom.
| vinko (napisa): |
P.S. Računanje 7^19 (mod 25)
Možemo uočiti da je 19=-1 (mod phi(25)=20), pa 7^19 (mod 25) shvatiti kao 7^-1 (mod 25), te to izračunati Euklidovim algoritmom tražeći rješenje kongruencije 7x=1 (mod 25) i dobiti rješenje 18. |
Računanje 7^279 (mod 100)
Sada kada ponovo gledam ovaj zadatak, vidim da je 279=39=-1 (mod 40=phi(100)), pa smo umjesto 7^279 mod 100 mogli racunati 7^-1 mod 100, odnosno naci rjesenje kongruencije 7x=1 (mod 100).
I to je dakako rjesenje zadatka (naravno isto broj 43), ali onda ne bi imali pricu s kineskim teoremom.
|
|
| [Vrh] |
|
ta2a
Forumaš(ica)
Pridružen/a: 01. 09. 2004. (12:59:54)
Postovi: (B4)16
Spol: 
Lokacija: zg
|
|
| [Vrh] |
|
vinko
Forumaš(ica)
Pridružen/a: 26. 08. 2006. (23:08:00)
Postovi: (1A8)16
Spol:
Lokacija: PMF-MO 214
|
| Postano: 16:07 pon, 15. 1. 2007 Naslov: Re: Nađite zadnje dvije znamenke broja 3^400 i 7^279. |
|
|
|
[quote="ta2a"]
a šta da smo dobili 7^-2(mod 25)? jel bi onda mogli računat Euklidovim algoritmom iz 7x=2(mod25) ? :???:[/quote]
Ne! To nije dobro zaključivanje.
7x=2(mod 25) ima rješenje x=11.
Međutim 7^18=7^-2(mod 25) ima rješenje 24. To smo mogli dobiti npr. tako da uočimo 7^-2=(7^-1)^2 ili = (7^2)^-1
Dakle, na prvi način bi izračunali 7x=1 (mod 25), dobili rješenje 18, pa kvadrirali i dobili 324, pa još mod 25, te dobijemo 24.
Na drugi bi način rješavali 7^2*x=1(mod 25), odnosno kad reduciramo mod 25 imamo 24x=1(mod 25) i dobili rješenje ponovo 24.
| ta2a (napisa): |
a šta da smo dobili 7^-2(mod 25)? jel bi onda mogli računat Euklidovim algoritmom iz 7x=2(mod25) ?  |
Ne! To nije dobro zaključivanje.
7x=2(mod 25) ima rješenje x=11.
Međutim 7^18=7^-2(mod 25) ima rješenje 24. To smo mogli dobiti npr. tako da uočimo 7^-2=(7^-1)^2 ili = (7^2)^-1
Dakle, na prvi način bi izračunali 7x=1 (mod 25), dobili rješenje 18, pa kvadrirali i dobili 324, pa još mod 25, te dobijemo 24.
Na drugi bi način rješavali 7^2*x=1(mod 25), odnosno kad reduciramo mod 25 imamo 24x=1(mod 25) i dobili rješenje ponovo 24.
Zadnja promjena: vinko; 19:34 pon, 15. 1. 2007; ukupno mijenjano 1 put.
|
|
| [Vrh] |
|
vinko
Forumaš(ica)
Pridružen/a: 26. 08. 2006. (23:08:00)
Postovi: (1A8)16
Spol:
Lokacija: PMF-MO 214
|
|
| [Vrh] |
|
|
