1. Demonstrati ca exista o infinitate de numere prime de forma 4n+3 si 6n+5 (fara a folosi teorema Dirichlet, cu progresiile aritmetice)
2. Demonstrati ca daca

, atunci f ia valori numere prime pentru x de la 1 la 80, dar nu si mai departe.
3. Fie a,b,c,d,m,n,u,v numere intregi cu proprietatile ad-bc=1 sau -1, u=am+bn, v=cm+dn. Demonstrati ca (m,n)=(u,v), unde (a,b)=cmmdc(a,b).
4. Demonstrati ca orice numar n se scrie ca n=ab, cu a liber de patrate si b patrat perfect. Mai mult, b este cel mai mare patrat perfect care divide n.

Observatii:
- Problema 4 nu prea o inteleg, sincer, decat daca se considera 1 ca fiind patrat perfect. De exemplu, am incercat sa ma gandesc la 100 = 25 * 4 si atat, la alte patrate nu se mai imparte, dar nu verifica, conditiile. Sau 30, de exemplu, cum se scrie?
- V-as ruga, pe cat posibil, sa dati solutii elementare. Toate problemele sunt din An Introduction in the Theory of Numbers - I. Niven, H. Montgomery, H. Zuckerman, primul capitol, unde se introduc doar notiunile de cmmdc si numere prime si notiuni conexe, insa la nivel elementar. Daca oferiti o solutie mai sofisticata, v-as ruga sa mentionati si notiunile teoretice utilizate, cu o scurta descriere.


Multumesc.

[Citat] 1. Demonstrati ca exista o infinitate de numere prime de forma 4n+3 si 6n+5 (fara a folosi teorema Dirichlet, cu progresiile aritmetice)

Daca prin absurd toate numerele prime de forma 4n+3 ar fi multimea finita

atunci sa ne uitam la numarul

Acest numar nu poate avea toti divizorii primi de forma 4n+1, prin urmare are un divizor prim de forma 4n+3. Dar acest divizor nu poate fi in multimea de mai sus, absurd! La fel se face si cealalta problema.

[Citat] 2. Demonstrati ca daca , atunci f ia valori numere prime pentru x de la 1 la 80, dar nu si mai departe.

Acest lucru este o variatie a faptului ca

sunt numere prime. La o olimpiada internationala s-a dat o problema care arata ca este suficient sa verificam acest lucru doar pentru

.

[Citat] 3. Fie a,b,c,d,m,n,u,v numere intregi cu proprietatile ad-bc=1 sau -1, u=am+bn, v=cm+dn. Demonstrati ca (m,n)=(u,v), unde (a,b)=cmmdc(a,b).

Arati ca aceste numere se divid unul pe celalalt, deci sunt egale (matricile de ordinul doi cu coef. intregi cu determinant unu sau minus unu sunt inversabile iar inversele au tot coeficienti intregi).

[Citat] 4. Demonstrati ca orice numar n se scrie ca n=ab, cu a liber de patrate si b patrat perfect. Mai mult, b este cel mai mare patrat perfect care divide n. Observatii: - Problema 4 nu prea o inteleg, sincer, decat daca se considera 1 ca fiind patrat perfect. De exemplu, am incercat sa ma gandesc la 100 = 25 * 4 si atat, la alte patrate nu se mai imparte, dar nu verifica, conditiile. Sau 30, de exemplu, cum se scrie? - V-as ruga, pe cat posibil, sa dati solutii elementare. Toate problemele sunt din An Introduction in the Theory of Numbers - I. Niven, H. Montgomery, H. Zuckerman, primul capitol, unde se introduc doar notiunile de cmmdc si numere prime si notiuni conexe, insa la nivel elementar. Daca oferiti o solutie mai sofisticata, v-as ruga sa mentionati si notiunile teoretice utilizate, cu o scurta descriere. Multumesc.

1 este patrat perfect!

"La o olimpiada internationala s-a dat o problema"...
E vorba despre http://www.mathlinks.ro/viewtopic.php?p=366550#366550

Foarte ingenioasa solutia cu matricea, multumesc si pentru cealalta.

O mica intrebare totusi...nu prea reusesc sa inteleg demonstratia la aceea cu

, stiu ca e chiar un rezultat celebru, ma refer la faptul ca stiu ca fost propusa de Euler ca o formula pentru prime. V-as ruga sa schitati o solutie un pic mai elaborata (cat mai - cu putinta )

Si scuze, cea la care dumneavoastra mi-ati confirmat "banuiala" ca 1 e patrat perfect..tot nu prea o diger.

Adica, de exemplu, pentru n=100, cum ziceam...scriu 1*100 sau 4*25 si tot nu e bine, adica nu are un factor liber de patrate.. Imi scapa ceva? (sigur! )

Multumesc.

Enuntul corect este: un numar natural fie este patrat perfect, fie se scrie in mod unic ca produs dintre un patrat perfect si un numar liber de patrate. E o chestie absolut triviala.

[Citat] [Citat] 2. Demonstrati ca daca , atunci f ia valori numere prime pentru x de la 1 la 80, dar nu si mai departe. Acest lucru este o variatie a faptului ca sunt numere prime. La o olimpiada internationala s-a dat o problema care arata ca este suficient sa verificam acest lucru doar pentru .

Imi aratati si cum, va rog?

Functia data se rescrie
f(x) = -x(81-x) + 41.41
si are graficul urmator:

(Simetrie. Doar 40 de valori de testat.)
Ne intereseaza aceasta functie mai ales pe [1,80] taiat cu ZZ.
Valorile ei AICI sunt intre f(40)=f(41)=41 si 1601 < 41*41,
deci daca una din valorile lui f pe [1,40], sa zicem in x din ZZ,
este numar compus,
dam de un factor prim sub 41 in f(x). Doar pe acestia trebuie sa-i discutam.



Nu avem 40 de valori de calculat si daramat, o nimica toata pentru computer,
ci putem sa ne facem viata mai grea
(dar calculele mai usoare, daca avem cunostinte mai grele),
si sa ne intrebam doar, daca avem sansa sa dam de unul dintre divizorii
dintre primele 12 numere prime

? print( primes(12) )
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

printre aceste numere.

Fie p unul dintre aceste numere prime.
Cazul p=2 iese imediat din discutie,
numarul x(81-x) fiind par ca produs de doua numere de paritate diferita.
Adunand 1681...

Atunci modulo p ne intrebam daca f(x) poate fi congruent cu 0.
Echivalent, daca 4f(x) poate fi congruent cu 0 modulo p.

Pentru 4f(x) avem grupare mai simpla...

Innodand firul mai sus, echivalent, daca

este rest patratic modulo p.
Acest lucru se determina "usor",
daca cititorul a auzit de simboluri Legendre, sau Hilbert, sau Jacobi...
Avem (code sage, vezi sagemath pe net):

Bun, nici o sansa ca -163 sa fie patrat modulo unul dintre primele numere prime.

Mai departe e clar ca f(81)=1681=41.41 nu mai e prim.

Statistica pentru urmatoarele valori este:

sage: for x in range(81,101): print "x=%3d f(x)=%4d is_prime = %s" % ( x, f(x), Integer(f(x)).is_prime() )
....:
x= 81 f(x)=1681 is_prime = False
x= 82 f(x)=1763 is_prime = False
x= 83 f(x)=1847 is_prime = True
x= 84 f(x)=1933 is_prime = True
x= 85 f(x)=2021 is_prime = False
x= 86 f(x)=2111 is_prime = True
x= 87 f(x)=2203 is_prime = True
x= 88 f(x)=2297 is_prime = True
x= 89 f(x)=2393 is_prime = True
x= 90 f(x)=2491 is_prime = False
x= 91 f(x)=2591 is_prime = True
x= 92 f(x)=2693 is_prime = True
x= 93 f(x)=2797 is_prime = True
x= 94 f(x)=2903 is_prime = True
x= 95 f(x)=3011 is_prime = True
x= 96 f(x)=3121 is_prime = True
x= 97 f(x)=3233 is_prime = False
x= 98 f(x)=3347 is_prime = True
x= 99 f(x)=3463 is_prime = True
x=100 f(x)=3581 is_prime = True