divisibilità

[Pasquale]

Questa volta bisogna dimostrare che $2^{2n}+24n-10$ è divisibile per 18, per ogni naturale n.

[Admin]

Per $n=1$ si ottiene proprio 18.
Ora vediamo cosa succede quando n aumenta di 1;
quindi in successione, per $n=2$, $n=3$, $n=4$, ...
Si ottiene:

$n=2\quad \Rightarrow \quad r_2=18+q_2$
$n=3\quad \Rightarrow \quad r_3=r_2+q_3$
$n=4\quad \Rightarrow \quad r_4=r_3+q_4$
$\cdot \cdot \cdot$
$n=n\quad \Rightarrow \quad r_n=r_{n-1}+q_n$

dove, in generale, il termine $q_n$ è la quantità che aggiunta al risultato dell'espressione che si ottiene per $n-1$, ci da il risultato dell'espressione per $n$.
Si nota che:

$q_2=12+24$
$q_3=12\cdot 4+24$
$q_4=12\cdot 16+24$
$\cdot \cdot \cdot$

ovvero, in generale,

$q_n=12\cdot 4^{n-2}+24$

quest'ultima può essere riscritta come:

$q_n=12\cdot 4^{n-2}+6+18$

e ancora

$q_n=12\cdot (4^{n-2}-1)+12+6+18 = 12\cdot (4^{n-2}-1)+36$
ora si nota che $4^{n-2}-1$ è sempre un multiplo di 3.
Ciò appare chiaro scomponendolo in:

$4^{n-2}-1=4\cdot 3(n-3)+4-1=4\cdot 3(n-3)+3$

(in pratica, ho osservato tutti casi, ed ho generalizzato la scomposizione, ma questa scomposizione dovrebbe venir fuori anche da differenze di potenze di 2...)

Per cui, essendo $4^{n-2}-1$ sempre un multiplo di 3, e, dato che $12\cdot 3k=36k$ che è divisibile per 18, le quantità $q_n$ sono sempre divisibili per 18.
Quindi l'espressione è sempre divisibile per 18, per ogni naturale n.

Admin

[Pasquale]

Scusa Pietro, ma mi sa che c'è qualcosa che non va.
L'ultimo passaggio non mi è molto chiaro e comunque, a titolo di esempio, per n=5, l'espressione del testo dà 1134 e quella generica $q_n = 12\cdot4^{n-2}+24 = 792$

[Admin]

i risultati devono giustamente essere diversi perchè stiamo parlando di 2 quantità diverse.
Infatti, ho scritto:

$n=2 \quad\Rightarrow\quad r_2=18+q_2\\n=3 \quad\Rightarrow\quad r_3=r_{2}+q_3\\n=4 \quad\Rightarrow\quad r_4=r_{3}+q_4\\...\\n=n \quad\Rightarrow\quad r_n=r_{n-1}+q_n$

dove $r_n$ è il risultato dell'espressione per un $n$ qualsiasi.

Nel caso di n=5, si ottiene:

$n=5 \quad\Rightarrow\quad r_5=r_{4}+q_5=r_{3}+q_4+q_5=...=18+q_2+q_3+q_4+q_5$

Dimostrato che il generico termine $q_n$ è sempre divisibile per 18, ne discende che $r_n$, che è il risultato dell'espressione in esame, è sempre divisibile per 18.

Spero si capisca.

Admin

[Pasquale]

ehm, non avevo capito...io l'ho affrontato con l'aritmetica modulare.

[Tino]

Ciao,

in effetti è facile usando le congruenze e notando che $2^{2n} \equiv 2^{2k}\ mod(9)$, dove $k \equiv n\ mod(9),\ 0 \leq k \leq 8$.
Infatti $2^3 \equiv -1\ mod(9)$ e $2^{2*9}=2^{3*6}=(2^3)^6 \equiv (-1)^6=1\ mod(9)$. Ora, $2^{2n} \equiv 2^{2(9h+k)}=2^{18h}2^{2k} \equiv 2^{2k}\ mod(9)$. Tramite una verifica immediata, usando questo fatto, si vede che l'espressione è costantemente 0 sia modulo 2 che modulo 9, e quindi è 0 modulo 18, essendo 2 e 9 coprimi.

[Admin]

Ciao Tino,
in effetti quando ho detto "...questa scomposizione dovrebbe venir fuori anche da differenze di potenze di 2..." alludevo all'aritmetica modulare.

Stavo cercando di capire il tuo ragionamento ma non sono molto pratico con l'aritmetica modulare;
il fatto che:

$2^{2n} \equiv 2^{2k}\ mod(9)$, dove $k \equiv n\ mod(9),\ 0 \leq k \leq n-1$

Da cosa viene fuori?

Admin

[Tino]

Ho sbagliato a scrivere

Intendevo $0 \leq k \leq 8$, ho corretto.

Quello che ho detto credo di averlo dimostrato subito dopo, almeno spero...

Ciao

[Bruno]

...

Riguardando il topic mi è venuta quest'idea.
Fra parentesi, ho trovato interessante l'analisi di Pietro.

Osservo, innanzitutto, che l'espressione data, per ogni $\displaystyle \, n \,$ intero e positivo,
risulta senz'altro divisibile per $\displaystyle \,2$.

Dal momento che $\displaystyle \, 18 = 2\cdot 9 \,$ e i fattori appena messi in evidenza sono fra
loro primi, una volta dimostrata la divisibilità per $\displaystyle \,9\,$ di:

$\displaystyle 2^{2n}+24\cdot n-10$,

risulta pure verificata la conseguente divisibilità per $\displaystyle \, 18$.

Considero, a questo punto, il termine $\displaystyle \, {\tex \footnotesize 2^{2n}=4^n=(3+1)^n}$.
Intanto ne scrivo i primi sviluppi come segue:

$\displaystyle (3+1)^1 = 9\cdot 0+3\cdot 1+1 \\ (3+1)^2 = 9\cdot 1+3\cdot 2+1 \\ (3+1)^3 = 9\cdot 6+3\cdot 3+1$

e vedo facilmente che, supponendo che tale forma si mantenga fino a un
certo $\displaystyle \, r \,$:

$\displaystyle (3+1)^r = 9\cdot s+3\cdot r+1$

e per un opportuno $\displaystyle \, s \,$, la proprietà sarà vera anche per $\displaystyle \,r+1\,$:

$\displaystyle (3+1)^r\cdot (3+1) = (9\cdot s+3\cdot r+1)\cdot (3+1) = 9\cdot (4\cdot s+r)+3\cdot (r+1)+1 = (3+1)^{r+1}$.

Ciò significa, in sostanza, che essa vale per tutti gli esponenti interi e positivi
(principio di induzione).

In altre parole, la differenza fra $\displaystyle \,{\text \footnotesize (3+1)^n}\,$ e il triplo dell'esponente più $\displaystyle \,1\,$ è un
multiplo di $\displaystyle \,9\,$.

Il più è fatto

Ponendo in $\displaystyle \, {\tex \footnotesize 2^{2n}+24\cdot n-10},\,$ al posto di $\displaystyle \, {\text \footnotesize 2^{2n}=(3+1)^n},\,$ l'espressione $\displaystyle \,{\text \footnotesize 9\cdot t+3\cdot n+1},$
si ottiene:

$\displaystyle 2^{2n}+24\cdot n-10 = 9\cdot t+3\cdot n+1+24\cdot n-10 = 9\cdot t+27\cdot n-9$.

L'ultimo membro, evidentemente, è divisibile per $\displaystyle \, 9$.



(Bruno)

[Pasquale]

Io la cosa l'ho vista così:

1) $2^{2n}+24n-10$

$2^{2n}+24n-10 = 2\(2^{2n-1}+12n-5\)$; questo intanto ci dice che la 1) è divisibile per 2

ci resta da dimostare che:

2) $2^{2n-1}+12n-5$ è divisibile per 9

E' facile dimostrare che nell'ambito della 2):

$[2^{2n-1} - 5] (MOD 3) = [2 - 2] = 0$ (divisibile per 3)

e quindi possiamo riscrivere la 2) come:

$3k + 12n = 3(k + 4n)$; da cui si deduce che la 2) è divisibile certamente per 3 e dove:

3) $k = \frac{2^{2n-1} - 5}{3}$

Resta da vedere se (k+4n) è divisibile per 3, ma poiché 4n (MOD 3) = n, è sufficiente ed è più agevole il semplice studio di:

k + n

Dalla 3) notiamo che in Modulo 3, al variare di n, abbiamo la seguente situazione ciclica:

per n = 1, k = 2
per n = 2, k = 1
per n = 3, k = 0

in cui k risulta essere il complemento a 3 di n, per cui k+n è divisibile per 3 ed in definitiva la 1) è divisibile per 18.