Numero non divisibile per 3 - SNS 1977

Messaggioda elios » 26/10/2009, 18:04

"Dimostrare che, per ogni intero positivo $n$, il numero $N=n^2+1$ non è divisibile per 3.
Facoltativo: dire per quali interi positivi $s$ esistono interi $n$ tali che $n^s+1$ è divisibile per 3".

Ho dimostrato la prima parte attraverso il principio di induzione:
per $n=1$, $N=2$ che non è divisibile per 3.
Per $n+1$, si ha $N=(n+1)^2+1=n^2+2n+1+1=(n^2+1) + (2n+1)$
La prima parentesi per ipotesi induttiva è non divisibile per 3. Se un numero (in questo caso $n^2+1$) è non divisibile per tre, allora lo è o $(n^2+1)+1$ o $(n^2+1)+2$. Ma per nessun intero positivo $n$, $(2n+1)=1$ oppure $(2n+1)=2$, quindi la somma $(n^2+1)+(2n+1)$ non è divisibile per 3.

Per la seconda parte, non credo sia plausibile fare con il principio di induzione, ma non so bene come andare avanti.. Come faccio a sfruttare il criterio di divisibilità per 3?

Grazie dell'aiuto.
L'egoista è una persona di cattivo gusto, più interessata a se stessa, che a me. (Ambrose Bierce)
elios
Average Member
Average Member
 
Messaggio: 803 di 937
Iscritto il: 05/10/2007, 19:25
Località: Ascoli Piceno

Messaggioda elios » 28/10/2009, 15:46

Forse ho trovato un modo per risolvere la seconda parte:
se $s$ è pari, allora $s=2k$, $n^s+1=n^(2k)+1=(n^k)^2+1$ e ponendo $N=n^k$, si avrebbe $N^2+1$, che è il caso che ho già dimostrato essere non divisibile per 3.
se $s$ è dispari, allora $s=2k+1$, $n^s+1=n^(2k+1)+1=n^(2k)*n+1=n(n^(2k)+1/n)=n[(n^(2k)+1)-1+1/n]=n(n^(2k)+1)-n+1$
Ricordando che ho già dimostrato che $(n^(2k)+1)$ non è divisibile per 3:
se $n$ non è multiplo di 3, allora $n(n^(2k)+1)$ non è divisibile per 3, e affinché $n(n^(2k)+1)-n+1$ lo sia, per lo stesso ragionamento fatto per la prima parte dell'esercizio, $-n+1$ deve essere uguale o a -1 o a -2 (non a +1 o +2 perché $-n+1$ è sicuramente un numero negativo). Quindi $-n+1=-1$ si ha per $n=2$ e $-n+1=-2$ si ha per $n=3$, non accettabile.
se $n$ è multiplo di 3, allora $n(n^(2k)+1)$ è divisibile per 3, e quindi $-n+1$ deve essere divisibile per 3: $-n+1=-3h$, $n=3h+1$, che è impossibile per un $n$ divisibile per 3.

Quindi le soluzioni si hanno per $s$ dispari, e gli $n$ che rendono verificata la richiesta sono quelli del tipo $n=3t+2$, con $t$ numeri interi positivi.
L'egoista è una persona di cattivo gusto, più interessata a se stessa, che a me. (Ambrose Bierce)
elios
Average Member
Average Member
 
Messaggio: 805 di 937
Iscritto il: 05/10/2007, 19:25
Località: Ascoli Piceno

Re: Numero non divisibile per 3 - SNS 1977

Messaggioda Thomas » 28/10/2009, 15:54

elios ha scritto:La prima parentesi per ipotesi induttiva è non divisibile per 3. Se un numero (in questo caso $n^2+1$) è non divisibile per tre, allora lo è o $(n^2+1)+1$ o $(n^2+1)+2$. Ma per nessun intero positivo $n$, $(2n+1)=1$ oppure $(2n+1)=2$, quindi la somma $(n^2+1)+(2n+1)$ non è divisibile per 3.


non capisco le implicazioni logiche... n è fissato e stai affermando che visto che uno tra quei due numeri è divisibile per tre allora se un numero è divisibile per 3 deve essere per forza uno di quei due numeri?

se è così c'è qualche falla... :lol:
Thomas
Advanced Member
Advanced Member
 
Messaggio: 1580 di 2223
Iscritto il: 28/09/2002, 21:44

Re: Numero non divisibile per 3 - SNS 1977

Messaggioda Gatto89 » 28/10/2009, 18:25

Si, chiaramente c'è quella falla nella dimostrazione non facilmente sopperibile... io ti consiglio di usare la congruenza modulo 3 (è un SNS quindi si presuppone le si debba conoscere e usare).

Se proprio non hai fatto le congruenze, ogni numero $n$ si può scrivere nella forma $3k$, $3k+1$ o $3k+2$ per un opportuno k intero e prova a vedere cosa succede a ognuno di questi numeri quando fai $n^2+1$.

La seconda parte mi sembra giusta (anche se un pò impicciata :P), sempre nel caso hai fatto le congruenze puoi dire:

Per il caso pari, ragionamento uguale.

Per il caso dispari:

1) Se $n\equiv 0 (mod$ $3)$ hai che $n^(2k+1) +1 \equiv 1 (mod$ $3)$ quindi non ci sono soluzioni.

2) Se $n != 0 (mod$ $3)$, allora $n^2 \equiv 1 (mod$ $3)$ e $n^(2k+1) + 1 \equiv n + 1 (mod$ $3)$ e quindi le soluzioni sono $n \equiv 2 (mod$ $3)$.
"La reductio ad absurdum è una delle più belle armi di un matematico. È un gambetto molto più raffinato di qualsiasi gambetto degli scacchi: un giocatore di scacchi può offrire in sacrificio un pedone o anche qualche altro pezzo, ma il matematico offre la partita."
Avatar utente
Gatto89
Senior Member
Senior Member
 
Messaggio: 991 di 1760
Iscritto il: 26/05/2008, 15:59

Messaggioda elios » 28/10/2009, 20:26

Sì, quindi posso scrivere $(3k)^2+1\equiv 0+1\equiv 1 (mod3)$
$(3k+1)^2+1 \equiv 9k^2+6k+1+1 \equiv 0+0+2 \equiv 2 (mod3)$
$(3k+2)^2+1\equiv 9k^2+12k+4+1 \equiv 0+0+2 \equiv 2 (mod3)$

@Gatto89, nella soluzione che mi hai corretto sono sottointesi i miei ragionamenti, oppure basta ciò che hai scritto tu?
L'egoista è una persona di cattivo gusto, più interessata a se stessa, che a me. (Ambrose Bierce)
elios
Average Member
Average Member
 
Messaggio: 806 di 937
Iscritto il: 05/10/2007, 19:25
Località: Ascoli Piceno

Messaggioda Gatto89 » 28/10/2009, 20:37

elios ha scritto:Sì, quindi posso scrivere $(3k)^2+1\equiv 0+1\equiv 1 (mod3)$
$(3k+1)^2+1 \equiv 9k^2+6k+1+1 \equiv 0+0+2 \equiv 2 (mod3)$
$(3k+2)^2+1\equiv 9k^2+12k+4+1 \equiv 0+0+2 \equiv 2 (mod3)$

Esattamente... così l'hai dimostrato per ogni $n$ ;)


elios ha scritto:@Gatto89, nella soluzione che mi hai corretto sono sottointesi i miei ragionamenti, oppure basta ciò che hai scritto tu?


La parte con $s$ pari come ho detto non l'ho messa perchè è identica alla tua... per la parte con $s$ dispari basta quello scritto, dopotutto è la dimostrazione che tutti e soli i numeri che rispecchiano sono di quella forma (al massimo compatti il tutto dicendo che sono i numeri della forma $6k + 5$).
"La reductio ad absurdum è una delle più belle armi di un matematico. È un gambetto molto più raffinato di qualsiasi gambetto degli scacchi: un giocatore di scacchi può offrire in sacrificio un pedone o anche qualche altro pezzo, ma il matematico offre la partita."
Avatar utente
Gatto89
Senior Member
Senior Member
 
Messaggio: 993 di 1760
Iscritto il: 26/05/2008, 15:59

Messaggioda elios » 28/10/2009, 20:39

perché $6k+5$ e non $3k+2$?
L'egoista è una persona di cattivo gusto, più interessata a se stessa, che a me. (Ambrose Bierce)
elios
Average Member
Average Member
 
Messaggio: 807 di 937
Iscritto il: 05/10/2007, 19:25
Località: Ascoli Piceno

Messaggioda Gatto89 » 28/10/2009, 20:50

Si scusa volevo dire $3k + 2$ :-D
"La reductio ad absurdum è una delle più belle armi di un matematico. È un gambetto molto più raffinato di qualsiasi gambetto degli scacchi: un giocatore di scacchi può offrire in sacrificio un pedone o anche qualche altro pezzo, ma il matematico offre la partita."
Avatar utente
Gatto89
Senior Member
Senior Member
 
Messaggio: 994 di 1760
Iscritto il: 26/05/2008, 15:59

Messaggioda elios » 28/10/2009, 20:53

Perfetto, tutto chiaro ora. Grazie dell'aiuto!
L'egoista è una persona di cattivo gusto, più interessata a se stessa, che a me. (Ambrose Bierce)
elios
Average Member
Average Member
 
Messaggio: 808 di 937
Iscritto il: 05/10/2007, 19:25
Località: Ascoli Piceno

Re: Numero non divisibile per 3 - SNS 1977

Messaggioda Caligola » 17/12/2012, 20:54

Premetto che sono nuovo quindi perdonatemi se commetto qualche errore nonostante abbia letto il regolamento.
Ho provato a dare una dimostrazione della prima parte del problema diversa rispetto a quella proposta da voi, e volevo sapere se il ragionamento che ho fatto fosse corretto anche perchè c'è un passaggio di cui non riesco a convincermi.

Se per assurdo \(\ n^2+1 \) è divisibile per 3, allora \(\ \frac{n^2+1}{3}\ \in \mathbb{N} \), quindi \(\ n^2+1 \) è un multiplo di 3 e quindi nella forma \(\ 3q \) con \(\ q \in \mathbb{N} \). Pertanto \(\ n^2+1 = 3q \) quindi \(\ 3q-1 \) è un quadrato perfetto e soddisfa la proprietà secondo cui la differenza tra due quadrati perfetti consecutivi \(\ n^2 - (n-1)^2 \) è esattamente uguale a \(\ 2n-1 \), quindi anche \(\ 3q-1 - (3(q-1)-1) = 2q -1 \) (questo passaggio che faccio non mi convince), da cui segue \(\ q=1 \) e quindi \(\ n^2 = 3q-1 \Rightarrow n^2=2 \Rightarrow n= \sqrt{2} \) che non appartiene ai numeri Interi, il che è contro l'ipotesi \(\ n \in \mathbb{N} \) e l'assurdo deriva dall'aver asserito \(\ \frac{n^2+1}{3}\ \in \mathbb{N} \), quindi \(\ n^2+1 \) non è divisibile per 3.
Caligola
Starting Member
Starting Member
 
Messaggio: 1 di 2
Iscritto il: 17/12/2012, 20:18

Prossimo

Torna a Pensare un po' di più

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite