Congruenze, scusate il titolo vago

[scambret]

Se ho che $ x \cong y $ (mod $ z $) posso dire che $ 2x \cong 2y $ (mod $ 2z $)??
E un'altra cosa:
Se ho un sistema di congruenze
$ nx \cong 0 $ (mod 2k) e $ x \cong h $ (mod k) posso dire che $ nh \cong 0 $ (mod 2k)?? Chi mi garantisce che ciò è vero?? Grazie mille e scusate la mia ignoranza!

[Drago96]

Se ho che $ x \cong y $ (mod $ z $) posso dire che $ 2x \cong 2y $ (mod $ 2z $)??

Direi di sì... Devi fare più attenzione con la divisione, invece : $ac \equiv bc \pmod n\rightarrow a \equiv b \pmod {\frac n {\gcd(n, c)}}$.

Se ho un sistema di congruenze
$ nx \cong 0 $ (mod 2k) e $ x \cong h $ (mod k) posso dire che $ nh \cong 0 $ (mod 2k)??

No, però puoi dire $nh\equiv 0\pmod k$

P.S: usa

Codice: Seleziona tutto

a \equiv b \pmod n

[scambret]

P.S: usa

Codice: Seleziona tutto

a \equiv b \pmod n

grazie per il ps, non sto usando il linguaggio LaTeX da un po di tempo.

Tornando a roba matematica:

No, però puoi dire $nh\equiv 0\pmod k$

come lo posso dire? Cioè presumo che ci sia qualche teorema.

Inoltre perchè se $ a^m \equiv b^n \pmod \alpha $ allora $ m \equiv n \pmod {\phi(\alpha)} $.
Grazie mille

[Drago96]

No, però puoi dire $nh\equiv 0\pmod k$

come lo posso dire? Cioè presumo che ci sia qualche teorema.

Nulla di che: $nx\equiv 0\pmod{2k}\rightarrow nx\equiv 0\pmod{k}$ e dato che $x\equiv h\pmod k$, lo puoi sostituire

Inoltre perchè se $ a^m \equiv b^n \pmod \alpha $ allora $ m \equiv n \pmod {\phi(\alpha)} $.
Grazie mille

Anche questo mi pare poco vero... $2^3\equiv3^5\pmod5$ ma $3\not\equiv5\pmod 4$
Al massimo puoi dire $a^m\equiv a^n\pmod b\rightarrow m\equiv n\pmod{\phi(b)}$ (dovrebbe servirti anche l'ipotesi $(a,b)=1$, ma non ne sono sicuro)

[scambret]

No, però puoi dire $nh\equiv 0\pmod k$

come lo posso dire? Cioè presumo che ci sia qualche teorema.

Nulla di che: $nx\equiv 0\pmod{2k}\rightarrow nx\equiv 0\pmod{k}$ e dato che $x\equiv h\pmod k$, lo puoi sostituire

qui dopo me ne sono accorto di averti chiesto una gran fesseria

Inoltre perchè se $ a^m \equiv b^n \pmod \alpha $ allora $ m \equiv n \pmod {\phi(\alpha)} $.
Grazie mille

Anche questo mi pare poco vero... $2^3\equiv3^5\pmod5$ ma $3\not\equiv5\pmod 4$
Al massimo puoi dire $a^m\equiv a^n\pmod b\rightarrow m\equiv n\pmod{\phi(b)}$ (dovrebbe servirti anche l'ipotesi $(a,b)=1$, ma non ne sono sicuro)

C'e sotto qualche giustificazione banale o è qualcosa di abbastanza complesso?
Ps grazie mille Drago96!!

[Drago96]

Inoltre perchè se $ a^m \equiv b^n \pmod \alpha $ allora $ m \equiv n \pmod {\phi(\alpha)} $.
Grazie mille

Anche questo mi pare poco vero... $2^3\equiv3^5\pmod5$ ma $3\not\equiv5\pmod 4$
Al massimo puoi dire $a^m\equiv a^n\pmod b\rightarrow m\equiv n\pmod{\phi(b)}$ (dovrebbe servirti anche l'ipotesi $(a,b)=1$, ma non ne sono sicuro)

C'e sotto qualche giustificazione banale o è qualcosa di abbastanza complesso?
Ps grazie mille Drago96!!

Uhm... Ora che ci ripenso quella roba non è tanto vera... Direi invece $a^m\equiv a^n\pmod b\rightarrow m\equiv n\pmod{ord_b(a)}$, dato che (con una forzatura di notazione) $a^n\equiv a^{n \mod ord_b(a)}\pmod b$
Se invece non sono coprimi, la ripetizione dei residui c'è, ma in questo momento non riesco a trovare una regola generale... ci penso un po' e se trovo qualcosa ti faccio sapere O se qualcuno lo sa, si faccia avanti!

[scambret]

Al massimo puoi dire $a^m\equiv a^n\pmod b\rightarrow m\equiv n\pmod{\phi(b)}$ (dovrebbe servirti anche l'ipotesi $(a,b)=1$, ma non ne sono sicuro)

Però mi pare di averla sentita da qualche parte questa cosa! Ed ero abbastanza sicuro anche! spero di non ricordare male!

[xXStephXx]

Forse hai sentito solo una cosa del tipo: $\displaystyle a^k \equiv (a \pmod n )^{k \pmod{ \phi(n)}} \pmod n $ con $a$ ed $n$ coprimi.

[scambret]

Forse hai sentito solo una cosa del tipo: $\displaystyle a^k \equiv (a \pmod n )^{k \pmod{ \phi(n)}} \pmod n $ con $a$ ed $n$ coprimi.

Mmmh,no!

[xXStephXx]

Allora forse hai sentito l'inverso di quello che hai scritto prima che è valido.
Cioè se $a$ è coprimo con $b$ e $m \equiv n \pmod{ \phi(b)}$ allora $a^m \equiv a^n \pmod b$

[scambret]

Allora forse hai sentito l'inverso di quello che hai scritto prima che è valido.
Cioè se $a$ è coprimo con $b$ e $m \equiv n \pmod{ \phi(b)}$ allora $a^m \equiv a^n \pmod b$

Anche questo ma sapevo che era un se e solo se! E quello si dimostra con?

Ps scusate la mia ignoranza su questo argomento, ma è l argomento di TdN che digerisco peggio!

[xXStephXx]

Quello lo puoi dimostrare col teorema di eulero, ma non è un se e solo se.
Ad esempio: $2^2 \equiv 2^5 \pmod 7$
Sarebbe un se e solo se se anzichè usare la $\phi$ usassi l'ordine moltiplicativo.

[scambret]

Quello lo puoi dimostrare col teorema di eulero, ma non è un se e solo se.
Ad esempio: $2^2 \equiv 2^5 \pmod 7$
Sarebbe un se e solo se se anzichè usare la $\phi$ usassi l'ordine moltiplicativo.

Ok a me serviva per $\phi$. Mi farò bastare solo l'implicazione che voi mi avete detto, ma ero abbastanza sicuro e mi ricordavo anche di aver letto che era anche valido il se e solo se! Grazie mille comunque!

[scambret]

Quello lo puoi dimostrare col teorema di eulero, ma non è un se e solo se.
Ad esempio: $2^2 \equiv 2^5 \pmod 7$
Sarebbe un se e solo se se anzichè usare la $\phi$ usassi l'ordine moltiplicativo.

Scusa xXStephXx o chi vuole, avete da darmi un accenno di dimostrazione dell'implicaziome?? $ 6!+280 $ thanks

[Drago96]

Scusa xXStephXx o chi vuole, avete da darmi un accenno di dimostrazione dell'implicaziome?? $ 6!+280 $ thanks

Allora...
Sia $A=\{0<x<n : (x,n)=1\}$; ora ovviamente $|A|=\phi(n)$ e gli elementi di $A$ sono tutti diversi. Prendiamo un $a : (a,n)=1$ e definiamo come ovvio $aA := \{ax : x\in A\}$. Possiamo dire che $A=aA$, perchè $|aA|=|A|$, in $aA$ non ci può essere un elemento che in $A$ non c'è, perchè abbiamo tutte cose coprime, e non ci possono essere due elementi uguali, perchè vorrebbe dire $ax\equiv ay\pmod n\rightarrow x\equiv y\pmod n$ (dove $x,y\in A$) e ovviamente in $A$ non ci sono due elementi uguali.
Boh, ora moltiplichiamo tra loro tutti gli elementi di $A$ e otteniamo $mostro$; facciamo la stessa cosa con $aA$ e otteniamo $a^{\phi(n)}\cdot mostro$; dato che $A=aA$, allora $mostro\equiv a^{\phi(n)}\cdot mostro\pmod n$. Ma $mostro$ è invertibile, perchè ci sono tutti numeri coprimi: quindi semplifichiamo e abbiamo $a^{\phi(n)}\equiv1\pmod n$
E questo per dimostrare il teorema della phi di Eulero...
Ma ora conlcudiamo in fretta: se $b=q\cdot\phi(n)+r$ (divisione con resto di $b$ per $\phi(n)$), allora $a^b\equiv a^{q\cdot\phi(n)}\cdot a^r\equiv {a^{\phi(n)}}^q\cdot a^r\equiv1^q\cdot a^r\equiv a^r\pmod n$
Quindi se $m\equiv n\pmod{\phi(b)}\rightarrow m=m'\cdot\phi(b)+r, n=n'\cdot\phi(b)+r\rightarrow a^m\equiv a^r\equiv a^n\pmod b$