Dimostrare per induzione congruenza potenze
Salve, non riesco a capire come ragionare su questa tipologia di esercizio.
L'esercizio chiede di dimostrare che tutte le potenze n-esime di $6$ per $n >= 1$ sono congrue a $6(mod10)$
Credo che l'esercizio va risolto con il principio di induzione ma con le congruenze di mezzo non ho ben capito come si fa. Io faccio così:
Passo base $(n = 1)$:
$6^1-=6(mod10)$ vero?
poi non so come continuare.
L'esercizio chiede di dimostrare che tutte le potenze n-esime di $6$ per $n >= 1$ sono congrue a $6(mod10)$
Credo che l'esercizio va risolto con il principio di induzione ma con le congruenze di mezzo non ho ben capito come si fa. Io faccio così:
Passo base $(n = 1)$:
$6^1-=6(mod10)$ vero?
poi non so come continuare.
Risposte
Devi usare l'induzione per forza?
Non saprei, nella soluzione dell'esercizio postata dal prof. dice di procedere per induzione. La soluzione è questa ma non ho capito come ci si è arrivato:
Osserviamo che $6^1 = 6$
Supponiamo che $6^n-=6(mod10)$
Allora $6^(n+1)=66^n-=66(mod10)=36(mod10)-=6(mod10)$
Osserviamo che $6^1 = 6$
Supponiamo che $6^n-=6(mod10)$
Allora $6^(n+1)=66^n-=66(mod10)=36(mod10)-=6(mod10)$
Allora ... il passo base lo hai già dimostrato, passiamo al passo induttivo ...
Per ipotesi $6^n-=6\ (mod 10)$ che significa $a*10+6-=6\ (mod 10)$; si deve dimostrare che $6^(n+1)-=6\ (mod10)$
Dato che $6^(n+1)=6^n*6=6a*10+36$ è evidente che la tesi è dimostrata.
Cordialmente, Alex
Per ipotesi $6^n-=6\ (mod 10)$ che significa $a*10+6-=6\ (mod 10)$; si deve dimostrare che $6^(n+1)-=6\ (mod10)$
Dato che $6^(n+1)=6^n*6=6a*10+36$ è evidente che la tesi è dimostrata.
Cordialmente, Alex
Il passo base sarebbe $6^1=6$ giusto?
Perchè $6^n$ significa $a*10+6$ ?
Perchè $6^n$ significa $a*10+6$ ?
Se un numero è congruente a $6$ modulo $10$ significa che dividendolo per dieci dà come resto sei, ok?
Di conseguenza è un numero che termina con la cifra $6$ cioè un numero di decine qualsiasi ($a*10$) più sei.
Di conseguenza è un numero che termina con la cifra $6$ cioè un numero di decine qualsiasi ($a*10$) più sei.
Si possono anche usare le sole proprietà elementari delle congruenze.
Per ipotesi induttiva è \( 6^{n} \equiv 6 \pmod{10} \). Ma le congruenze sono invarianti per le moltiplicazioni, i.e. se è \( a \equiv b \pmod{n} \) allora è anche \( a \cdot c \equiv b \cdot c \pmod{n} \), sicché, nella fattispecie, è \( 6^{n} \cdot 6 \equiv 6 \cdot 6 \pmod{10} \). Ma poiché è \( 6 \cdot 6 = 36 \equiv 6 \pmod{10} \), allora per la transitività delle congruenze è \( 6^{n} \cdot 6 = 6^{n+1} \equiv 6 \pmod{10} \).
Per ipotesi induttiva è \( 6^{n} \equiv 6 \pmod{10} \). Ma le congruenze sono invarianti per le moltiplicazioni, i.e. se è \( a \equiv b \pmod{n} \) allora è anche \( a \cdot c \equiv b \cdot c \pmod{n} \), sicché, nella fattispecie, è \( 6^{n} \cdot 6 \equiv 6 \cdot 6 \pmod{10} \). Ma poiché è \( 6 \cdot 6 = 36 \equiv 6 \pmod{10} \), allora per la transitività delle congruenze è \( 6^{n} \cdot 6 = 6^{n+1} \equiv 6 \pmod{10} \).
Voleva l'induzione ... 
Altrimenti si vede facilmente che la cifra delle unità di un prodotto dipende solo dal prodotto delle cifre delle unità dei fattori e dato che sei per sei fa trentasei, si entra in un loop infinito ...
Altrimenti si vede facilmente che la cifra delle unità di un prodotto dipende solo dal prodotto delle cifre delle unità dei fattori e dato che sei per sei fa trentasei, si entra in un loop infinito ...
Sì lo so che voleva l'induzione.
L'abbiamo usata entrambi: tu sulla scrittura del numero, io sul \( 6^{n} \).
L'abbiamo usata entrambi: tu sulla scrittura del numero, io sul \( 6^{n} \).
Riprendo un attimo la discussione. Ho svolto praticamente un esercizio simile, non so però se è fatto bene. L'esercizio chiede di dimostrare che tutte le potenze di 5 sono congrue a 5 modulo 10.
Quindi credo bisogna dimostrare che:
$5^n-=5(mod10)$ per ogni $n>=1$
Io l'ho svolto così:
$5^1=5-=5(mod10)$
Supponiamo vera $5^n-=5(mod10)$
Allora:
$5^(n+1)=5^n*5-=5*5(mod10)=25(mod10)-=5(mod10)$
E' corretto? Sono abbastanza dubbioso.
Quindi credo bisogna dimostrare che:
$5^n-=5(mod10)$ per ogni $n>=1$
Io l'ho svolto così:
$5^1=5-=5(mod10)$
Supponiamo vera $5^n-=5(mod10)$
Allora:
$5^(n+1)=5^n*5-=5*5(mod10)=25(mod10)-=5(mod10)$
E' corretto? Sono abbastanza dubbioso.
Corretto è corretto. Il punto è che scritto così è scritto male.
Ipotesi induttiva: \( 5^{n} \equiv 5 \pmod{10} \).
Tesi dell'induzione: \( 5^{n+1} \equiv 5 \pmod{10} \).
Partendo da \( 5^{n} \equiv 5 \pmod{10} \) si ha che \( 5^{n} \cdot 5 \equiv 5 \cdot 5 \pmod{10} \), ovvero \( 5^{n+1} \equiv 25 \pmod{10} \); poiché è anche \( 25 \equiv 5 \pmod{10} \), per transitività \( 5^{n+1} \equiv 5 \pmod{10} \).
Ipotesi induttiva: \( 5^{n} \equiv 5 \pmod{10} \).
Tesi dell'induzione: \( 5^{n+1} \equiv 5 \pmod{10} \).
Partendo da \( 5^{n} \equiv 5 \pmod{10} \) si ha che \( 5^{n} \cdot 5 \equiv 5 \cdot 5 \pmod{10} \), ovvero \( 5^{n+1} \equiv 25 \pmod{10} \); poiché è anche \( 25 \equiv 5 \pmod{10} \), per transitività \( 5^{n+1} \equiv 5 \pmod{10} \).
Riprendo un attimo la discussione con un altro esercizio (inventato da me):
In sostanza voglio dimostrare che tutte le potenze di 3 sono congrue a 5 modulo 2.
Correggetemi se sbaglio, io ho fatto così:
Ipotesi induttiva: $3^n -=5(mod 2)$
Tesi dell'induzione: $3^(n+1) -=5(mod2)$
Partendo da $3^n -=5(mod 2)$ si ha che $3^n * 3 -=5*3(mod2)$, ovvero $3^(n+1) -=15(mod2)$, poichè è anche $15-=5(mod2)$, per la transitività si ha che $3^(n+1) -=5(mod2)$ ...pertanto la tesi è verificata.
E' corretto? Intanto grazie per il vostro tempo.
In sostanza voglio dimostrare che tutte le potenze di 3 sono congrue a 5 modulo 2.
Correggetemi se sbaglio, io ho fatto così:
Ipotesi induttiva: $3^n -=5(mod 2)$
Tesi dell'induzione: $3^(n+1) -=5(mod2)$
Partendo da $3^n -=5(mod 2)$ si ha che $3^n * 3 -=5*3(mod2)$, ovvero $3^(n+1) -=15(mod2)$, poichè è anche $15-=5(mod2)$, per la transitività si ha che $3^(n+1) -=5(mod2)$ ...pertanto la tesi è verificata.
E' corretto? Intanto grazie per il vostro tempo.
Sì: va bene.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo