Probabilmente è una domanda assai stupida , ma essendo io un povero pivellino vi chiedo di perdonarmi
Studiando una dispensa olimpica ho letto che se $ a \equiv b \bmod{m} $ e $ c \equiv d \bmod{m} $ allora $ ac \equiv bd \bmod{m} $ .
Innanzitutto non ho ben chiaro il perché (intuitivamente diciamo che ci arrivo ma non saprei dare una dimostrazione matematica) , ma il mio dubbio è questo : perché se $ a \equiv b \bmod{m} $ e $ c \equiv c \bmod{m} $ non è sempre vero che $ ac \equiv bc \bmod{m} $ come afferma la relazione precedente?
Grazie per le eventuali spiegazioni...
Dubbio sulle congruenze
Re: Dubbio sulle congruenze
Il forum esiste anche (e forse soprattutto) per questo!
Detto ciò, forse la domanda sarebbe più appropriata nel Glossario che in una sezione di problemi, ma per ora non sto a spostarla.
Il fatto di cui parli all'inizio è semplice ma importante; assumo che tu abbia già pensato da solo a come dimostrarlo, e in caso contrario t'invito a farlo prima di leggere quello che segue.
Dire che $a\equiv b \bmod{m}$ significa che gli interi $a$ e $b$ danno lo stesso resto nella divisione per $m$. Scrivi esplicitamente risultato e resto della divisione per entrambi: devi avere $a=mh+r$ e $b=mk+r$, dove $h$ e $k$ sono interi. Allo stesso modo, $c=mh'+r'$ e $d=mk'+r'$. Ora basta esplicitare i prodotti: $ac=(mh+r)(mh'+r')=m(...)+rr'$, il che implica $ac\equiv rr'\bmod{m}$ (nota che potresti benissimo calcolare l'espressione da sostituire ai puntini, ma per la verità non ti serve farlo: tutto ciò che ti serve sapere è che il prodotto $ac$ si scrive somma di un multiplo di $m$ e di $rr'$); naturalmente vale anche, per lo stesso motivo, $bd=(mk+r)(mk'+r')\equiv rr' \bmod{m}$, e dunque $ac\equiv bd \bmod{m}$.
Ma a questo punto (e anche prima, per la verità) dovrebbe esserti chiaro che, dati tre interi $a$, $b$ e $c$ tali che $a\equiv b\bmod{m}$, in effetti $ac\equiv bc \bmod{m}$.
Il dubbio che rimane è da dove e come tu abbia dedotto la tua ultima affermazione.
Detto ciò, forse la domanda sarebbe più appropriata nel Glossario che in una sezione di problemi, ma per ora non sto a spostarla.
Il fatto di cui parli all'inizio è semplice ma importante; assumo che tu abbia già pensato da solo a come dimostrarlo, e in caso contrario t'invito a farlo prima di leggere quello che segue.
Dire che $a\equiv b \bmod{m}$ significa che gli interi $a$ e $b$ danno lo stesso resto nella divisione per $m$. Scrivi esplicitamente risultato e resto della divisione per entrambi: devi avere $a=mh+r$ e $b=mk+r$, dove $h$ e $k$ sono interi. Allo stesso modo, $c=mh'+r'$ e $d=mk'+r'$. Ora basta esplicitare i prodotti: $ac=(mh+r)(mh'+r')=m(...)+rr'$, il che implica $ac\equiv rr'\bmod{m}$ (nota che potresti benissimo calcolare l'espressione da sostituire ai puntini, ma per la verità non ti serve farlo: tutto ciò che ti serve sapere è che il prodotto $ac$ si scrive somma di un multiplo di $m$ e di $rr'$); naturalmente vale anche, per lo stesso motivo, $bd=(mk+r)(mk'+r')\equiv rr' \bmod{m}$, e dunque $ac\equiv bd \bmod{m}$.
Ma a questo punto (e anche prima, per la verità) dovrebbe esserti chiaro che, dati tre interi $a$, $b$ e $c$ tali che $a\equiv b\bmod{m}$, in effetti $ac\equiv bc \bmod{m}$.
Il dubbio che rimane è da dove e come tu abbia dedotto la tua ultima affermazione.
Re: Dubbio sulle congruenze
Bentornata phi!
Probabilmente la domanda che si poneva alla fine è: "perchè se $ac \equiv bc \pmod m$ e $c \equiv c \pmod m$ allora non è necessariamente vero che $a \equiv b \pmod m$..
Probabilmente la domanda che si poneva alla fine è: "perchè se $ac \equiv bc \pmod m$ e $c \equiv c \pmod m$ allora non è necessariamente vero che $a \equiv b \pmod m$..
The only goal of science is the honor of the human spirit.
-
- Messaggi: 35
- Iscritto il: 12 feb 2012, 20:08
Re: Dubbio sulle congruenze
Chiedo scusa , non mi ero accorto proprio di quella sezione!La prossima volta farò così.phi ha scritto:Il forum esiste anche (e forse soprattutto) per questo!
Detto ciò, forse la domanda sarebbe più appropriata nel Glossario che in una sezione di problemi, ma per ora non sto a spostarla.
In realtà ho sbagliato io pensando che valesse anche l'inverso.Ora ho capito perché non è così ma ho ancora un dubbio...sulla dispensa è scritto che appunto l'inverso vale solo se MCD(m,c)=1 , ecco io questo non sono riuscito a dimostrarlo...se saresti così gentile da darmi ancora un mano te ne sarei gratophi ha scritto:Il dubbio che rimane è da dove e come tu abbia dedotto la tua ultima affermazione.
Re: Dubbio sulle congruenze
Immaginavo che il problema fosse qualcosa del genere.flutist001 ha scritto:In realtà ho sbagliato io pensando che valesse anche l'inverso.
Be', supponi che $c$ ed $m$ siano primi fra loro, e supponi che, per due interi $a$ e $b$, si abbia $ac\equiv bc \bmod{m}$. Questo vorrebbe dire che $m \mid ac-bc$ (dove, come probabilmente sai benissimo se stai leggendo delle dispense in proposito, $\mid$ significa "divide": se $ac$ e $bc$ danno lo stesso resto nella divisione per $m$, allora la loro differenza non può che essere un multiplo di $m$, e viceversa). Ma da $m\mid c(a-b)$ puoi dedurre $m \mid a-b$ (cioè $a\equiv b \bmod{m}$) perché $c$ è primo con $m$ (se questo non ti è completamente chiaro a prima vista, pensa alla scomposizione in fattori primi degli interi coinvolti).
Al contrario, se $c$ ed $m$ hanno fattori primi in comune, l'argomento di sopra non funziona. Supponi che ci sia un primo $p$ tale che $p \mid c$ e $p \mid m$; prendi - ad esempio - $a=0$ e $b=m/p$. Allora $ac=0\equiv 0 \bmod{m}$ e $bc=m \cdot (c/p) \equiv 0 \bmod{m}$, ma naturalmente $a\not\equiv b \bmod{m}$.