Kolokvij 20.1.2006.? (zadatak)

[LSSD]

Moze li mi netko reci rijesenje slijedecih zadataka:
1.Dokazite da za k>5 brojevi k, 2k+1,4k+1 nisu svi prosti.
2.Odredite (23/p), za svaki prosti broj p.
Zanima me da li vrijedi:
5^123 daje ostatak 125 pri dijeljenju sa 2501?

_________________
' Zasto jednostavno kad moze i komplicirano?'

[vsego]

Prvi... jedan od tih brojeva je uvijek djeljiv s 3. Raspisi za k=3x/3x+1/3x+2 i dobit ces.

Btw, cini mi se da je moglo komotno pisati i k>3.

_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.

[vinko]

[LSSD]

hvala:)sad me zanima rijesenje slijedeceg zadatka:
naci sve Pitagorine trojke cije su stranice u aritmetickoj progresiji?

_________________
' Zasto jednostavno kad moze i komplicirano?'

[duje]

[vjekovac]

[vjekovac]

Hm da... Iz dujinog rjesenja se vidi kako je lako naci sve takve pravokutne trokute s ne nuzno cjelobrojnim stranicama. Mrvicu sam zakomplicirao...

[vinko]

[Lara]

Evo još jedno pitanje vezano za taj kolokvij:
Odrediti (19/p) za svaki prost broj p.

Kako se rješavaju ovakvi zadatci?

[Lara]

Ups! Upravo sam našla odgovor pod Legendrovi simboli...

[hermione]

[vinko]

Odredite 5^214 (mod 2201).

Danas sam na vjezbama napravio jedan sitan propust kod ovog zadatka.

Naime, iz 2201=31*71 sam promatrao:

5^214 (mod 31) i 5^214 (mod 71),

te po Malom Fermatovom Teoremu zakljucio da je

5^214=5^4 (mod 31) i 5^214=4^4 (mod 71),

pa iz toga po Kineskom teoremu zakljucio 5^214 = 5^4 (mod 2201).

Naime, greska je jer je 5^4 > 31 i 5^4 > 71.

Na taj bi nacin uistinu trebali koristiti Kineski teorem (jer taj broj daje ostatak 5 pri djeljenju sa 31 i ostatak 57 pri djeljenju sa 71).

Tocnije bi bilo da sam rekao:

5^210=1 (mod 31) i 5^210=1 (mod 71), pa je stoga i 5^210=1 (mod 2201).

Odnosno 5^214 = 5^4 = 625 (mod 2201).

[vinko]

Rjesavanje phi(n)=44.

Preporucio bih citateljima da procitaju i temu http://degiorgi.math.hr/forum/viewtopic.php?t=5905

Iz 44 = 2^2 * 11, mozemo zakljuciti da za neparne proste faktore p od n mora vrijediti p-1 dijeli 44.

Buduci su djelitelji od 44 redom 1, 2, 4, 11, 22 i 44, n je oblika 2^a * 3^b * 5^c * 23^d.
Djelitelje 11 i 44 ne moramo promatrati (jer 12 i 45 nisu prosti).

Buduci 4|44, a 8 ne dijeli 44 ==> a=0,1,2 ili 3
Buduci 3 ne dijeli 44 ==> b=0,1
Buduci 5 ne dijeli 44 ==> c=0,1
Buduci 23 ne dijeli 44 ==> d=0,1

Mogli bi na prste provjeriti sve mogucnosti.

Dosta jednostavnije bi bilo to pokusati sistematizirati.

Presutno cu koristiti cinjenice da je phi(a*b)=phi(a)*phi(b) za a i b relativno proste i da su 1 i 2 jedini brojevi za koje je phi(n)=1.

Moglo bi nam pomoci da buduci da 4|44 i 8 ne |44 slijedi na n ima najvise 2 neparna prosta faktora.

Najjednostavnije bi bilo krenuti od najveceg:

23 (d=1). Promotrimo mogucnost c=1: phi(5*23)=4*22=88 > 44, pa dakle c mora biti 0.
Promotrimo slucaj b=1: phi(3*23)=2*22=44. Pa dakle a mora biti 0 ili 1. Dobili smo brojeve 3*23 i 2*3*23
Ostaje nam slucaj b=0: phi(2^a*23)=2^(a-1)*22=44. Pa dakle a mora biti jednak 2. Dobili smo broj 4*23.

Ostaje nam slucaj d=0.

Ako je c=1 imamo...

No mozemo uociti da u preostalim slucajevima vrijedi:

phi(n) <= (uvrstimo najvece moguce vrijednosti za a, b i c) 2^2*2*4=32 < 44, pa mozemo zakljuciti da dalje ne trebamo provjeravati, jer cemo uvijek dobiti broj manji od 44.

Dakle, sva rjesenja su 69, 92 i 138.

[vinko]

Rjesavanje phi(n)=20.

Iz 20 = 2^2 * 5, mozemo zakljuciti da za neparne proste faktore p od n mora vrijediti p-1 dijeli 20.

Buduci su djelitelji od 20 jednaki 1, 2, 4, 5, 10 i 20, n je oblika 2^a * 3^b * 5^c * 11^d.
5 i 20 ne moramo promatrati (jer 6 i 21 nisu prosti).

Buduci 4|20, a 8 ne dijeli 20 ==> a=0,1,2 ili 3
Buduci 3 ne dijeli 20 ==> b=0,1
Buduci 5|20, a 25 ne dijeli 20 ==> c=0,1,2
Buduci 11 ne dijeli 20 ==> d=0,1

Mogli bi na prste provjeriti sve mogucnosti (sto sam i pokusao na vjezbama, cinilo mi se jednostavnije i brze, jer se puno mogucnosti ne moze dogoditi).

Pa ipak, jednostavnije je sistematizirano promatrati.

Presutno cu koristiti cinjenice da je phi(a*b)=phi(a)*phi(b) za a i b relativno proste i da su 1 i 2 jedini brojevi za koje je phi(n)=1.

Kao i u prethodnom zadatku, mozemo zakljuciti da n ima najvise 2 (ovdje treba) razlicita prosta faktora.

Krenimo opet od najveceg.

11 (d=1). Promotrimo mogucnost c>=0: phi(n)>=phi(5*11)=40>20 pa to otpada. Dakle c=0. Ako je b=1 imamo phi(3*11)=20, pa dobijemo brojeve 3*11 i 2*3*11. Ako je b=0 imamo phi(2^a*11)=2^(a-1)*10=20, tj a=2, pa dobijemo broj 2^2*11.

Ostaje slucaj d=0.
Ako je c=2, imamo phi(5^2)=4*5=20, pa mora biti b=0, te dobijemo brojeve 25 i 50.

Ako je c=1, uzmimo prvo b=1, pa imamo phi(5*3)=2*4=8 on ne dijeli 20, pa to otpada. Dakle b=0. Imamo phi(2^a*5)=2^(a-1)*4=20, tj. 2^(a-1)=5, pa i to otpada.

Sveukupno, dobili samo brojeve 25, 33, 44, 50 i 66.


Jedna kolegica je predlozila jos jedno pojednostavljenje: Mogli bi postupiti kao u rjesenju ovakvog zadatka iz skripte, samo koristeci brojeve 2 i 5 (a ne 2 i 3 kao u knjizi).


A mogli bi i cijeli zadatak drugacije promatrati. Vratimo se na mjesto gdje smo poceli sistematizirati.

Mogli bi promatrati slucaj a<=1. Tj. n=3^b*5^c*11^d ili n=2*3^b*5^c*11^d. Tada ili n mora sastojati od 2 razlicita prosta broja (da bi phi(n) bio djeljiv sa 4) ili mora biti 5^2. Ovaj drugi slucaj je dobar pa dobijemo brojeve 25 i 50.
Dakle, na prste provjerimo slucajeve:
b=0,c=1,d=1 ... nije dobar
b=1,c=0,d=1 ... dobar, pa dobijemo 33 i 66
b=1,c=1,d=0 ... nije dobar.

Ako je a=2, tada n mora imati tocno jedan neparan prost faktor (da bi phi(n) bio djeljiv sa 4). Provjerimo ih sve.
phi(2^2*3)=4 ... nije dobar
phi(2^2*5)=8... nije dobar
phi(2^3*11)=20... dobar ... tj dobili samo 44

Ostaje slucaj a=3... n ne smije imati neparnih prostih djelitelja.
Provjerimo phi(8 )=4 ... nije dobar.

Dakle, kad sve saberemo, ponovo smo dobili 25, 33, 44, 50 i 66.

[Lara]

Hvala asistentu:) Ovo će nam dobro doći...

Nego imam jedno pitanje ako može. Evo čitam ovaj dio vježbi s verižnim razlomcima. I negdje sam pri kraju, točnije kod definicije sekundarne konvergente. Pa sad ide par dokaza i par zadataka za zadaću.

Koliko je to sve bitno za kolokvij? Nismo baš puno napravili. Da bi riješili zadatke za zadaću, trebalo bi dobro proučiti skriptu, a tamo ima puno toga.

Npr. kako nismo uopće govorili o transcedentnim brojevima, već je samo za zadaću dano da se dokaže da je red s članom (2 na -n!) transcedentan, smijem li pretpostaviti da pitanja s transcedentnosti neće biti u kolokviju? Mislim općenito na sve u ovom dijelu gradiva, ne samo na transcedentnost.

I još nešto,u dokazu da je svaka dobra aproksimacija irac. broja njegova konvergenta ili sekundarna konvergenta, zašto postoje onakvi P/Q i P'/Q'?

[Lara]

Mislim, suma onog reda je transcedentan broj, naravno

[vinko]

[duje]

[Lara]

Hvala:) Onda se neću zamarati takvim zadatcima...

[Ema]

ako imamo zadatak izracunati broj a=[1,3,1,2,1,2,1,2,....]
a=1+1/(3+1/b),
pri čemu je b=[1,2,1,2,1,2,...]=1+1/(2+1/b))=1+b/(2b+1)=(3b+1)/(2b+1)
⇒ 2b^2-2b-1=0 ⇒ b=(2+2sqrt(3))/4=(1+sqrt(3))/2
ako to uvrstimo u prvu jednadzbu imamo

a=1+1/(3+2/(1+sqrt(3))=1+(1+sqrt(3))/(5+3sqrt(3))=(6+4sqrt(3))/(5+3sqr(3))

a=3-sqrt(3)

zanima me kako bi sada a=3-sqrt(3) ponovo razvili u jednostavni verizni razlomak a=[1,3,1,2,1,2,1,....]?
algoritmom koji je opisan u skripti i koji smo radili na vjezbama sa s_i, t_i, i a_i ne ide, jer dobivamo negativne brojeve.
Smijemo li algoritam promijeniti tako da za s_i, t_i i a_i uzimamo apsolutne vrijednosti dobivenih izraza i a_0=3-sqrt(3)?
u ovom primjeru mi je to uspijelo pa me zanima vrijedi li to i opcenito?
hvala