Teorija brojeva - Zadatak

Teorija brojeva - Zadatak 01.07.2011. u 18:10 · pre 186 meseci #1

ZADATAK
Dokazati da postoji beskonačno mnogo trojki uzastopnih prirodnih brojeva od kojih je svaki zbir dva potpuna kvadrata.

RJEŠENJE:
Postoji bar jedna trojka: $72=6^2+6^2$ , $73=8^2+3^2$ , $74=7^2+5^2$ .

Neka su a,b,c,d, e, f prirodni brojevi i $a^2+b^2$ , $c^2+d^2$ , $e^2+f^2$ tražene trojke.

Onda vrijedi:

$c^2+d^2-a^2-b^2=1$ ,
$e^2+f^2-c^2-d^2=1$ .

...

Treba dokazati da ovaj sistem ima beskonačno mnogo različitih rješenja na skupu prirodnih brojeva. Ima li neko ideju kako dokazati tvrđenje zadatka?

Re: Teorija brojeva - Zadatak 01.07.2011. u 18:51 · pre 186 meseci #2

Umes li da dokazes da postoji beskonacno mnogo Pitagorejskih trojki-tripleta? Imas Euklidov dokaz.
P.S. Da li je dovoljno dokazati da postoji beskonacno mnogo Pitagorejskih trojki?

Potpis

"Nije mi žao što su ukrali moje ideje, već što nisu imali svoje." Nikola Tesla

Re: Teorija brojeva - Zadatak 01.07.2011. u 19:14 · pre 186 meseci #3

Nije to ono što se u zadatku traži, treba dokazati da postoji beskonačno mnogo trojki uzastopnih prirodnih brojeva (svi oni ne mogu da budu potpuni kvadrati, razlika između dva potpuna kvadrata je uvijek veća od 1) koji se mogu napisati kao zbir dva potpuna kvadrata. Jedna takva trojka je 72, 73, 74.

Re: Teorija brojeva - Zadatak 01.07.2011. u 19:32 · pre 186 meseci #4

Pronađi ručno još nekoliko slučajeva, pa probaj da nađeš pravilnost. Uočićeš da za svaki prirodan broj $k$ trojka $\langle 2n^2,2n^2+1,2n^2+2\rangle$ , gde je $n=k(k+1)$ , čini jednu takvu trojku (odgovarajuće sume kvadrata su $n^2+n^2$ , $(n+k)^2+(n-k-1)^2$ i $(n+1)^2+(n-1)^2$ , redom).

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Teorija brojeva - Zadatak 01.07.2011. u 21:27 · pre 186 meseci #5

Hvala ti Bojane, pomogao si mi. Napravio sam program koji traži slučajeve umjesto mene. Sumnjam da bi sam uspio da nađem pravilnost. Može li na neki drugi način da se dokaže tvrđenje zadatka ili mora da se "pogađa"?

Code:
#include <math.h>
#include <iostream>
using namespace::std;

bool provjera(int i)
{
    int k=1;
    while (k*k<i)
        {
            if (sqrt(i-k*k)==(int)(sqrt(i-k*k)))
                {
                    return true;
                }
                    else
                        if ((k+1)*(k+1)>i)
                            return false;
            k++;
        }
}

void ispis(int i)
{
    int k=1;
    while (k*k<i)
        {
            if (sqrt(i-k*k)==(int)(sqrt(i-k*k)))
                {
                    cout<<i<<"="<<k<<"^2+"<<(int)(sqrt(i-k*k))<<"^2\n";
                }
                    else
                        if ((k+1)*(k+1)>i)
                            k=i;
            k++;
        }
}
main()
{
    int* a;
    int n;
    cout<<"n=";
    cin>>n;
    int j;
    cout<<"\nTrazene trojke brojeva manjih od "<<n+1<<" su:\n";
    for(j=1;j<=n-2;j++)
        {
            if (provjera(j)&&provjera(j+1)&&provjera(j+2))
                {
                    cout<<"\n("<<j<<", "<<j+1<<", "<<j+2<<")\n";
                    ispis(j);
                    ispis(j+1);
                    ispis(j+2);

                }
        }
}

Citat:

n=1000

Trazene trojke brojeva manjih od 1001 su:

(72, 73, 74)
72=6^2+6^2
73=3^2+8^2
73=8^2+3^2
74=5^2+7^2
74=7^2+5^2

(232, 233, 234)
232=6^2+14^2
232=14^2+6^2
233=8^2+13^2
233=13^2+8^2
234=3^2+15^2
234=15^2+3^2

(288, 289, 290)
288=12^2+12^2
289=8^2+15^2
289=15^2+8^2
290=1^2+17^2
290=11^2+13^2
290=13^2+11^2
290=17^2+1^2

(520, 521, 522)
520=6^2+22^2
520=14^2+18^2
520=18^2+14^2
520=22^2+6^2
521=11^2+20^2
521=20^2+11^2
522=9^2+21^2
522=21^2+9^2

(584, 585, 586)
584=10^2+22^2
584=22^2+10^2
585=3^2+24^2
585=12^2+21^2
585=21^2+12^2
585=24^2+3^2
586=15^2+19^2
586=19^2+15^2

(800, 801, 802)
800=4^2+28^2
800=20^2+20^2
800=28^2+4^2
801=15^2+24^2
801=24^2+15^2
802=19^2+21^2
802=21^2+19^2

(808, 809, 810)
808=18^2+22^2
808=22^2+18^2
809=5^2+28^2
809=28^2+5^2
810=9^2+27^2
810=27^2+9^2

Process returned 0 (0x0) execution time : 6.328 s
Press any key to continue.

Re: Teorija brojeva - Zadatak 03.07.2011. u 01:39 · pre 186 meseci #6

Ovako kako si uradio — tražio od programa da ispiše sve trojke — dobio si mnogo „šuma“ i zato stvarno ne bi bilo lako naći pravilnost među tim rezultatima. Ja sam postupio malo drugačije: uočio sam da je u tvom primeru prvi član trojke zbir dva ista kvadrata, tj. $2n^2$ , pa sam potražio nekoliko takvih. Uz to se brzo uočava da je tada $2n^2+2=(n+1)^2+(n-1)^2$ (bilo analizom pronađenih primera, bilo čak odmah), što svedoči da smo na dobrom putu — treba još samo uglaviti srednji član trojke. Opet ne treba puno vremena kako bi se ustanovilo da je u svim navedenim primerima srednji član trojke zbir oblika $(n+k)^2+(n-k-1)^2$ , za neko $k$ . Onda postavimo jednačinu $2n^2+1=(n+k)^2+(n-k-1)^2$ i dobijamo da ovo važi za $n=k(k+1)$ .

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Teorija brojeva - Zadatak 03.07.2011. u 15:11 · pre 186 meseci #7

Dobro si uradio (upravo ono što se u zadatku traži, može da se nađe pravilnost postupajući na način koji si opisao), ja sam tražio opšti oblik za sve trojke (više nego što se u zadatku traži), zato nisam uspio. Još jednom hvala.

Re: Teorija brojeva - Zadatak 08.12.2012. u 10:52 · pre 169 meseci #8

Jel moze neko da pomogne oko zadatka...

4.zadatak.png9.4k

Re: Teorija brojeva - Zadatak 08.12.2012. u 14:18 · pre 169 meseci #9

Kako je $a \equiv_{p^n} b$ to nam govori da je $a=b+kp^n$ za neko $k \in \textbf{Z}$ . Zelimo da pokazemo da vazi $a^p \equiv_{p^{n+1}} b^p$ . Pa nista, raspisi $(b+kp^n)^p$ uz pomoc binomne formule i onda pogledaj cemu je to jednako mod $p^{n+1}$ i dobices trazeni rezultat.

Iz kog predmeta ti je ovaj zadatak?

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Teorija brojeva - Zadatak 08.12.2012. u 14:19 · pre 169 meseci #10

Neka je $p$ prost broj. Važi

$a^p-b^p=(a-b)(a^{p-1}+a^{p-1}b+\cdots+b^{p-1})$ .

Dovoljno je dokazati da je drugi činilac sa desne strane jednakosti deljiv sa $p$ . Obzirom da je $b-a$ deljivo sa $p^n$ , deljivo je i sa $p$ , pa je $b\equiv_pa$ odakle sledi da su svi sabirci kongruentni sa $a^{p-1}$ po modulu $p$ , a pošto ih ukupno ima $p$ zbir je deljiv sa $p$ .

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Teorija brojeva - Zadatak 08.12.2012. u 14:55 · pre 169 meseci #11

To je sa prvog kolokvijuma iz teorije brojeva i polinoma... Poceo sam kao i Nedeljko, razvio po onoj formuli, i dokazao da $p^n$ deli citav izraz, pa sam odatle zakljucio da i p deli taj izraz, ali mi je pogresan bio zakljucak... ( da $pp^n$ deli isti izraz... )

Re: Teorija brojeva - Zadatak 08.12.2012. u 15:13 · pre 169 meseci #12

Ja taj predmet ne mogu da nadjem medju predmetima na PMF-u u Nisu, na Matematici, nema veze.

A sta vi ucite iz te teorije brojeva?

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Teorija brojeva - Zadatak 08.12.2012. u 22:37 · pre 169 meseci #13

Stoji na sajtu.. medju prvim predmetima. Izmedju ostalog, radimo deljivost, sisteme ostataka, kongruencije, sisteme kongruencijskih jednacina... To je najtezi ispit, bar u prvom semestru... A radimo zadatke uglavnom sa olimpijada....

Re: Teorija brojeva - Zadatak 08.12.2012. u 23:14 · pre 169 meseci #14

Nasao sam, http://www.pmf.ni.ac.rs/pmf/predmeti/program/1504.pdf. Interesovalo me je samo sta se radi na drugim fakultetima iz predmeta Teorija brojeva i naisao sam na odgovor kakav sam i ocekivao (a koji je za mene razocaravajuci). Ne bih rekao da radite uglavno zadatke sa olimpijada, bar oni koje sam ja nasao http://www.pmf.ni.ac.rs/pmf/predmeti/1504/vezbe.php ne bi se mogli svesti pod tu kategoriju, al nema veze.

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Teorija brojeva - Zadatak 08.12.2012. u 23:25 · pre 169 meseci #15

A zašto bi se radili plimpijski zadaci, pa da niko ne može da pooži ispit? Meni se ovi zadaci sviđaju.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Teorija brojeva - Zadatak 08.12.2012. u 23:33 · pre 169 meseci #16

Nisam rekao da mi je razocaravajuce sto se ne rade olimpijski zadaci, i ne bi trebalo da se rade. Samo me je interesovalo sta se podrazumeva pod predmetom Teorija brojeva i uvek cujem isto (kongruencije po modulu, itd.), a to me malo nervira (to sto se podrazumeva pod samim predmetom, ne mislim na kongruencije po modulu).

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Teorija brojeva - Zadatak 09.12.2012. u 00:32 · pre 169 meseci #17

A stvarno bode oči da nema ničega o raspodeli prostih brojeva.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Teorija brojeva - Zadatak 09.12.2012. u 01:12 · pre 169 meseci #18

Ako si mislio na Prime number theorem onda je i logicno sto to ne rade, jer za njen dokaz je potrebno znanje iz Kompleksne analize (bar za dokaz koji ja znam), pa nije za ocekivati da se to drzi brucosima. Ali zato, sa druge strane, ocene Čebiševa ne zahtevaju neko preveliko znanje, zatim, asimptotske formule za odredjene funkcije i slicno, na primer. Sve zavisi (rekao bih) od predavaca i njegovog odabira kojom oblasti teorije brojeva ce njegov kurs stremiti (da li je to analiticka teorija brojeva, algebraska teorija brojeva ili nesto drugo). Al verujem da je bolje ovaj kurs ostaviti za starije godine, a da se ovakvi zadaci (koij su ovde bili razmatrani) rade u algebri, diskretnoj i slicnim predmetima.

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Teorija brojeva - Zadatak 09.12.2012. u 01:42 · pre 169 meseci #19

Na novosadskom PMF-u u najnovijem (predstojećem) ciklusu akreditacije predmet Teorija brojeva nalazi se na trećoj godini jednog smera i na master studijama drugog smera. Pošto će meni biti poveren taj predmet (predavanja + vežbe), evo programa koji sam sastavio, možda će nekome biti zanimljiv.

Teorijska nastava:
Uvodni pojmovi, mala Fermaova, Ojlerova i Vilsonova teorema. Red ostatka, primitivni koreni. Kvadratni ostaci. Zakon kvadratne recipročnosti. Klasični problemi o prostim brojevima. Diofantove jednačine. Pitagorejske trojke, istorijat velike Fermaove teoreme. Pelova jednačina. Reprezentacije brojeva sumama kvadrata. Proširenja prstena celih brojeva: Gausovi celi brojevi, prsten ℤ[√d]. Dalekosežne hipoteze teorije brojeva: Rimanova hipoteza, Šincelova hipoteza H, abc-hipoteza. Prikaz savremenih tokova teorije brojeva. Osnovni pojmovi o eliptičkim krivima. Osnovi analitičke teorije brojeva. (Poslednja dva naslova rade se samo na ovom smeru gde je predmet na master studijama.)
Praktična nastava:
Osnovna svojstva prostih brojeva i deljivosti. Primena kineske teoreme o ostacima. Primena male Fermaove, Ojlerove i Vilsonove teoreme. Rad sa kongruencijama višeg reda. Rešavanje i primena Pelove jednačine. Reprezentacije brojeva sumama kvadrata. Primena proširenja prstena celih brojeva. Kondicionalno rešavanje problema pod otvorenim pretpostavkama.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

1

Re: Teorija brojeva - Zadatak 09.12.2012. u 01:55 · pre 169 meseci #20

Sonec

Teorema se može učiti i bez dokaza, kao i njeno primenjianje.

Bojane, zašto nisi ugurao teoremu o prostim brojevima, možda na račun nečega drugog? Da li će biti na sajtu nečega za nas neuke?

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Forum kao aplikacija na telefonu

Srodne teme