OliForum Matematico

Salve, propongo di iniziare la staffetta anche in questa sezione, che al momento mi pare la più attiva; proporrei anche agli autori dei problemi di postare la loro soluzione qualora il problema non venisse risolto entro circa una settimana..

Problema 1.
Mostrare che se $ p $ è primo allora esistono $ (a,b) \in \mathbb{Z}^2 $ tali che $ p|a^2+b^2+1 $.

Buon lavoro

Se p congruo 1 mod 4 si sa ch esiste soluzione a $ x^2 \equiv -1 \pmod p $ e di lì ponendo a soluzione, b=0 fine. Altrimenti si ha: la lista dei residui quadratici è tale che l'opposto di un residuo nn è mai della lista, ma allora basta far vede che aggiungere 1 a ciascun elemento della lista porta ad un residuo non quadratico: ragionando all estremo partendo da 1 si arriva fino a p-1/2 e da lì necessariamente non quadratico. Ma allora è chiaro che prendendo a residuo quadratico tale che a+1 non lo è, si ottiene che -a-1 lo è, e dunque abbiamo ricavato la soluzione.

Questo problema io l'ho risolto per metà(poi semmai espliciterò più avanti il senso di questa frase) ma ritengo che già fin lì è davvero interessantissimo...Se nessuno dovesse mettere soluzione entro la settimana metterò la mia parziale nella speranza che qualcuno sappia adoperarla adeguatamente per l'altra metà.
Sia R l'insieme dei residui quadratici, sia S l'insieme ottenuto aggiungendo 1 a ciascun residuo quadratico: il tutto in Zp, con p primo. Calcolare la cardinalità dell'intersezione tra R e S.

No! Mi hai preceduto!
Avevo risolto il problema a scuola e stavo per scrivere la soluzione

Dovrei quasi vergognarmi io vecchio puzzone che rubo il pane di bocca alla beata gioventù : ma in fondo nella staffetta vige la legge della giungla
Comunque rifatti col mio dai, che è molto bello

Problema 2.

Sia $ n_p $ il numero cercato, con $ p $ primo; consideriamo inoltre per il momento che 0 non sia un residuo quadratico nè non quadratico.
Fatto 1. Abbiamo che $ |(\frac{\alpha}{p})|=1, \forall 0<\alpha<p $, per cui $ (\frac{\alpha}{p})+1=0 $ se e solo se $ \alpha $ non è un residuo quadratico. Per cui un intero $ 0<a<p-1 $ appartiene all'intersezione tra $ S $ e $ R $ se e solo se $ \frac{1}{4}((\frac{a}{p})+1)((\frac{a+1}{p})+1)=1 $, altrimenti sarà 0.
Fatto 2. Ricordiamo che $ \sum_{i=0}^{p-1}{i^n} \equiv 0 \pmod p $ se $ p-1 \nmid n $, altrimenti dà resto $ -1 $, sempre grazie a Fermat. Per cui $ \sum_{i=0}^{p-1}{(i^2-1)^{\frac{p-1}{2}}}=\sum_{i=0}^{p-1}{i^{p-1}+q(i)} \equiv -1 \pmod p $, per qualche polinomio $ q(x)\in \mathbb{Z}[X] $ tale che $ deg(q(x))<p-1 $.
Fatto 3. Cerchiamo di calcolare $ A=\sum_{i=0}^{p-1}{(\frac{i(i+1)}{p})} $. Abbiamo $ A=(\frac{4}{p})A = \sum_{i=0}^{p-1}{(\frac{(2i+1)^2-1}{p})} $. Inoltre $ \{2i+1\}_{i=0}^{p-1} $ forma un sistema completo di residui modulo $ p>2 $. Ciò significa che $ A=\sum_{i=0}^{p-1}{(\frac{i^2-1}{p})} $. Per il criterio di Eulero allora $ A=\sum_{i=0}^{p-1}{(i^2-1)^{\frac{p-1}{2}}} \equiv -1 \pmod p $ grazie al fatto 2.
Fatto 4. Vale inoltre che $ |A| \le p $ per cui $ A+1 $ può valere solo $ 0 $ o $ p $. Poniamo che $ A=p-1 $ allora nella sommatoria di $ A $ tutti i simboli di Legendre avranno come valore $ 1 $ ed uno solo lo $ 0 $; chiamiamo $ x_0 $ tale valore: ciò significa che $ p|x_0^2-1 $, ma anche $ p|(-x_0)^2-1 $, per cui $ x_0=0 $, e quindi $ p|1 $, assurdo. Abbiamo quindi concluso che $ A=-1 $.
Fatto 5. Se un primo è diverso da 2 allora, grazie al criterio di Eulero, $ (\frac{-1}{p})=1 \leftrightarrow 4|p-1 $.
Soluzione. Abbiamo per le considerazioni precedenti che (senza considerare lo 0) il valore di $ n_p $, per ogni primo $ p>2 $, è dato da $ n_p=\frac{1}{4}[\sum_{i=1}^{p-2}{((\frac{i}{p})+1)((\frac{i+1}{p})+1)}] $, per cui $ 4n_p=\sum_{i=0}^{p-1}{(\frac{i(i+1)}{p})}+\sum_{i=0}^{p-1}{[(\frac{i}{p})+(\frac{i+1}{p})+1]}- $ $ ((\frac{0}{p})+1)((\frac{1}{p})+1)-((\frac{p}{p})+1)((\frac{p-1}{p})+1) $, allora $ 4n_p=(A+p)-2-(1+(\frac{-1}{p})). $.
Considerando inoltre il fatto 5, e aggiungendo lo zero si dovrà aggiungere $ 2 $ se $ 4|p-1 $, altrimenti soltanto $ 1 $.
Conclusione. $ n_2=2 $, e $ n_p=\frac{p+2+(-1)^{\frac{p-1}{2}}}{4}, \forall p>2 $.

Problema 3.
Sapendo che $ a \in \mathbb{Z} $ è un residuo quadratico modulo tutti i primi, mostrare che $ a $ è un quadrato perfetto.

Nb. Può essere utile utilizzare il teorema di Dirichlet, secondo cui ogni progressione aritmetica $ ax+b $ contiene infiniti primi se $ gcd(a,b)=1 $.

Prima che vada nell oblio il problema, posto il mio tentativo che magari qualcuno di voi sa concludere(pure perchè è molto diverso dall approccio di jordan quindi può essere utile vedere più approcci).
1)Dimostriamo per assurdo che due residui quadratici aventi differenza 1 esistono:sappiamo che 1 e 4 sono residui quadratici, dunque 2 e 3 non possono esserlo. Cioè se a è residuo quadratico, nè a-1 nè a+1 lo sarà. Ma dunque sapendo che vi sono $ (p-1)/2 $ residui quadratici abbiamo che il massimo residuo quadratico è almeno $ 4+2((p-1)/2-2)=p-1 $ . Ne segue che da 4 in poi se a è residuo quadratico necessariamente a+2 lo è. Ma allora 8 è residuo quadratico, ma 2 no, e poichè $ 4(2)=8 $ e poichè i residui quadratici sono chiusi rispetto al prodotto si ha un assurdo.Dunque abbiamo appurato che due residui quadratici consecutivi vi devono essere.
2)Sia R l'insieme dei residui quadratici, sia al solito $ R^2 $ l'insieme di coppie di elementi di R. Sia g l'applicazione da $ R^2 $ a $ Z_p $ t.c: per ogni $ (x,y); g(x,y)=x-y $. Sappiamo che 1 ammette controimmagine nonvuota. Vogliamo calcolare la cardinalità della controimmagine di 1.
Dimostriamo ora che la controimmagine di 1 ha la stessa cardinalità della controimmagine di qualsiasi residuo quadratico. Difatti sia $ r $ in R. Trasformiamo $ R^2 $ in se stesso moltiplicando ciascuna coppia per r: questa è una permutazione di $ R^2 $. E la controimmagine di 1 si è permutata nella controimmagine di r. Questa stessa idea ci permette di dire che le controimmagini dei residui non quadratici hanno tutte la stessa cardinalità. Difatti sappiamo che esiste nell'immagine almeno un residuo non quadratico( altrimenti i residui quadratici sarebbero chiusi rispetto alla somma, ma poichè 1 è residuo quadratico questo significa che tutti sono residui quadratici). E sappiamo che ciascun altro residuo non quadratico è esprimibile come prodotto del nostro residuo per un elemento di R. Dunque permutando le coppie come prima la controimmagine di ciscun residuo non quadratico si trasforma biettivamente nella controimmagine di un altro residuo non quadratico.
3)Dunque chiamiamo $ j,k $ rispettivamente la cardinalità delle controimmagini dei residui quadratici e dei residui non quadratici. Tutto il lavoro del punto 2 ci dice che $ (p-1/2)(j+k)=(p-1)/2(p-1/2-1) $ (il secondo membro dell'uguaglianza è la cardinalità delle coppie a elementi non identici).
Ovvero $ j+k=(p-1)/2-1 $. E se $ p \equiv 3 \pmod 4 $ sappiamo che $ j=k $ perchè difatti $ -1 $ non è residuo quadratico e se $ (x,y) $ appartiene alla controimmagine di 1, allora $ (y,x) $ appartiene a quella di -1. Dunque si ha $ j=(p-1/2-1)/2 $ come risultato ricercato.
Qui mi son fermato perchè non sono riuscito a trovare relazioni tra j e k nell'altro caso.
Nel link di seguito trovate descritto da federiko97 un modo per completare in generale, e decisamente più sofisticato dell'ingenuo switch nelle coppie
viewtopic.php?t=12642

Sia a il nostro numero: supponiamo per assurdo che non è un quadrato perfetto. Allora esistono $ p_1...p_n $ fattori primi di a, tali che ciascuno di essi abbia esponente dispari nella fattorizzazione di a. Dal teorema di Dirichlet so che posso trovare un certo primo $ q $ che ha un residuo a mia scelta modulo ciascuno dei $ p_i $. Ora si tratta di usare qualcosa che ci permette di ribaltare questa cosa in relazione alla quadraticità:la legge di reciprocità quadratica. Sempre per il teorema di Dirichlet posso suppore $ q \equiv 1 \pmod 4 $. Da questa scelta segue che se scelgo q residuo quadratico mod $ p_i $ allora anche $ p_i $ è residuo quadratico mod q e viceversa. Ma allora sia $ n=h+f $ con h dispari e f non ci interessa: nella selezione del primo che possiamo fare col teorema di Dirichlet facciamo in modo che rispetto a f primi q sia residuo quadratico e rispetto a h primi sia non quadratico: questo significa che h primi saranno residui non quadratici mod q e f primi si: ma allora poichè la quadraticità di a è la stessa di questo prodotto,otteniamo che a non è quadratico mod q. Quindi la tesi...

Problema 4
Sia $ p(n) $ la funzione che associa ad ogni naturale n il numero di modi in cui può essere scritto come somma di numeri interi positivi. Dimostrare che $ 2^{[(\sqrt(n))]}<p(n) $ Spero non lo troviate troppo banale/brutto, ma al momento non mi è venuto altro in mente.
Ciaociao!
p.s:n è maggiore di uno
Edit:si Feddy stra, ovviamente intendevo quello.Insomma:parte intera della radice quadrata di n: ora penso non ci siano più ambiguità possibili

Con $ [(\sqrt(x))] $ intendi $ \lfloor\sqrt x\rfloor $?

Bon la settimana è passata,e il problema non deve essere piaciuto tanto a tanti. Vabbeh metto la mia soluzione e amen:
Basta trovare un insieme che ha cardinalità $ 2^{[ \sqrt n]} $ e che sia sottoinsieme proprio dell'insieme delle partizioni di n: che ci ricorda quel numero?la cardinalità dell'insieme delle parti di un insieme a cardinalità $ [ \sqrt n] $: prendiamo dunque l'insieme $ {1,.....,[ \sqrt n] } $ esso ha $ 2^{[ \sqrt n]} $ parti. Proviamo a far corrispondere a ciascuna parte una partizione. La costruzione è semplice: nella partizione ci sarà gli elementi della parte, a cui aggiungiamo il termine complementare per arrivare ad n. Si tratta di vedere che la cosa è ben posta ai nostri fini: ma in effetti la somma massima che troviamo dalle parti è ovviamente $ 1+....+[ \sqrt n]=[ \sqrt n]([ \sqrt n]+1)/2 $...ed è chiaro che a somma massima corrisponde complementare minimo: $ ({[ \sqrt n]}^2)/2-[ \sqrt n]/2> [ \sqrt n] $ la quale disequazione(LHS sarebbe, svolgendo i conti, il calcolo del complementare minimo) è soddisfatta per $ [ \sqrt n]>2 $ .Il che significa che le partizioni così costruite sono a due a due distinte(se il calcolo ci dava torto si rischiava di contare due volte la stessa cosa,perchè il complementare poteva scambiarsi con un termine dell'insieme di su)...ma a questo punto è ben evidente che si trova almeno un altra partizione diversa da quelle costruite(un modo può essere a mò di esempio mettere due volte 1 e completare a casaccio...tanto tutte quelle che abbiamo costruito 1 compare al più una volta)... E' chiaro che per il caso 2 basta a mano p(4)>4 che ovviamente, a causa della crescenza di p(n) e dell'invarianza di $ [ \sqrt n] $ da un quadrato all'altro implica tutti i casi fino a 9.
Passo la staffetta per passare la staffetta: chi pensa di avere un bel problema di teoria dei numeri da proporre, proponga(al momento non ne ho).

Non ti offendi se ti chiedo di riscriverla meglio? Perché leggendo mi perdo alla terza riga... chenneso, dando dei nomi agli insiemi e andando ogni tanto a capo. Sarò scemo io, ma non riesco a leggerla...

No se mi offendessi sarei ,come si dice dalle mie parti: ciuccio e presuntuoso.In effetti rileggendola è scritta piuttosto maluccio.Dunque avevi il diritto a non comprenderla.
Vabbeh dopo aver speso una mezz oretta a scriverla bene, una volta postata mi si è scambiati due paragrafi e texxato follemento in vari punti.
Mò la riscrivo.

Osservazioni:1) dimostrata la tesi per $ n^2 $ essa sarà automaticamente provata per ogni naturale a causa della crescenza di p(n), e dell'invarianza di $ [\sqrt n] $ tra due quadrati.
2) sia $ R(n^2) $ l'insieme delle partizioni di $ n^2 $, S l'insieme $ (1,...n) $ P(S) il suo insieme delle parti, la tesi è $ card(P(S))<card(R(n^2))=p(n^2) $
Vogliamo quindi trasformare gli elementi di $ P(S) $ in elementi di $ R(n^2) $ iniettivamente, e poi vedere che tale trasformazione non è suriettiva.
3) Sia $ j=\sum_1^n(i) $ è la somma massima che possiamo ottenere da una collezione di elementi di S presi a due a due distinti. Sappiamo che vale $ j=(n^2+n)/2 $
4) $ j<n^2 $
5) Per n maggiore di 2,n quadro meno j è maggiore di n(uguale solo in n=3 e come dice julio nel post dopo non ci dà problemi), (ok non so perchè se mettevo insieme gli ultimi due messaggi in codice impazziva)
6) consideriamo l'applicazione che mi manda la parte $ h=(h_1....h_g) $ nella partizione $ h_1+...h_g+c $ dove c è il termine complementare per arrivare ad n^2.
Ora la 4 ci dice che l'applicazione è ben definita, ovvero che c è intero positivo e che dunque quella è una partizione; la 5 mi dice che tale applicazione è iniettiva:difatti se c è maggiore di n, partendo da parti diverse arrivo a partizioni che differiscono per i valori minori di n(cosa che non è assicurata appunto se c fosse minore di n). Ora è facile vedere che l applicazione non è suriettiva: basta prendere una partizione in cui 1 compare due volte(difatti nell'immagine della nostra applicazione 1 compariva al più una volta).
Il caso n=2 si sistema a mano.
Spero di averla scritta in un modo un pò più chiaro di prima, ma ditemi pure se è ancora oscura. Devo dire che tex si è sbizzarito nel frattempo a mettermi i bastoni tra le ruote(frase che può essere vista al rovescio: tu imbranato mettevi i bastoni tra le ruote a tex scrivendo come una capra,violando più volte i tabù base del codice ), dunque le frasi scritte non simboliche non sono frutto di un ostentato tentativo di sfregio al simbolismo
Edit: ok grazie delle segnalazioni julio.