Pagina 1 di 2
Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 12:34
da 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!

Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 13:34
da Drago96
scambret ha scritto: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)}}$.
scambret ha scritto: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

Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 14:43
da scambret
Drago96 ha scritto:P.S: usa

grazie per il ps, non sto usando il linguaggio LaTeX da un po di tempo.
Tornando a roba matematica:
Drago96 ha scritto: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

Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 15:16
da Drago96
scambret ha scritto:Drago96 ha scritto: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
scambret ha scritto: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)
Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 17:03
da scambret
Drago96 ha scritto:scambret ha scritto:Drago96 ha scritto: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
Drago96 ha scritto:scambret ha scritto: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!!

Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 18:39
da Drago96
scambret ha scritto:Drago96 ha scritto:scambret ha scritto: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!

Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 19:00
da scambret
Drago96 ha scritto:
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!
Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 19:21
da 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.
Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 19:25
da scambret
xXStephXx ha scritto: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!

Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 19:28
da 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$
Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 19:37
da scambret
xXStephXx ha scritto: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!
Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 19:46
da 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.
Re: Congruenze, scusate il titolo vago
Inviato: 28 giu 2012, 19:54
da scambret
xXStephXx ha scritto: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!
Re: Congruenze, scusate il titolo vago
Inviato: 29 giu 2012, 13:06
da scambret
xXStephXx ha scritto: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
Re: Congruenze, scusate il titolo vago
Inviato: 29 giu 2012, 14:10
da Drago96
scambret ha scritto: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$