trova il più grande comune divisiore della sequenza:
$ 16^{n} +10n-1 $
con n=1,2,....
MCD di una sequenza
Uhm... provo n=1 da cui si ricava che MCD della serie divide 25.
Ora dimostro che 25 divide ogni elemento della serie.
Per farlo analizzo $ $16^n\pmod 25 $:
$ $n\equiv 0\pmod{5}\Rightarrow 16^n\equiv 1\pmod{25} $
$ $n\equiv 1\pmod{5}\Rightarrow 16^n\equiv 16\pmod{25} $
$ $n\equiv 2\pmod{5}\Rightarrow 16^n\equiv 6\pmod{25} $
$ $n\equiv 3\pmod{5}\Rightarrow 16^n\equiv 21\pmod{25} $
$ $n\equiv 4\pmod{5}\Rightarrow 16^n\equiv 11\pmod{25} $
Ora analizzo $ $10n\pmod{25} $ (notando che n=5 e n=0 danno lo stesso risultato):
$ $n\equiv 0\pmod{5}\Rightarrow 10n\equiv 0\pmod{25} $
$ $n\equiv 1\pmod{5}\Rightarrow 10n\equiv 10\pmod{25} $
$ $n\equiv 2\pmod{5}\Rightarrow 10n\equiv 20\pmod{25} $
$ $n\equiv 3\pmod{5}\Rightarrow 10n\equiv 5\pmod{25} $
$ $n\equiv 4\pmod{5}\Rightarrow 10n\equiv 15\pmod{25} $
Da cui ovviamente si ottiene che 25 divide ogni elemento della serie (basta dividere sempre nei casi in base alla congruenza modulo 25 e svolgere le somme).
Tanto per dare un senso a questo post do una dritta per questo genere di esercizi... che sono quasi meccanici.
Il tipo di esercizi che intendo è quello in cui si deve trovare MCD di una successione o di un polinomio (o di un esponenziale) valutata negli interi.
Se l'esercizio è semplice di solito basta guardare i primi 2-3 termini per trovare l'MCD (che di solito è formato da 2-3 primi bassi elevati a una potenza) e una volta identificato si devono analizzare tutti i termini e dimostrare che tutti sono divisibili per quel numero. In generale i metodi sono 2 o si analizza modulo tutti i primi (elevati alla relativa potenza) oppure si usa il teorema di fermat che spesso può far comodo in questi casi.
Un esempio istruttivo (me lo sono inventato sul momento... ma comunque non è malaccio xD) è:
Trovare il massimo k tale che $ $k|(n^7-n)\ \forall\ n\in \mathbb{N} $
EDIT: sono un pirla... mi sono appena accorto che l'esercizio che ho postato sta anche nel thread "qualcosa sui primi" xD Vabbè... diciamo che per dare l'idea xD
Ora dimostro che 25 divide ogni elemento della serie.
Per farlo analizzo $ $16^n\pmod 25 $:
$ $n\equiv 0\pmod{5}\Rightarrow 16^n\equiv 1\pmod{25} $
$ $n\equiv 1\pmod{5}\Rightarrow 16^n\equiv 16\pmod{25} $
$ $n\equiv 2\pmod{5}\Rightarrow 16^n\equiv 6\pmod{25} $
$ $n\equiv 3\pmod{5}\Rightarrow 16^n\equiv 21\pmod{25} $
$ $n\equiv 4\pmod{5}\Rightarrow 16^n\equiv 11\pmod{25} $
Ora analizzo $ $10n\pmod{25} $ (notando che n=5 e n=0 danno lo stesso risultato):
$ $n\equiv 0\pmod{5}\Rightarrow 10n\equiv 0\pmod{25} $
$ $n\equiv 1\pmod{5}\Rightarrow 10n\equiv 10\pmod{25} $
$ $n\equiv 2\pmod{5}\Rightarrow 10n\equiv 20\pmod{25} $
$ $n\equiv 3\pmod{5}\Rightarrow 10n\equiv 5\pmod{25} $
$ $n\equiv 4\pmod{5}\Rightarrow 10n\equiv 15\pmod{25} $
Da cui ovviamente si ottiene che 25 divide ogni elemento della serie (basta dividere sempre nei casi in base alla congruenza modulo 25 e svolgere le somme).
Tanto per dare un senso a questo post do una dritta per questo genere di esercizi... che sono quasi meccanici.
Il tipo di esercizi che intendo è quello in cui si deve trovare MCD di una successione o di un polinomio (o di un esponenziale) valutata negli interi.
Se l'esercizio è semplice di solito basta guardare i primi 2-3 termini per trovare l'MCD (che di solito è formato da 2-3 primi bassi elevati a una potenza) e una volta identificato si devono analizzare tutti i termini e dimostrare che tutti sono divisibili per quel numero. In generale i metodi sono 2 o si analizza modulo tutti i primi (elevati alla relativa potenza) oppure si usa il teorema di fermat che spesso può far comodo in questi casi.
Un esempio istruttivo (me lo sono inventato sul momento... ma comunque non è malaccio xD) è:
Trovare il massimo k tale che $ $k|(n^7-n)\ \forall\ n\in \mathbb{N} $
EDIT: sono un pirla... mi sono appena accorto che l'esercizio che ho postato sta anche nel thread "qualcosa sui primi" xD Vabbè... diciamo che per dare l'idea xD
Mumble... in effetti tutti i conti osceni erano evitabili, tanto per continuare la spiegazione di prima risolvo anche per induzione, che è un altro dei metodi per risolvere questo genere di esercizi.
Il passo base è quasi ovvio $ $25|16+10-1 $
Ora partendo da
$ $25|16^n+10n-1 $
dimostro che è vero anche per n+1.
Per farlo intanto noto:
$ $16^n\equiv 1-10n \pmod{25} $
Da cui ottengo
$ 16^{n+1}+10(n+1)-1\equiv 16(1-10n)+10(n+1)-1\equiv 16-160n+10n+10-1\equiv 25+150n\equiv 25(1+6n)\equiv 0\pmod{25} $
Questa soluzione è indubbiamente molto più elegante della precedente e da un idea di come si può sfruttare l'induzione: dal passo induttivo si ricava una qualche congruenza e poi sostituendo nel passo successivo si ottiene una cosa vera per ogni n :)
Il passo base è quasi ovvio $ $25|16+10-1 $
Ora partendo da
$ $25|16^n+10n-1 $
dimostro che è vero anche per n+1.
Per farlo intanto noto:
$ $16^n\equiv 1-10n \pmod{25} $
Da cui ottengo
$ 16^{n+1}+10(n+1)-1\equiv 16(1-10n)+10(n+1)-1\equiv 16-160n+10n+10-1\equiv 25+150n\equiv 25(1+6n)\equiv 0\pmod{25} $
Questa soluzione è indubbiamente molto più elegante della precedente e da un idea di come si può sfruttare l'induzione: dal passo induttivo si ricava una qualche congruenza e poi sostituendo nel passo successivo si ottiene una cosa vera per ogni n :)
grazieSi si lo so sto facendo necromancing 
sempre meglio che aprire un topic nuovo no?
Volevo chiedere se è sbagliata questa dimostrazione per induzione.
Per n=1 mcd=25.
Ora, supponendo che $ 25 | 16^n+10n-1 $, sottraggo le espressioni per n-1 e n. $ 16^{n+1}+10(n+1)-1-16^n-10n+1 = 16^n(15)+10 $ Guardando il risultato mod 25 noto che $ 16^n\equiv 1 \pmod{25} \Rightarrow 15+10 \equiv 0 \pmod{25} $
La posto perchè è un modo di ragionare per induzione che non avevo mai provato e quindi suppongo che non sia corretto concettualmente
sempre meglio che aprire un topic nuovo no?Volevo chiedere se è sbagliata questa dimostrazione per induzione.
Per n=1 mcd=25.
Ora, supponendo che $ 25 | 16^n+10n-1 $, sottraggo le espressioni per n-1 e n. $ 16^{n+1}+10(n+1)-1-16^n-10n+1 = 16^n(15)+10 $ Guardando il risultato mod 25 noto che $ 16^n\equiv 1 \pmod{25} \Rightarrow 15+10 \equiv 0 \pmod{25} $
La posto perchè è un modo di ragionare per induzione che non avevo mai provato e quindi suppongo che non sia corretto concettualmente
Questa parte è sbagliata. Devi dimostrare che $ 25\mid 16^n\cdot 15+10 $ che è equivalente a $ 5\mid 16^n\cdot 3+2 $, che è equivalente a $ 5\mid 2(16^n\cdot 3+2)-5 $ cioè $ 5\mid 16^n-1 $ che adesso è banale. Il resto è giusto.Sonner ha scritto:Guardando il risultato mod 25 noto che $ 16^n\equiv 1 \pmod{25} \Rightarrow 15+10 \equiv 0 \pmod{25} $
La mia soluzione (non ho le letto le altre). Sia $ x_n:=16^n+10n-1 $ e sia $ y:=\text{gcd}(x_1,x_2,\ldots) $. In particolare $ y\mid x_1=25 $. Ora in $ \mathbb{Z}/25\mathbb{Z} $ vale $ x_n=(3\cdot 5+1)^n+(10n-1)=(15n+1)+(10n-1)=0 $. []
The only goal of science is the honor of the human spirit.