Numero non divisibile per 3 - SNS 1977

[elios]

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

Ho dimostrato la prima parte attraverso il principio di induzione:
per \( \displaystyle {n}={1} \), \( \displaystyle {N}={2} \) che non è divisibile per 3.
Per \( \displaystyle {n}+{1} \), si ha \( \displaystyle {N}={{\left({n}+{1}\right)}}^{{2}}+{1}={{n}}^{{2}}+{2}{n}+{1}+{1}={\left({{n}}^{{2}}+{1}\right)}+{\left({2}{n}+{1}\right)} \)
La prima parentesi per ipotesi induttiva è non divisibile per 3. Se un numero (in questo caso \( \displaystyle {{n}}^{{2}}+{1} \)) è non divisibile per tre, allora lo è o \( \displaystyle {\left({{n}}^{{2}}+{1}\right)}+{1} \) o \( \displaystyle {\left({{n}}^{{2}}+{1}\right)}+{2} \). Ma per nessun intero positivo \( \displaystyle {n} \), \( \displaystyle {\left({2}{n}+{1}\right)}={1} \) oppure \( \displaystyle {\left({2}{n}+{1}\right)}={2} \), quindi la somma \( \displaystyle {\left({{n}}^{{2}}+{1}\right)}+{\left({2}{n}+{1}\right)} \) 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.

[elios]

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

Quindi le soluzioni si hanno per \( \displaystyle {s} \) dispari, e gli \( \displaystyle {n} \) che rendono verificata la richiesta sono quelli del tipo \( \displaystyle {n}={3}{t}+{2} \), con \( \displaystyle {t} \) numeri interi positivi.

[Thomas]

La prima parentesi per ipotesi induttiva è non divisibile per 3. Se un numero (in questo caso \( \displaystyle {{n}}^{{2}}+{1} \)) è non divisibile per tre, allora lo è o \( \displaystyle {\left({{n}}^{{2}}+{1}\right)}+{1} \) o \( \displaystyle {\left({{n}}^{{2}}+{1}\right)}+{2} \). Ma per nessun intero positivo \( \displaystyle {n} \), \( \displaystyle {\left({2}{n}+{1}\right)}={1} \) oppure \( \displaystyle {\left({2}{n}+{1}\right)}={2} \), quindi la somma \( \displaystyle {\left({{n}}^{{2}}+{1}\right)}+{\left({2}{n}+{1}\right)} \) 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...

[Gatto89]

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 \( \displaystyle {n} \) si può scrivere nella forma \( \displaystyle {3}{k} \), \( \displaystyle {3}{k}+{1} \) o \( \displaystyle {3}{k}+{2} \) per un opportuno k intero e prova a vedere cosa succede a ognuno di questi numeri quando fai \( \displaystyle {{n}}^{{2}}+{1} \).

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

Per il caso pari, ragionamento uguale.

Per il caso dispari:

1) Se \( \displaystyle {n}\equiv{0}{\left(\text{mod}\right.} \) \( \displaystyle {3}\) \) hai che \( \displaystyle {{n}}^{{{2}{k}+{1}}}+{1}\equiv{1}{\left(\text{mod}\right.} \) \( \displaystyle {3}\) \) quindi non ci sono soluzioni.

2) Se \( \displaystyle {n}\ne{0}{\left(\text{mod}\right.} \) \( \displaystyle {3}\) \), allora \( \displaystyle {{n}}^{{2}}\equiv{1}{\left(\text{mod}\right.} \) \( \displaystyle {3}\) \) e \( \displaystyle {{n}}^{{{2}{k}+{1}}}+{1}\equiv{n}+{1}{\left(\text{mod}\right.} \) \( \displaystyle {3}\) \) e quindi le soluzioni sono \( \displaystyle {n}\equiv{2}{\left(\text{mod}\right.} \) \( \displaystyle {3}\) \).

[elios]

Sì, quindi posso scrivere \( \displaystyle {{\left({3}{k}\right)}}^{{2}}+{1}\equiv{0}+{1}\equiv{1}{\left(\text{mod}{3}\right)} \)
\( \displaystyle {{\left({3}{k}+{1}\right)}}^{{2}}+{1}\equiv{9}{{k}}^{{2}}+{6}{k}+{1}+{1}\equiv{0}+{0}+{2}\equiv{2}{\left(\text{mod}{3}\right)} \)
\( \displaystyle {{\left({3}{k}+{2}\right)}}^{{2}}+{1}\equiv{9}{{k}}^{{2}}+{12}{k}+{4}+{1}\equiv{0}+{0}+{2}\equiv{2}{\left(\text{mod}{3}\right)} \)

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

[Gatto89]

Sì, quindi posso scrivere \( \displaystyle {{\left({3}{k}\right)}}^{{2}}+{1}\equiv{0}+{1}\equiv{1}{\left(\text{mod}{3}\right)} \)
\( \displaystyle {{\left({3}{k}+{1}\right)}}^{{2}}+{1}\equiv{9}{{k}}^{{2}}+{6}{k}+{1}+{1}\equiv{0}+{0}+{2}\equiv{2}{\left(\text{mod}{3}\right)} \)
\( \displaystyle {{\left({3}{k}+{2}\right)}}^{{2}}+{1}\equiv{9}{{k}}^{{2}}+{12}{k}+{4}+{1}\equiv{0}+{0}+{2}\equiv{2}{\left(\text{mod}{3}\right)} \)

Esattamente... così l'hai dimostrato per ogni \( \displaystyle {n} \)

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

La parte con \( \displaystyle {s} \) pari come ho detto non l'ho messa perchè è identica alla tua... per la parte con \( \displaystyle {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 \( \displaystyle {6}{k}+{5} \)).

[elios]

perché \( \displaystyle {6}{k}+{5} \) e non \( \displaystyle {3}{k}+{2} \)?

[Gatto89]

Si scusa volevo dire \( \displaystyle {3}{k}+{2} \)

[elios]

Perfetto, tutto chiaro ora. Grazie dell'aiuto!