Preimo 2022 N1 [L04]

Numeri interi, divisibilità, primalità, ed equazioni a valori interi.
Rispondi
Stef2008
Messaggi: 42
Iscritto il: 08/04/2023, 19:28

Preimo 2022 N1 [L04]

Messaggio da Stef2008 »

Si dimostri che esistono infiniti interi positivi n per cui non esiste alcun intero positivo [tex]m < n[/tex] tale che [tex]m^2 + 1 | n^2 + 1.[/tex]

Posto la mia soluzione del quesito, come sempre sarò lieto se qualcuno me ne confermasse la corretteza
PS: chiedo scusa se posto così spesso problemi. Ma credo che mi sia utile per il mio allenamento.

Soluzione
Testo nascosto:
Procediamo per assurdo: supponiamo siano un numero finito pari a a k. Si [tex]M[/tex] il più grande di questi. Dall'ipotesi che siano in numero finito segue che che per ogni [tex]n>M[/tex] esiste [tex]m \leq M[/tex] tale che [tex]m^2+1| n^2+1[/tex]. Questo può essere provato per induzione. Per [tex]n=M+1[/tex] è vero dall'ipotesi di massimalità di M. Supponiamo sia vero per tutti i numeri minori di [tex]n+1[/tex] e maggiori di [tex] M[/tex]. Sappiamo che esiste un [tex]a \leq n[/tex] tale che [tex]a^2+1|(n+1)^2+1[/tex] (questo dall'ipotesi fatta all'inizio della dimostrazione); se [tex]a \leq M[/tex], si ha la tesi, altrimenti a è un numero compreso tra [tex]M+1[/tex] e [tex]n[/tex](estremi inclusi) e per ipotesi induttiva [tex]l^2+1|a^2+1|(n+1)^2+1[/tex] con [tex]l[/tex] minone o uguale a [tex]M[/tex]. Ne deriva la tesi.
Notiamo ora che i primi [tex]p_i[/tex] che dividono almeno un numero della forna [tex]m^2+1[/tex], [tex]m \leq M[/tex], sono in numero finito. Chiamiamo l'insieme di questi primi [tex]A[/tex]. Costruiamo ora un N tale che [tex]N \equiv 0 \pmod{p_i}[/tex] per ogni [tex]p_i \in A[/tex] (questo è possibile per il teorema cinese del resto). Nessun [tex]p_i[/tex] divide [tex]N^2+1[/tex] (quindi nessun [tex]m^2+1|N^2+1[/tex], [tex]m \leq M[/tex]). Questo contraddice quanto dimostrato prima, assurdo. Ne segue che esistono infiniti numeri con proprietà del testo del quesito.
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Preimo 2022 N1 [L04]

Messaggio da afullo »

Ok. Il fatto che [tex]N>M[/tex] è scontato? Naturalmente, nella costruzione di [tex]N[/tex], è possibile scegliere qualunque multiplo del mcm tra tutti i [tex]p_i[/tex] (che si riduce poi ad essere il loro prodotto, non avendo gli stessi fattori in comune), quindi lo si può costruire arbitrariamente grande...
Stef2008
Messaggi: 42
Iscritto il: 08/04/2023, 19:28

Re: Preimo 2022 N1 [L04]

Messaggio da Stef2008 »

@afullo, grazie di avermi fatto notare che avrei dovuto motivare meglio il motivo dell'assurdo (e quindi il fatto chr [tex]N>M[/tex]). Grazie mille della disponibilità, per questa volta e per le altre volte che mi hai aiutato! :D
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Preimo 2022 N1 [L04]

Messaggio da afullo »

Figurati. Siamo ancora nella coda del periodo di ferie quindi c'è un po' meno attività del solito, riprendendo la scuola dovrebbe tornare a bazzicare qualcuno di più... ;)
Cap
Messaggi: 3
Iscritto il: 18/02/2022, 17:46

Re: Preimo 2022 N1 [L04]

Messaggio da Cap »

Io ho provato in questo modo, spero sia corretto.
Testo nascosto:
Consideriamo l'insieme [tex]U[/tex] di tutti gli [tex]x[/tex] tali che per ogni [tex]y \in U[/tex], [tex]y[/tex] non divide [tex]x[/tex] e [tex]x = n^2 + 1[/tex], con [tex]x[/tex], [tex]y[/tex], [tex]n[/tex] interi positivi.
Supponiamo per assurdo che [tex]U[/tex] sia composto da un numero finito di elementi e sia [tex]X[/tex] il suo elemento più grande. Per costruzione, [tex]X = n^2 + 1[/tex] e per ipotesi [tex](n+u)^2 + 1[/tex] è divisibile per un elemento [tex]a \in U[/tex] per ogni [tex]u[/tex] intero positivo. Quindi, [tex](n+u)^2 + 1 = X + 2nu + u^2 = X + u(2n + u)[/tex]. Tuttavia, è assurdo quando [tex]u[/tex] è uguale al prodotto di tutti gli elementi di [tex]U[/tex]. Infatti, se si considerasse un [tex]a \in U[/tex], [tex]a|X + u(2n + u)[/tex] se e solo se [tex]a[/tex] divide [tex]X[/tex], ma ciò non è vero per ipotesi.
Il ragionamento è piuttosto simile e probabilmente avrei potuto anche dilungarmi un po' di più nelle spiegazioni.
Rispondi