Congruenze per induzione

corel_86
Ciao a tutti sono un nuovo utente del forum e ho bisogno del vostro aiuto.
Durante un compito di Formazione Discreta mi sono apparse queste tipologie di esercizio:

"Dimostrare che, per ogni n≥0 risulta 4^2n≡1 (mod 3)"

(^ è il simbolo di elevazione a potenza)

"Dimostrare utilizzando il principio di induzione, che:
1)4^2n-3•4^n≡4 (mod 3) con n€N
2)3^3n-2•3^n≡3 (mod 4) con n€N
"

(• e il simbolo di moltiplicazione, non ho trovato atro :lol: )
:shock: :shock: :shock:

Sareste in grado di spiegarmi passo per passo come si risolvono?
In attesa di una vostra risposta vi saluto.......Ciao :smt039 :smt039

Risposte
adaBTTLS1
benvenuto nel forum.

premesso che non conosco i moderni metodi di dimostrazione sulle congruenze, che ho visto utilizzare con molta abilità da altri utenti "giovani",
provo comunque a darti qualche input, spero risolutivo. vedi tu di formalizzare con il metodo usato a lezione.

$4^(2n)=(4^2)^n=16^n=(15+1)^n=(3*5+1)^n$

dato che sia $4^(2n)-3*4^n$ sia $4^(2n-3)*4^n$ sono congrui a 1 modulo 3, ma anche 4 è congruo a 1 modulo 3, la congruenza è valida con entrambe le interpretazioni:
$4^(2n)-3*4^n$: la prima parte è congrua a 1 (per quanto già visto), la seconda a 0 (essendo un multiplo di 3), dunque ...
$4^(2n-3)*4^n=4^(2n-3+n)=4^(3n-3)=4^(3(n-1))=(4^3)^(n-1)=64^(n-1)=(3*21+1)^(n-1)$ ...

$3^(3n-2)*3^n=3^(4n-2)=9^(2n-1)=(4*2+1)^(2n-1)$, così sarebbe conrua a 1 e non a 3 (modulo 4). provo con l'altra interpretazione:
$3^(3n)-2*3^n=27^n-2*3^n=(28-1)^n-2*(4-1)^n$. con n pari viene congruo a -1 e quindi a +3 (modulo 4). con n dispari ho qualche problema (verrebbe -3 e quindi +1 ?).

spero di esserti stata d'aiuto. comunque precisa le operazioni, o con le formule o almeno con le parentesi. ciao.

corel_86
Sono 3 diversi esercizi:

1)dimostrare che, per ogni n≥0 risulta 4^2n≡1 (mod 3)

Dimostrare utilizzando il principio di induzione, che:
2)(4^2n)-(3•4^n)≡4 (mod 3) con n€N
3)(3^3n)-(2•3^n)≡3 (mod 4) con n€N

io sapevo che per il principio di induzione si fissa n=0 e supposto vero per n=0 si dimostra per n+1......

cioè per esempio:

"Dimostrare che la somma dei primi n numeri naturali dispari è n^2"

1+3+5+......(2n-1)=n^2

per n=0 risulta 1=1 vero

per n+1 si ha

1+3+5+....(2n-1)+(2n+1)=n^2+2n+1 si somma ambo i membri

e dopo semplici passaggi si ha
1+3+5+....(2n-1)+(2n)=(n+1)^2 vero perchè se sostituisco al secondo membro n+1 al posto di n risulta

lo stesso procedimento lo devo applicare alle congruenze che non so fare

corel_86
all'ultimo 1+3+5+....(2n-1)+(2n+1)=(n+1)^2 scusate ho sbagliato a scrivere

corel_86
Comunque ada sei stata gentilissima e scusami se non ti ho ringraziato......

adaBTTLS1
adesso che hai messo le parentesi mi hai tolto ogni dubbio: il terzo non è giusto se n è dispari.
basta considerare ad esempio n=1: si ha 27-6=21=20+1, quindi non è congruo a 3 modulo 4.

quanto alla dimostrazione per induzione, puoi facilmente ricavartela da quello che ho scritto nel messaggio precedente.
non voglio forzare molto la mano, perché sicuramente le mie notazioni sulle congruenze sono "antiquate", però ti do un'idea sul primo.

il primo valore (n=1) è 4^2=16=15+1, congruo a 1 (modulo 3: nei passaggi successivi lo sottintendo)
vogliamo ora provare che se 4^(2n) è congruo a 1, lo è anche 4^(2(n+1))=4^(2n+2)=4^(2n)*4^2
ma quest'ultima espressione, per l'ipotesi induttiva, si può scrivere (3k+1)*(15+1) per un opportuno k, per cui anche tale prodotto è congruo a 1.
....
spero sia chiaro. prova a continuare tu e a rivedere le condizioni dell'ultimo quesito.
ciao.

corel_86
C'è una cosa che mi sfugge nel primo esercizio si parte n≥0 quindi si considera n=0;

cioè $4^0≡1 (mod 3)$ vale a dire 1≡1 (mod 3) => 1-1=3k ma se 3 divide 1-1 è sbagliato giusto....

io ho un po' di difficolta a capire le congruenze potresti dare un definizione per capire se è vero quello che dico?

per quanto riguarda n+1 bisogna moltiplicare ambo i membri per $4^2$ diventando cosi:

$4^(2n) * 4^2 = (3k +1 )*4^2$ e fino a qui ci sono diventanto poi con vari passaggi

$4^(2n) * 4^2 = 48k +16$ e poi cosa devo fare? ti ripeto sono un po' in difficoltà

grazie per la pazienza

Sk_Anonymous
Corel_86 ha scritto:
io sapevo che per il principio di induzione si fissa n=0 e supposto vero per n=0 si dimostra per n+1......
---------------------
No, non è affatto così. Il principio di induzione dice questo:
1-Se una proposizione P(n) è vera per n=0 (o per n=1, fa lo stesso), e
2-se, supposta vera P(n) per un n generico (NON per n=0), si riesce a dimostrare vera anche P(n+1),
allora la P(n) è vera per ogni n>0.
-------------------
Rifaccio ora con cura l'applicazione del principio alla somma dei dispari.
La proposizione P(n) è l'affermazione: $1 + 3 + 5 + + (2n-1) = n^2$ (A)
Per n=1, la proposizione afferma che: 1 = 1 , e questo é vero.
Ora supponiamo vera la P(n), cioè usiamo come ipotesi la su scritta identità (A)
(ciò è curioso, perchè quella è proprio la tesi da dimostrare!).
Proviamo ora a dimostrare P(n+1) che afferma
$[1 + 3 + 5 + ... + (2n-1) ] + (2n+1) = (n+1)^2$
Ma la parentesi quadra, essendo P(n) vera per ipotesi, vale $n^2$.
Quindi dobbiamo solo mostrare che
$n^2+2n+1=(n+1)^2$
il che è banalmente vero (si tratta dello sviluppo d'un quadrato, che s'impara alla 1.a media, se ben ricordo).
Essendo soddisfatte entrambe le condizioni del principio d'induzione, possiamo concludere che
l'identità sopra scritta circa la somma dei numeri dispari risulta valida per ogni n.
Chiaro?

adaBTTLS1
Io per associazione con gli altri esercizi ho trascurato il caso n=0. Comunque 1 congruo a 1 (mod 3) ed è finita qui. La congruenza è una relazione di equivalenza: ogni numero è congruente a se stesso.
16 congruo a 1 modulo 3 significa che il resto della divisione tra 16 e 3 è 1.
Se dici che “5 è congruo a 14 modulo 3” significa che 5 e 14, se li dividi per 3, hanno lo stesso resto (in questo caso 2).
Quindi il 16 lo scrivo come 15+1 perché 15 è multiplo di 3, anzi è il più grande multiplo di 3 minore di 16.
Un qualsiasi numero congruo a 1 modulo 3 può essere scritto come (3k+1), dove k è un numero intero (k è il quoziente della divisione tra il numero e 3. Questa proprietà può essere estesa a tutti i numeri se ci si limita a {3k+0, 3k+1, 3k+2}.
Veniamo alla dimostrazione.
Come base puoi prendere $4^0=1$ oppure $4^2=16=3*5+1$, che sono entrambi congrui a 1 modulo 3.
Supponi (ipotesi induttiva) che sia vero che $4^(2n)$ sia congruo a 1 modulo 3, per un generico n. Allora questo significa che $4^(2n)=3k+1$ per un certo k intero. Vogliamo dimostrare che la stessa cosa vale per (n+1) al posto di n.
$4^(2(n+1))=4^(2n+2)=4^(2n)*4^2=(3k+1)*16=48k+16=48k+15+1=3(16k+5)+1$, dove (16k+5) è un numero intero, per cui anche $4^(2(n+1))$ è congruo a 1 modulo 3.
Dunque la relazione è valida $AA n >= 0$.
Spero sia chiaro. Ciao.

corel_86
rispondo a seascoli

è esattamente quello che ho detto soltanto non mi sono espresso bene, perchè se ci fai caso se hai supposto P(n) vero cioè

$1+3+5+....+(2n-1)=n^2$

per n+1 si ha

$1+3+5+....+(2n-1) + (2n+1)=(n+1)^2$

ma siccome dobbiamo prendere l'equazione iniziale basta aggiungere ambo i membri 2n+1 cioè

$1+3+5+....+(2n-1) + (2n+1)=n^2 + (2n +1)$

$1+3+5+....+(2n-1) + (2n+1)=(n+1)^2$ e cosi è verificata

rispondo ad ada

mi stai dicendo che se $4^(2n)*4^2=(1+3h)*4^2$

svolgo il secondo membro che viene 16+48h => 15+1+48h => 3(5+16h) + 1

fisso k=5+16h e risulta 3k+1 che è quello che volevamo dimostrare giusto?

se è cosi credo di avere capito

adaBTTLS1
sì, è giusto.

corel_86
Perfetto adesso faccio gli altri. Mi aiuti a vedere se faccio giusto? grazie!!!!
l'esercizio $3^(2n) - 2*3^n ≡ 3 (mod 4)$ e riconducibile a

=> $3^n*7≡ 3 (mod 4)

per n=1 essendo numeri naturali si parte dal numero 1 si ha

$21≡3 (mod 4)$ falso perchè 21 e 3 se li divido per 4 hanno resto diverso


$4^(2n) - 3*4^n ≡ 4 (mod 3)$ si riconduce a $4^n≡ 1 (mod 3)

per n=1 si ha

4≡1 (mod 3) vero

per n+1 si ha

$4^(n+1)≡ 4 (mod 3)$ => $4^n*4^1≡ 4 (mod 3)$ => $4^n*4^1≡ 1 (mod 3)$

prendo il secondo membro e si ha:

$(1+3h)4=4+12h=3+1+12h=3(1+4h)+1$

fisso k=1+4h => 3k +1 vero

Steven11
Certo mi viene abbastanza la pelle d'oca davanti al primo esercizio (ma pure al secondo).

Infatti dice
$4^(2n)\equiv1 (mod3)$ ma questo è limitante, dal momento che l'esponente non deve essere pari per forza, vale in generale
$4^n\equiv1 (mod3)$.
Banale da provare: siccome
$4\equiv1 (mod3)$ e siccome è lecito innalzare ad esponente i due membri della congruenza, allora
$4^n\equiv 1^n =1(\mod3)$

Il secondo è uguale al primo: infatti eliminando senza problemi il termine $3*4^n$ che vale $0 (mod3)$ e facendo diventare il $4$ come $1$, si ha quello di prima.

corel_86
se ho fatto tutto giusto il merito e senza dubbio tuo grazie tante ada sei stata paziente e gentile

se riesco a fare il compito e per merito tuo

corel_86
ovvimente grazie anche alle altre persone che mi hanno aiutato........

adaBTTLS1
prego! mi fa piacere se posso aiutarti!

anche se riesco a leggere con difficoltà le tue formule (ho visto che il simbolo di congruenza all'interno di una formula si ottiene con -=),
nella seconda hai copiato male il testo, perché inizialmente c'era (3n) come esponente, e così è vera, mentre qui hai copiato con (2n) come esponente, e così è giustamente falsa.
per la terza c'è qualcosa che non va quando hai raccolto (rivedila, e cerca di usare il simbolo giusto oppure è meglio uguale che un simbolo che il sistema non legge).

ciao.

corel_86
allora il testo è giusto sia della seconda che nella terza......per quanto riguarda il terzo esercizio ho sbagliato a scrivere comunque ho fatto in questo modo ti faccio vedere tutti i passaggi (il simbolo => è la freccia non la congruenza)

$4^(2n) - 3*4^n≡4 (mod 3)$
$4^n*4^2-3*4^n≡4(mod 3)$
$4^n(4^2-3)≡4(mod 3)$
$4^n*(13)≡4(mod 3)$
$4^n*(13)≡1(mod 3)$

per n=1 si ha

$52≡1(mod 3)$ cioè essendo 52=3*17+1 risulta $1≡1 (mod 3)$ il che risulta vero

poi applicando per n+1 si ha

$4^(n+1)*(13)≡1 (mod 3)

$4^n*4^1*(13)≡1 (mod 3)

prendo il secondo membro e si ottiene

$(1+3h)4 = 4+12h = 1+3+12h = 1+3(1+4h)

fisso k=1+4h e risulta $1+3k$ e cosi si dimostra che è vero

adaBTTLS1
$4^(2n)=(4^n)^2 != 4^n*4^2=4^(n+2)$
mi fermo qui per ora, così ti invio subito il messaggio.

corel_86
già è vero che sciocco un errore da 5 elementare......... aspetta che correggo

corel_86
mi sono fermato!!! dopo che ho fatto questi passaggi che devo fare?

$4^(2n) - 3*4^n≡4 (mod 3)$

$4^n(4^n-3)≡4(mod 3)$

$4^n(4^n-3)≡1(mod 3)$

adaBTTLS1
non ti conviene raccogliere 4^n.
ti conviene usare il metodo di ieri...
$4^(2n)-3*4^n=(4^2)^n-3*4^n=(15+1)^n-3*4^n$.... OK? prova a continuare. ciao.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.