Congruenza Modulo n
Non riesco a risolvere questi esercizi di algebra e questo mi sta parecchio scoraggiando se penso a quello che troverò all'esame...
1- Dimostrare che se $a,b,c in ZZ$ e $a, n$ sono primi tra loro, da $ab-=ac (mod n)$ segue che $b-=c (mod n)$ .
Qui ho cercato di usare il corollario secondo cui a,b primi tra loro implica $\alphaa+\betab=1$ solo che non capisco come possa aiutarmi
2 - Dimostrare che per ogni $n$ naturale si ha $7^n-=1 (mod 8)$ per $n$ pari, e $7^n-=7 (mod 8)$ per $n$ dispari.
Qui ho cercato di dimostrarlo per induzione distinguendo i due casi, ovvero provando che se è vero per $2n$ allora è vero per $2n + 2$ (caso pari) e se è vero per $2n+1$ allora è vero per $2n+3$ , ma anche qua sono giunto al nulla.
Non posto i procedimenti perchè credo che già i punti di inizio da dove son partito siano sbagliati. Qualcuno che riesce a indirizzarmi?
1- Dimostrare che se $a,b,c in ZZ$ e $a, n$ sono primi tra loro, da $ab-=ac (mod n)$ segue che $b-=c (mod n)$ .
Qui ho cercato di usare il corollario secondo cui a,b primi tra loro implica $\alphaa+\betab=1$ solo che non capisco come possa aiutarmi
2 - Dimostrare che per ogni $n$ naturale si ha $7^n-=1 (mod 8)$ per $n$ pari, e $7^n-=7 (mod 8)$ per $n$ dispari.
Qui ho cercato di dimostrarlo per induzione distinguendo i due casi, ovvero provando che se è vero per $2n$ allora è vero per $2n + 2$ (caso pari) e se è vero per $2n+1$ allora è vero per $2n+3$ , ma anche qua sono giunto al nulla.
Non posto i procedimenti perchè credo che già i punti di inizio da dove son partito siano sbagliati. Qualcuno che riesce a indirizzarmi?
Risposte
1) Poiché $(a,n)=1$ allora esiste $x,y \in \mathbb{Z}$ tali che $ax+ny=1$, in particolare moltiplicando $b-c$ all'identità otteniamo
$(ab-ac)x+(b-c)ny=b-c$
Ora il primo addendo $(ab-ac)x$ è divisibile per $n$, dunque il primo membro dell'identità è divisibile per $n$ e quindi anche il secondo $b-c$. Fine
2) Usa il prodotto notevole $x^n-y^n=(x-y)(x^{n-1}+ \cdots y^{n-1})$...
$(ab-ac)x+(b-c)ny=b-c$
Ora il primo addendo $(ab-ac)x$ è divisibile per $n$, dunque il primo membro dell'identità è divisibile per $n$ e quindi anche il secondo $b-c$. Fine
2) Usa il prodotto notevole $x^n-y^n=(x-y)(x^{n-1}+ \cdots y^{n-1})$...
@dan95 Mi sembra che vi stiate complicando la vita tremendamente
1. \(ab\equiv ac\pmod{n} \Rightarrow a(b-c) \equiv 0\pmod{n} \) ovvero \(\displaystyle n|a(b-c) \) da qui si ha direttamente che \(\displaystyle n|(b-c) \). Insomma usi la definizione di coprimo direttamente.
2. \(\displaystyle n = 0,1 \) sono banali. Ora supponiamo che valga per un \(n-1\) pari, allora
\begin{align*} 7^n &\equiv 7^{n-1}\cdot 7\pmod{8} \\
&\equiv 1\cdot 7\pmod{8} \\
&\equiv 7\pmod{8}.
\end{align*}
Supponiamo quindi che valga per un \(n-1\) dispari, allora
\begin{align*} 7^n &\equiv 7^{n-1}\cdot 7\pmod{8} \\
&\equiv 7\cdot 7\pmod{8} \\
&\equiv 49\pmod{8} \\
&\equiv 1\pmod{8}.
\end{align*}
Siccome vale per un pari ed un dispari allora vale per tutti gli \(n\in\mathbb{N}\). Un po' più complesso è dimostrarlo per gli \(n<0\), ma non molto dopo che noti che \(7\) è inverso di sé stesso in \(\mathbb{Z}_8\).
Siccome ti ho di fatto mostrato le soluzioni, ti propongo un problema su cui approfondire. Dimostra la stessa cosa sostituendo \(8\) con \(m\) e \(7\) con \(m-1\).
1. \(ab\equiv ac\pmod{n} \Rightarrow a(b-c) \equiv 0\pmod{n} \) ovvero \(\displaystyle n|a(b-c) \) da qui si ha direttamente che \(\displaystyle n|(b-c) \). Insomma usi la definizione di coprimo direttamente.
2. \(\displaystyle n = 0,1 \) sono banali. Ora supponiamo che valga per un \(n-1\) pari, allora
\begin{align*} 7^n &\equiv 7^{n-1}\cdot 7\pmod{8} \\
&\equiv 1\cdot 7\pmod{8} \\
&\equiv 7\pmod{8}.
\end{align*}
Supponiamo quindi che valga per un \(n-1\) dispari, allora
\begin{align*} 7^n &\equiv 7^{n-1}\cdot 7\pmod{8} \\
&\equiv 7\cdot 7\pmod{8} \\
&\equiv 49\pmod{8} \\
&\equiv 1\pmod{8}.
\end{align*}
Siccome vale per un pari ed un dispari allora vale per tutti gli \(n\in\mathbb{N}\). Un po' più complesso è dimostrarlo per gli \(n<0\), ma non molto dopo che noti che \(7\) è inverso di sé stesso in \(\mathbb{Z}_8\).
Siccome ti ho di fatto mostrato le soluzioni, ti propongo un problema su cui approfondire. Dimostra la stessa cosa sostituendo \(8\) con \(m\) e \(7\) con \(m-1\).
1) dimostrazione standard
2) sì delle due che avevo in mente ho scelta la più "calcolosa"
2) sì delle due che avevo in mente ho scelta la più "calcolosa"
Grazie mille a entrambi, allora per il primo purtroppo sono scemo io. Ho scritto qui sul forum la consegna giusta ma sul quaderno ho scritto per a,b coprimi... ho perso un'ora per nulla.
Per il secondo invece non ho ben capito come hai trattato i due casi (49 e 1), ma appena torno a casa provo a riscrivermi tutto e sicuramente mi tornerà. Proverò anche a pensare all'esercizio che hai proposto
Per il secondo invece non ho ben capito come hai trattato i due casi (49 e 1), ma appena torno a casa provo a riscrivermi tutto e sicuramente mi tornerà. Proverò anche a pensare all'esercizio che hai proposto
Ho calcolato a mano il modulo: \(49 = 48 + 1 = 8\times 6 + 1\).
Propongo un altro paio di esercizi sempre sulla congruenza:
Sia $n>=1$ . Si consideri $r: ZZ\toZZ$ definita $AA x in ZZ$ da $r(x) =$ "resto della divisione di x per n". Dimostrare che:
(a): $r(x) = {0,1, ... ,n-1}$
Soluzione: per def $x=nq + r$ , $q in ZZ$, $0<=r<=n-1$, quindi l' immagine di r è $r(x) = {0,1,..., n-1}$
(b): la relazione $~$ associata all' applicazione r è la congruenza modulo n.
Soluzione: Siano $x=nq + r$ , $y=nq' + r' => x-y=nq + r - nq' - r' => x-y = n(q-q') + r-r'$
ma se $x-=y (mod n) => n|(x-y) => r-r'=0 => r=r'$
(c): se $y in {0,1,2,...,n-1}$ , allora $r^(-1)(y) = [y]_-= (mod n)$
Soluzione: $r^(-1)(y) = {x | x in ZZ , r(x) = y} => x = nq + y$ ,
$[y]_-= = {x | x in ZZ , x-=y} => x-y = nq => x = nq + y $
Non sono sicuro di nessun punto quindi ecco se poteste dirmi dove ho sbagliato così riprovo ...
Secondo esercizio:
$f:ZZ\toZZ$ e $n$ intero. Si definisca $~$ su $ZZ$ ponendo, $AA a,b in ZZ$ , $a~b$ se $f(a)-=f(b) (mod n)$ .
(a) dimostrare che $~$ è equivalenza su $ZZ$. (non scrivo nulla perchè sono solo conti e almeno questo so che è giusto)
(b) dimostrare che $[A]_~ = f^(-1)([f(a)]_-= (mod n) ) AA a in ZZ$
Non ho idee da dove partire, devo dimostrare la doppia inclusione?
Sia $n>=1$ . Si consideri $r: ZZ\toZZ$ definita $AA x in ZZ$ da $r(x) =$ "resto della divisione di x per n". Dimostrare che:
(a): $r(x) = {0,1, ... ,n-1}$
Soluzione: per def $x=nq + r$ , $q in ZZ$, $0<=r<=n-1$, quindi l' immagine di r è $r(x) = {0,1,..., n-1}$
(b): la relazione $~$ associata all' applicazione r è la congruenza modulo n.
Soluzione: Siano $x=nq + r$ , $y=nq' + r' => x-y=nq + r - nq' - r' => x-y = n(q-q') + r-r'$
ma se $x-=y (mod n) => n|(x-y) => r-r'=0 => r=r'$
(c): se $y in {0,1,2,...,n-1}$ , allora $r^(-1)(y) = [y]_-= (mod n)$
Soluzione: $r^(-1)(y) = {x | x in ZZ , r(x) = y} => x = nq + y$ ,
$[y]_-= = {x | x in ZZ , x-=y} => x-y = nq => x = nq + y $
Non sono sicuro di nessun punto quindi ecco se poteste dirmi dove ho sbagliato così riprovo ...
Secondo esercizio:
$f:ZZ\toZZ$ e $n$ intero. Si definisca $~$ su $ZZ$ ponendo, $AA a,b in ZZ$ , $a~b$ se $f(a)-=f(b) (mod n)$ .
(a) dimostrare che $~$ è equivalenza su $ZZ$. (non scrivo nulla perchè sono solo conti e almeno questo so che è giusto)
(b) dimostrare che $[A]_~ = f^(-1)([f(a)]_-= (mod n) ) AA a in ZZ$
Non ho idee da dove partire, devo dimostrare la doppia inclusione?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo