Divisibilità per 3

[Denny]

Ciao a tutti..... come posso dimostrare che (2^n+1)(2^n-1) è sempre divisibile per 3?

[ndp15]

Ciao a tutti..... come posso dimostrare che (2^n+1)(2^n-1) è sempre divisibile per 3?

Ragionando!
Non serve nessuna tecnica, considera come sono i due fattori che compaiono.

[fraboz]

l'esercizio è molto semplice quindi se guardi l'hint è come se lo avessi risolto . e comunque ascolta prima il consiglio di ndp15 che è più saggio di me sicuramente

hint:

Testo nascosto:

$ mod 3 $

[Drago96]

Penso che la soluzione sia questa:

Testo nascosto:

Osservo che:
$ \displaystyle{2^n \equiv 1 \ (mod \ 3)} $ se n è pari
$ \displaystyle{2^n \equiv 2 \ (mod \ 3)} $ se n è dispari
Esamino il caso n pari: $ \displaystyle{{(2^n + 1)} \cdot {(2^n - 1)} \equiv 2 \cdot 0 \equiv 0 \ (mod \ 3)} $
Il caso n dispari: $ \displaystyle{{(2^n + 1)} \cdot {(2^n - 1)} \equiv 0 \cdot 1 \equiv 0 \ (mod \ 3)} $
CVD

EDIT: Ho notato una soluzione molto più breve:

Testo nascosto:

$ \displaystyle{{(2^n + 1)} \cdot {(2^n - 1)} = 2^{2n} - 1} $
Ovviamente $ 2n $ è pari, perciò dall'osservazione di prima ho che:
$ \displaystyle{2^{2n} - 1 \equiv 1 - 1 \equiv 0 \ (mod \ 3)} $

[jordan]

$ (2^n-1)(2^n+1)=4^n-1=(3+1)^n-1= $ $ \displaystyle \sum_{0\le i\le n}{\binom{n}{i}3^i}-1 =\sum_{1\le i\le n}{\binom{n}{i}3^i}= 3\left( \sum_{1\le i\le n}{\binom{n}{i}3^{i-1}}\right) $

[Denny]

Chiedo scusa per l'ignoranza... ma potrei avere l'equivalente discorsivo? Grazie

[fraboz]

tanto per non complicarsi la vita jordan ha usato il binomiale di Newton http://it.wikipedia.org/wiki/Teorema_binomiale

[Denny]

ahem... questo mi lascia quasi nella stessa situazione....

[Drago96]

Chiedo scusa per l'ignoranza... ma potrei avere l'equivalente discorsivo? Grazie

Jordan ha usato il binomio di Newton e poi delle proprietà delle sommatorie per raccogliere a fattore 3...

Invece io ho usato le congruenze... (e mi sono accorto che nella seconda soluzione si può fare anche con le potenze di 4)
Così sarebbe:
$ \displaystyle{(2^n + 1) \cdot (2^n - 1) = 4^n - 1} $
Osservo che tutte le potenze di 4 sono $ \equiv 1 \ (mod \ 3) $
Perciò $ \displaystyle{4^n - 1 \equiv 1 - 1 \equiv 0 \ (mod \ 3)} $

[matty96]

Credo sia giusta la prima: $(2^n)^2=2^{2n} \not = 4^{2n}=(4^n)^2$

[Denny]

già... (2^n)^2=2^2n... lol.
Il problema è che non so leggere la dimostrazione... so che n mod x da il resto della divisione... ma poi? XD

[Drago96]

Credo sia giusta la prima: $(2^n)^2=2^{2n} \not = 4^{2n}=(4^n)^2$

Sì, oppure $ (2^n)^2 = 4^n $...
Devo aver fatto un mix tra lo svolgimento di jordan e il mio, creando questa atrocità...
Comunque le potenze di 4 sono sempre $ \equiv 1 \ (mod \ 3) $, e in questo caso l'esponente non importava molto...

Il problema è che non so leggere la dimostrazione... so che n mod x da il resto della divisione... ma poi? XD

Beh, se hai un'espressione che ha come resto 0, vuol dire che è divisibile per il numero con cui fai le congruenze...
Ad esempio $ 2 \cdot 4 \equiv 2 \cdot 1 \equiv 2 \ (mod \ 3) $
Infatti 8 non è divisibile per tre...
Mentre $ 2 + 4 \equiv 2 + 1 \equiv 3 \equiv 0 $ Infatti 6 è divisibile per 3

[matty96]

Allora dovresti modificare quel messaggio, comunque la soluzione è sostanzialmente la stessa

[Denny]

Ok, ho scoperto che stavate parlando di aritmetica modulare... da quanto ho capito da wikipedia... ecco perchè non ci capivo assolutamente nulla

[matty96]

già... (2^n)^2=2^2n... lol.
Il problema è che non so leggere la dimostrazione... so che n mod x da il resto della divisione... ma poi? XD

Ok.....tu sai che $2 \equiv -1 \pmod 3$, quindi $2^n \equiv (-1)^n \pmod 3$.Se n è pari, significa che $2^n \equiv 1 \pmod 3$ perchè un numero negativo elevato ad un esponente pari è positivo.Il testo del problema dice che deve valere $2^{2n} -1 \equiv 0 \pmod 3$, che è vero poichè $2^{2n}-1 \equiv 1-1 = 0 \pmod 3$ (nota che 2n è pari).Chiaro ora?