Congruenza Modulo n

Messaggioda anti-spells » 23/10/2018, 18:58

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?
anti-spells
Junior Member
Junior Member
 
Messaggio: 22 di 210
Iscritto il: 08/08/2018, 18:20

Re: Congruenza Modulo n

Messaggioda dan95 » 23/10/2018, 19:36

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})$...
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Cannot live without
Cannot live without
 
Messaggio: 2427 di 5268
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Congruenza Modulo n

Messaggioda vict85 » 23/10/2018, 20:11

@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\).
vict85
Moderatore
Moderatore
 
Messaggio: 9429 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Congruenza Modulo n

Messaggioda dan95 » 23/10/2018, 20:55

1) dimostrazione standard

2) sì delle due che avevo in mente ho scelta la più "calcolosa"
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Cannot live without
Cannot live without
 
Messaggio: 2429 di 5268
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Congruenza Modulo n

Messaggioda anti-spells » 23/10/2018, 21:09

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
anti-spells
Junior Member
Junior Member
 
Messaggio: 23 di 210
Iscritto il: 08/08/2018, 18:20

Re: Congruenza Modulo n

Messaggioda vict85 » 23/10/2018, 21:23

Ho calcolato a mano il modulo: \(49 = 48 + 1 = 8\times 6 + 1\).
vict85
Moderatore
Moderatore
 
Messaggio: 9430 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Congruenza Modulo n

Messaggioda anti-spells » 24/10/2018, 19:49

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?
anti-spells
Junior Member
Junior Member
 
Messaggio: 24 di 210
Iscritto il: 08/08/2018, 18:20


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite