Staffetta tdn

[<enigma>]

Ottimo kn, lo stesso procedimento a cui avevo pensato. Ma a questo punto generalizziamo... il numero di soluzioni a $ x^2 \equiv 1 \pmod n $ in $ \mathbb Z _n ^* $ è
- $ 2^ {\omega (n)-1} $ se $ n \equiv 2, 6 \pmod 8 $;
- $ 2^ {\omega (n)} $ se $ n \equiv 1, 3, 4, 5, 7 \pmod 8 $;
- $ 2^ {\omega (n) +1} $ se $ n \equiv 0 \pmod 8 $.
Vai col 72!

[kn]

Problema 72. Prendiamo un intero n dispari maggiore di 3. Siano k e t i più piccoli interi positivi tali che $ \displaystyle~kn+1 $ e $ \displaystyle~tn $ sono entrambi quadrati perfetti. Mostratemi che n è primo sse k e t sono entrambi $ \displaystyle~>\frac{n}{4} $

[GioacchinoA]

Problema 72.

Divido in due parti:

- n primo $ $\Rightarrow k, t > \frac{n}{4}$ $

Chiaramente se n è primo allora $ $t=p$ $. Trovo il più piccolo k t.c. $ $kp + 1 =x^2$ $. Analizzo mod p e ottengo $ $x^2 \equiv 1 \pmod p \Rightarrow x \equiv 1,p-1 \pmod p $. Escluso 1 il più piccolo x è proprio $ $p-1$ $, da cui risulta $ $k=p-2 > \frac{p}{4}$ $ perché $ $p \geq 3$ $ per ipotesi.

- $ $k, t > \frac{n}{4} \Rightarrow $ $ n primo.

Ricordando che $ $a \Rightarrow b \Leftrightarrow \overline{b} \Rightarrow \overline{a}$ $ rimane da dimostrare che n composto $ $\Rightarrow$ $ almeno uno fra $ $k,t \leq \frac{n}{4}$ $.

Caso 1: Se $ n $ è scrivibile come il prodotto di due o più primi distinti l'equazione $ $x^2 \equiv 1 \pmod n$ $ ha almeno 4 soluzioni (vedi post precedenti). Ma se $ $x$ $ è soluzione lo è anche $ $n-x$ $, dunque posso concludere che esiste almeno una soluzione diversa da 1 e minore di $ $\frac{n}{2} $. Sia A l'insieme delle soluzioni (modulo n) diverse da 1 e minori di $ $\frac{n}{2} $. Per quanto detto A non è vuoto e dunque ha minimo essendo finito. Sia $ a $ tale minimo. Chiaramente per tutti gli $ $x equiv a \pmod n$ $ esiste un k, ma in corrispondenza di $ a $ si ha quello minimo. Dunque $ $kn + 1 = a^2 \Rightarrow kn \leq \frac{n^2-4}{4} \Rightarrow k \leq \frac{n^2-4}{4n} < \frac{n}{4} $.

Caso 2: Se $ $n$ $ è la potenza di un primo con esponente diverso da 1, se l'esponente è pari $ $t=1 < \frac{n}{4}$ $. Se l'esponente è dispari $ $t=p < \frac{p^3}{4} \leq \frac{p^{2m+1}}{4}$ $, dove 2m+1 è un disapri maggiore o uguale di 3.

Giusto? Aspetto la tua conferma $ kn $

[GioacchinoA]

Ho ricevuto la conferma di kn.
$ \textbf{Problema 73} $
Sia $ $P(n)$ $ la funzione che associa ad ogni intero positivo $ $n$ $ il numero di permutazioni di $ $\{ 1,2,...,n \}$ $ tali che $ $\forall 1 \leq i \leq n, ia_i $ $ è un quadrato ($ $a_i$ $ è l'i-esimo termine della permutazione). Trova il più piccolo $ $n$ $ tale che $ $2010|P(n)$ $.

[dario2994]

Uhm... contiamo un po sto P(n)...
Prima di tutto "libero dai quadrati" tutti i numeri nell'insieme... tanto non cambia una mazza ai fini del problema, anzi si semplifica tutto.
Così ottengo un set di numeri che sono prodotto di primi distinti... se voglio che il prodotto fra 2 sia un quadrato... beh l'unica è chiaramente che quei 2 siano uguali.
Quindi la permutazione deve mandare un elemento in uno uguale, quindi la permutazione è la composizione di permutazioni ASSOLUTAMENTE libere tra gli elementi uguali. Resta da contare il numero di permutazioni tra gli elementi uguali e poi moltiplicare tutto.
Ora... creo un nuovo insieme in cui riordino la roba, quelli uguali li piazzo vicini, ed inoltre in ordine crescente. Quindi avrò una cosa tipo un po di 1, poi dei 2, poi qualche 3, qualche 5, alcuni 6, un poco di 7, una barca di 10... etcetc
Ora associo a questo insieme un altro insieme che ha come primo elemento il numero di 1, poi il numero di 2, poi il numero di 3, poi il numero di 5 etc etc.
Ne creo un altro ancora in cui l'i-esimo elemento è il fattoriale dell'i-esimo elemento dell'insieme precedente.
È chiaro che quest'ultimo insieme contiene i numeri delle permutazioni libere tra gli elementi uguali (quindi moltiplicando tutto otterrei P(n)).
Io voglio che tra questi fattoriali alcuni moltiplicati contengano 2010 quindi 2*3*5*67... è chiaro che se un fattoriale è divisibile per 67 è divisibile anche per 2,3,5... quindi voglio che almeno uno dei fattoriali sia >= 67!... tra quei fattoriali "È molto credibile" che il più grande sia il primo (in verità il fattoriale associato ad un dato prodotto di primi è la radice di n fratto quel prodotto di primi, da cui segue quanto ho claimato). Quindi affinchè sia vera l'ipotesi del problema il numero di numeri minori di n che una volta liberati da quadrati fanno 1 deve essere almeno 67...
Ma se un numero liberato da quadrati va in 1 allora era un quadrato, inoltre i quadrati minori di n sono $ $\lfloor\sqrt{n}\rfloor $... quindi devo trovare il minore n tale che:
$ $\lfloor\sqrt{n}\rfloor\ge 67 $
È ovvio che questo n è $ $67^2 $ che perciò è la soluzione del problema.

[dario2994]

Problema 74
La sequenza di interi positivi $ $a_0,a_1,a_2\dots $ rispetta:
$ $MCD(a_{n+2},a_{n+1})>a_n\ \ \forall n\ge0 $
Dimostrate che $ $a_n\ge 2^n\ \ \forall n\ge 0 $

[kn]

Intanto poniamo $ \displaystyle~b_n=(a_n,a_{n+1}) $ per ogni $ \displaystyle~n\ge 0 $.
Consideriamo la sequenza $ \displaystyle~\{c_n\} $ con $ \displaystyle~c_0=b_0 $ e $ \displaystyle~c_{n+1}=\textrm{lcm}(b_n,b_{n+1}) $ per ogni $ \displaystyle~n\ge 0 $.
Questa rispetta ancora tutte le ipotesi: dato che $ \displaystyle~b_{n+1}\mid c_{n+1} $ e $ \displaystyle~b_{n+1}\mid c_{n+2} $, $ \displaystyle~(c_{n+1},c_{n+2})\ge b_{n+1}=(a_{n+1},a_{n+2})>c_n,~\forall n\ge 0 $. Inoltre $ \displaystyle~c_0=b_0\le a_0 $ e dato che $ \displaystyle~b_n\mid a_{n+1} $ e $ \displaystyle~b_{n+1}\mid a_{n+1} $ abbiamo $ \displaystyle~c_{n+1}\mid a_{n+1}~(*) $, quindi $ \displaystyle~c_{n+1}\le a_{n+1} $.
Dunque basta far vedere che $ \displaystyle~c_n\ge 2^n~\forall n\ge 0 $ per avere la tesi.
Scusate questo ciarpame di successioni, potevo sostituire tutto con un bel wlog ma così è più rigoroso..
Dopo aver semplificato la successione, ci accorgiamo che, essendo $ \displaystyle~c_n\mid a_n~\forall n\ge 0~(*) $, $ \displaystyle~(c_n,c_{n+1})\mid b_n $ che unito a $ \displaystyle~b_n\mid (c_n,c_{n+1}) $ dà $ \displaystyle~(c_n,c_{n+1})=b_n $. Quindi possiamo sbarazzarci dei $ \displaystyle~\{c_n\} $, visto che ora ipotesi e tesi sono esprimibili con i soli $ \displaystyle~\{b_n\} $:

Problema 74 (2^ edizione)
La sequenza di interi positivi $ \displaystyle~b_0,b_1,b_2,\ldots $ rispetta le ipotesi $ \displaystyle~b_{n+1}>\textrm{lcm}(b_n,b_{n-1})~\forall n\ge 1 $ e $ \displaystyle~b_1>b_0 $. Allora $ \displaystyle~(b_n,b_{n-1})\ge 2^n $ (e $ \displaystyle~b_0\ge 1 $ ).

Dalle ipotesi $ \displaystyle~\{b_n\} $ è strettamente crescente. Mostriamo la tesi per $ \displaystyle~n=1,2,3,4 $:
n=1 $ \displaystyle~b_1>b_0\ge 1 $ quindi $ \displaystyle~b_1\ge 2 $ e $ \displaystyle~\textrm{lcm}(b_1,b_0)\ge 2 $
n=2 $ \displaystyle~b_2>\textrm{lcm}(b_1,b_0)\ge 2 $ (v. qui sopra) e quindi è almeno 3. Se $ \displaystyle~b_2=3 $, $ \displaystyle~1<b_1<b_2=3 $ da cui $ \displaystyle~b_1=2 $ e $ \displaystyle~\textrm{lcm}(b_2,b_1)=6>4 $, altrimenti $ \displaystyle~b_2\ge 4 $ e $ \displaystyle~\textrm{lcm}(b_2,b_1)\ge 4 $
n=3 $ \displaystyle~b_3>\textrm{lcm}(b_2,b_1)\ge 4 $ e se fosse $ \displaystyle~\textrm{lcm}(b_3,b_2)<8 $ allora $ \displaystyle~\textrm{lcm}(b_3,b_2) $ dovendo essere multiplo di $ \displaystyle~b_3 $ dovrebbe essere proprio $ \displaystyle~b_3 $, da cui $ \displaystyle~b_2\mid b_3 $, quindi $ \displaystyle~b_3 $, non potendo essere primo ($ \displaystyle~b_2>2 $), dovrebbe essere 6, da cui $ \displaystyle~b_2=3 $ e $ \displaystyle~b_1=2 $ (assurdo per l'ipotesi $ \displaystyle~b_3>\textrm{lcm}(b_2,b_2) $)
n=4 anche qui supponiamo per assurdo che $ \displaystyle~(b_3,b_4)<16 $; allora $ \displaystyle~8<b_4<16 $ con $ \displaystyle~b_3\mid b_4 $. Essendo $ \displaystyle~b_4 $ composto con un divisore proprio maggiore di 4 ($ \displaystyle~b_3 $) deve essere $ \displaystyle~b_4\in\{10,12,14,15\} $. Se $ \displaystyle~b_4\in\{10,15\} $, $ \displaystyle~b_3=5 $ da cui, essendo $ \displaystyle~b_2\ge 3 $ e coprimo con 5, $ \displaystyle~15\ge b_4>\textrm{lcm}(b_2,b_3)=5b_2\ge 15 $, assurdo. Se $ \displaystyle~b_4=14 $, $ \displaystyle~b_3=7 $ che di nuovo è coprimo con $ \displaystyle~b_2 $ e dà un assurdo come sopra (14>21). Se $ \displaystyle~b_4=12 $, $ \displaystyle~b_3=6 $ e $ \displaystyle~\textrm{lcm}(b_3,b_2)=b_3 $ (sempre per l'ipotesi $ \displaystyle~b_4>\textrm{lcm}(b_3,b_2) $) quindi $ \displaystyle~b_2=3 $ e $ \displaystyle~b_1=2 $, assurdo perché deve essere $ \displaystyle~b_3>\textrm{lcm}(b_2,b_1) $

A questo punto supponiamo per assurdo che $ \displaystyle~n\ge 5 $ sia il minimo per cui non vale la tesi, cioè $ \displaystyle~\textrm{lcm}(b_n,b_{n-1})<2^n $. Useremo implicitamente il fatto che $ \displaystyle~b_k>\textrm{lcm}(b_{k-1},b_{k-2})\ge 2^{k-1},~\forall 2\le k\le n $.
Passo 1. Poiché $ \displaystyle~b_n>2^{n-1} $, $ \displaystyle~\textrm{lcm}(b_n,b_{n-1}) $, essendo suo multiplo minore del suo doppio, deve essere proprio $ \displaystyle~b_n $, quindi $ \displaystyle~b_{n-1}\mid b_n $. Ma se $ \displaystyle~b_n\ge 4 b_{n-1} $, $ \displaystyle~b_n>4\cdot 2^{n-2}=2^n $ assurdo. Se $ \displaystyle~b_n=2b_{n-1} $, poiché $ \displaystyle~b_n>\textrm{lcm}(b_{n-1},b_{n-2}) $ (che è multiplo di $ \displaystyle~b_{n-1} $), $ \displaystyle~\textrm{lcm}(b_{n-1},b_{n-2})=b_{n-1} $, quindi $ \displaystyle~b_{n-1}\ge 2^{n-1} $ per ipotesi e $ \displaystyle~b_n>2^n $, assurdo. Quindi $ \displaystyle~b_n=3b_{n-1} $.
Passo 2. Sempre per $ \displaystyle~b_n>\textrm{lcm}(b_{n-1},b_{n-2}) $, questo $ \displaystyle~\textrm{lcm} $ può essere solo $ \displaystyle~b_{n-1} $ o $ \displaystyle~2b_{n-1} $. Nel primo caso otteniamo un assurdo come sopra, quindi $ \displaystyle~2b_{n-1}=kb_{n-2} $ con $ \displaystyle~k>2 $ dispari (altrimenti $ \displaystyle~b_{n-2}\mid b_{n-1} $). Quindi $ \displaystyle~2^n>b_n=3b_{n-1}=\frac{3k}{2}b_{n-2}>\frac{3k}{2}\cdot 2^{n-3} $, da cui $ \displaystyle~k\le 5 $.
Se $ \displaystyle~k=3 $, $ \displaystyle~b_{n-1}=\frac{3}{2}b_{n-2} $ e $ \displaystyle~\textrm{lcm}(b_{n-2},b_{n-3})=b_{n-2} $ (deve essere $ \displaystyle~<\frac{3}{2}b_{n-2} $), quindi $ \displaystyle~b_{n-2}\ge 2^{n-2} $ e $ \displaystyle~b_n=\frac{9}{2}b_{n-2}>2^n $ assurdo. Rimane il caso $ \displaystyle~k=5 $. Non ci arrendiamo e continuiamo fiduciosi il delirio.
Passo 3. Per non cadere in un assurdo come prima, poiché $ \displaystyle~\textrm{lcm}(b_{n-2},b_{n-3})<\frac{5}{2}b_{n-2} $, deve essere $ \displaystyle~\textrm{lcm}(b_{n-2},b_{n-3})=2b_{n-2} $. Sia quindi di nuovo $ \displaystyle~2b_{n-2}=k'b_{n-3} $ con $ \displaystyle~k' $ dispari: da $ \displaystyle~2^n>b_n=\frac{15}{2}b_{n-2}=\frac{15k'}{4}b_{n-3}>\frac{15k'}{4}\cdot 2^{n-4} $ otteniamo $ \displaystyle~k'\le 4 $, cioè $ \displaystyle~k'=3 $. Finalmente essendo $ \displaystyle~b_{n-2}=\frac{3}{2}b_{n-3} $ abbiamo $ \displaystyle~\textrm{lcm}(b_{n-3},b_{n-4})=b_{n-3} $, quindi $ \displaystyle~b_{n-3}\ge 2^{n-3} $ e $ \displaystyle~b_n=\frac{45}{4}b_{n-3}\ge 45\cdot 2^{n-5}>2^n $, assurdo.
Puff pant che problema bastardo!
Aspetto conferme da Dario/Federico..

[dario2994]

Uhm, hai affrontato il problema esattamente come me, perfino stessa notazione, ma con una differenza: tu hai concluso xD
Io ero affogato in tutti i casi vari che portano alla follia (e questo mi ha impedito anche di finire la lettura della tua dimostrazione).
Comunque pur non avendo letto per filo e per segno Passo 2 e Passo 3 mi fido pienamente e ti passo l'onere di trovare un problema per la staffetta xD

[kn]

Problema 75. Mostrate che l'equazione $ \displaystyle~x^3+y^3+z^3+w^3=1999 $ ha infinite soluzioni intere.

[lilceng]

Soluzione problema 75. Per ogni $ x\in \mathbb{Z} $ vale $ (10+60x^3)^3+(10-60x^3)^3+(-60x^2)^3+(-1)^3=1999 $.

Problema76. Sia definita la sequenza $ a_1=1, a_{n+1}=a_n^4-a_n^3+2a_n^2+1 $ per ogni intero positivo $ n $. Mostrare che esistono infiniti primi che non dividono nessun termine di suddetta sequenza.

[kn]

Sia $ \displaystyle~p(x)=x^4-x^3+2x^2+1 $. Ovviamente $ \displaystyle~a_{n+1}=p(a_n) $.

Passo 1. Vale $ \displaystyle~(a_m,a_n)=a_{(m,n)} $. Prova: se $ \displaystyle~m\mid n $ abbiamo $ \displaystyle~a_{m+1}\equiv 1\equiv a_1\pmod{a_m} $ e quindi induttivamente $ \displaystyle~a_{m+k+1}\equiv p(a_k)\equiv a_{k+1}\pmod{a_m} $, dunque $ \displaystyle~a_{jm}\equiv a_m\equiv 0\pmod{a_m} $. Stessa cosa per $ \displaystyle~n\mid m $.
Se $ \displaystyle~m<n $ e $ \displaystyle~m\nmid n $ possiamo scrivere $ \displaystyle~n=jm+r $, con $ \displaystyle~0<r<m $. Per quanto detto sopra vale $ \displaystyle~a_{jm+r}\equiv a_{(j-1)m+r}\equiv\dots\equiv a_r\pmod{a_m} $. Dunque ci siamo ridotti al massimo comun divisore di $ \displaystyle~(a_m,a_r) $. Continuando questo procedimento, poiché stiamo facendo l'algoritmo di Euclide sugli indici, prima o poi arriveremo al massimo comun divisore di $ \displaystyle~(a_x,a_y) $, con $ \displaystyle~x\mid y $ e come sappiamo $ \displaystyle~x=(m,n) $.
Dunque è proprio $ \displaystyle~(a_m,a_n)=a_{(m,n)} $. (Abbiamo usato implicitamente il fatto che se $ \displaystyle~u\equiv v\pmod t $ allora $ \displaystyle~(t,u)=(t,v) $)

Passo 2. Consideriamo $ \displaystyle~a_{n+1}-a_n=a_n^4-a_n^3+2a_n^2-a_n+1=(a_n^2+1)(a_n^2-a_n+1) $ e prendiamo $ \displaystyle~p\mid a_n^2+1 $. Abbiamo $ \displaystyle~p\nmid a_n $ e $ \displaystyle~a_{n+1}\equiv{a_n}\not\equiv 0\pmod p $. Quindi $ \displaystyle~a_{n+2}\equiv p(a_n)\equiv a_{n+1}\equiv a_n\not\equiv 0\pmod p $ e così via. Dunque $ \displaystyle~p\nmid a_k~\forall k\ge n $.

Passo 3. Può essere $ \displaystyle~p\mid a_k $ per qualche $ \displaystyle~k<n $? No perché detto $ \displaystyle~b $ un intero $ \displaystyle~\ge\frac{n}{k} $ abbiamo $ \displaystyle~p\mid a_k\mid a_{bk} $ con $ \displaystyle~bk>n $ (v. passo 1). Questo è incompatibile col passo 2. Quindi $ \displaystyle~p $ è uno dei primi che cerchiamo.

Passo 4. Basta mostrare che la successione $ \displaystyle~a_n^2+1 $ ha infiniti divisori primi. Abbiamo $ \displaystyle~a_{n+1}^2+1\equiv a_n^2+1\equiv 0\pmod{a_n} $, quindi speriamo di guadagnare un primo in $ \displaystyle~a_{n+1}^2+1 $ come direbbe il grande Gobbino e facendo i conti $ \displaystyle~a_{n+1}^2+1=(a_{n+1}-a_n+a_n)^2+1 $
$ \displaystyle~=(a_n^2+1)^2(a_n^2-a_n+1)^2+2(a_n^2+1)(a_n^2-a_n+1)a_n+a_n^2+1 $$ \displaystyle~=(a_n^2+1)[(a_n^2+1)(a_n^2-a_n+1)^2+2(a_n^2-a_n+1)a_n+1] $. Ma $ \displaystyle~((a_n^2+1)(a_n^2-a_n+1)^2+2(a_n^2-a_n+1)a_n+1,a_n^2+1) $$ \displaystyle~=(2(a_n^2-a_n+1)a_n+1,a_n^2+1) $$ \displaystyle~=(-2a_n^2+1,a_n^2+1)=(3,a_n^2+1)=1 $, visto che $ \displaystyle~3\nmid a_n^2+1 $. Dunque, poiché $ \displaystyle~(a_n^2+1)(a_n^2-a_n+1)^2+2(a_n^2-a_n+1)a_n+1>1 $, $ \displaystyle~a_{n+1}^2+1 $ ha un fattore primo q che $ \displaystyle~a_n^2+1 $ non ha e, poiché abbiamo mostrato che $ \displaystyle~a_k^2+1\mid a_{k+1}^2+1 $ per ogni k, q non è nemmeno in uno dei termini precedenti della successione. Può andare?

[lilceng]

Potresti riscrivere il passo 3, disabilitando HTML? Comunque le idee ci sono tutte, anche se io non avevo osservato che era una sequenza di mersenne; in ogni caso spero di sia piaciuto. Poi vai con il prossimo

[kn]

lo disabilito di default.. ergo devo scrivere più chiaramente:
Passo 3. Può essere $ \displaystyle~p\mid a_k $ per qualche $ \displaystyle~k<n $? (il $ \displaystyle~p $ è quello del passo 2)
Risposta: No. Se così fosse, detto $ \displaystyle~b $ un intero $ \displaystyle~\ge\frac{n}{k} $, avremmo $ \displaystyle~p\mid a_k\mid a_{bk} $ (dal passo 1 abbiamo $ \displaystyle~a_k\mid a_{bk} $), ma per il $ \displaystyle~b $ che abbiamo preso è $ \displaystyle~bk\ge n $. Questo è incompatibile col passo 2 (dal quale segue che $ \displaystyle~p\nmid a_{bk} $). Quindi $ \displaystyle~p\nmid a_i~\forall i $. Più chiaro adesso?

anche se io non avevo osservato che era una sequenza di mersenne

di che trattasi?

[lilceng]

Esattamente la tua definizione: viewtopic.php?t=8138&highlight=mersenne o viewtopic.php?t=8153&highlight=mersenne ; comunque si, va bene tutto: buona giornata

[kn]

Che figata! Grazie per i link! In cambio un problema carino:
Problema 77. $ \displaystyle~\prod_{k=1}^{p-1}k^{2k-p-1} $ è intero per ogni $ \displaystyle~p $ primo