Divisione
Ciao a tutti ragazzi, questo è il mio primo post. 
Arrivo al sodo, voglio fare l'esonero di Matematica Discreta per il corso di informatica. Il problema e che riesco ad usare il principio di induzione ne le relazioni di equivalenza sulla divisione!
Per l'induzione ci riesco soltanto su quei esercizi con la sommatoria e/o uguaglianza ma non ci riesco con quelli con minore/maggiore oppure con le divisioni! Mentre per la relazione di equivalenza oltre a x|(p-q) non riesco a determinare se è di equivalenza o no!
Ecco un esempio:
8|3^(2n) -1 (Scusate non so usare ancora i vostri simboli, comunque è 8 divide 3 elevato a 2n, tutto -1, quindi -1 non è esponente di 3)
Ma già qui sono bloccato, nelle uguaglianze ad esempio sommavo entrambi i membri e facevo un po di calcoli... qui cosa dovre fare??
Io avevo pensato ad 3^2n-1 = K*8 ma poi mi sono bloccato...
Grazie a tutti!
Arrivo al sodo, voglio fare l'esonero di Matematica Discreta per il corso di informatica. Il problema e che riesco ad usare il principio di induzione ne le relazioni di equivalenza sulla divisione!
Per l'induzione ci riesco soltanto su quei esercizi con la sommatoria e/o uguaglianza ma non ci riesco con quelli con minore/maggiore oppure con le divisioni! Mentre per la relazione di equivalenza oltre a x|(p-q) non riesco a determinare se è di equivalenza o no!
Ecco un esempio:
8|3^(2n) -1 (Scusate non so usare ancora i vostri simboli, comunque è 8 divide 3 elevato a 2n, tutto -1, quindi -1 non è esponente di 3)
Ma già qui sono bloccato, nelle uguaglianze ad esempio sommavo entrambi i membri e facevo un po di calcoli... qui cosa dovre fare??
Io avevo pensato ad 3^2n-1 = K*8 ma poi mi sono bloccato...
Grazie a tutti!
Risposte
Insomma, cosa devi dimostrare? Io non ho ben capito, ma provo ad interpretare.
Vuoi provare che \(\displaystyle \forall \; n \in \mathbb{N^{*}} \) si ha \(\displaystyle 8 | (3^{2n} -1) \) [1], giusto?
Opero induttivamente.
1. base induttiva (\(\displaystyle n=1 \)): senza dubbio si ha \(\displaystyle 8|(3^{2} -1) \). Equivalentemente (perdona la tautologia) \(\displaystyle (8+1) \equiv_{8} 9 \).
2. ipotesi induttiva: suppongo vera la [1]. Equivalentemente suppongo che \(\displaystyle 3^{2n} \equiv_{8} (8k+1) \) (o, ancora meglio, che \(\displaystyle 3^{2n} \equiv_{8} 1 \)) per qualche \(\displaystyle k \ \in \mathbb{N} \) (ricordando che presi \(\displaystyle a,\ b,\ c,\ d,\ n \ \in \mathbb{N} \) tali che \(\displaystyle a\ \equiv_{n}b \) e \(\displaystyle c \ \equiv_{n} d \) allora si ha \(\displaystyle (a+c) \ \equiv_{n} (b+d) \) e \(\displaystyle ac\ \equiv_{n} bd \)).
3. passo induttivo: provo che [1] è valida per \(\displaystyle n+1 \). Si ha \(\displaystyle 3^{2n+2}=9\cdot 3^{2n} \); del resto \(\displaystyle 9 \equiv_{8} 1 \) e \(\displaystyle 3^{2n} \equiv_{8} 1 \) per ipotesi, quindi \(\displaystyle 9\cdot 3^{2n} \equiv_{8} 1\cdot 1 \) per la proprietà poc'anzi enunciata \(\displaystyle \Box \).
Che poi \(\displaystyle | \) (per esempio su \(\displaystyle \mathbb{N} \) o su \(\displaystyle \mathbb{Z} \)) sia o meno una relazione d'equivalenza lo lascio decidere a te...
Vuoi provare che \(\displaystyle \forall \; n \in \mathbb{N^{*}} \) si ha \(\displaystyle 8 | (3^{2n} -1) \) [1], giusto?
Opero induttivamente.
1. base induttiva (\(\displaystyle n=1 \)): senza dubbio si ha \(\displaystyle 8|(3^{2} -1) \). Equivalentemente (perdona la tautologia) \(\displaystyle (8+1) \equiv_{8} 9 \).
2. ipotesi induttiva: suppongo vera la [1]. Equivalentemente suppongo che \(\displaystyle 3^{2n} \equiv_{8} (8k+1) \) (o, ancora meglio, che \(\displaystyle 3^{2n} \equiv_{8} 1 \)) per qualche \(\displaystyle k \ \in \mathbb{N} \) (ricordando che presi \(\displaystyle a,\ b,\ c,\ d,\ n \ \in \mathbb{N} \) tali che \(\displaystyle a\ \equiv_{n}b \) e \(\displaystyle c \ \equiv_{n} d \) allora si ha \(\displaystyle (a+c) \ \equiv_{n} (b+d) \) e \(\displaystyle ac\ \equiv_{n} bd \)).
3. passo induttivo: provo che [1] è valida per \(\displaystyle n+1 \). Si ha \(\displaystyle 3^{2n+2}=9\cdot 3^{2n} \); del resto \(\displaystyle 9 \equiv_{8} 1 \) e \(\displaystyle 3^{2n} \equiv_{8} 1 \) per ipotesi, quindi \(\displaystyle 9\cdot 3^{2n} \equiv_{8} 1\cdot 1 \) per la proprietà poc'anzi enunciata \(\displaystyle \Box \).
Che poi \(\displaystyle | \) (per esempio su \(\displaystyle \mathbb{N} \) o su \(\displaystyle \mathbb{Z} \)) sia o meno una relazione d'equivalenza lo lascio decidere a te...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo