Dubbio sulle congruenze

[flutist001]

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...

[phi]

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.

[jordan]

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$..

[flutist001]

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.

Chiedo scusa , non mi ero accorto proprio di quella sezione!La prossima volta farò così.

Il dubbio che rimane è da dove e come tu abbia dedotto la tua ultima affermazione.

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 grato

[phi]

In realtà ho sbagliato io pensando che valesse anche l'inverso.

Immaginavo che il problema fosse qualcosa del genere.

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}$.