Allora...
Mi piacerebbe chiarire un pò di regole sulle congruenze...
se noi ad esempio abbiamo
$ \dispaystyle
a+b \equiv c \pmod{p} $
$ \dispaystyle
a \equiv a_{r} \pmod{p} $
dove $ \dispaystyle a_{r} $ è il residuo di $ \dispaystyle a $
E' possibile fare questo passaggio?
$
\dispaystyle
a_{r}+b \equiv c \pmod{p} $
Oppure volendo fare un'altro esempio
$ \dispaystyle \\
a \cdot b \equiv c \pmod{p} \\
a \equiv a_{r} \pmod{p} \\
a_{r} \cdot b \equiv c \pmod{p}
$
Stesso discorso vale per le potende e tutte le altre operazioni...
Ovvero la domanda si riduce a questo: e' possibile scambiare numeri con residui a mio piacimento?E' sempre possibile?
CONGRUENZE
CONGRUENZE
Ultima modifica di angus89 il 22 feb 2008, 17:23, modificato 1 volta in totale.
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Non sempre funziona. Per somma, sottrazione e moltiplicazione è facilmente dimostrabile sostituendo ad a $ np+a_r $, per le potenze è valido solo alla base applicando ciò che è appena stato dimostrato per le moltiplicazioni, per esponente e per la divisione si vede che è sbagliato con facili controesempi. In genere è questo che ti serve in TdN, ma anche per funzioni più complesse non è molto difficile vedere come la cosa funzioni.
ok i casi che hai riportato tu sono facilmente dimostrabili
vediamo...ad esempio in questo caso
$ \displaystyle \\ a \equiv a_{r} \pmod{p} \\ (a+b)^{g} \equiv c \pmod{p} \\ (a_{r}+b)^{g} \equiv c \pmod{p} \\ $
E' lecita la sostituzione scarto-numero?
Quali sono i limiti di queste sostituzioni?
Tipo nelle divisioni non è sempre lecito...
In quali altri casi non è lecito?
vediamo...ad esempio in questo caso
$ \displaystyle \\ a \equiv a_{r} \pmod{p} \\ (a+b)^{g} \equiv c \pmod{p} \\ (a_{r}+b)^{g} \equiv c \pmod{p} \\ $
E' lecita la sostituzione scarto-numero?
Quali sono i limiti di queste sostituzioni?
Tipo nelle divisioni non è sempre lecito...
In quali altri casi non è lecito?
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
$ a \equiv_p a_r \Longleftrightarrow \exists t \in \mathbb{Z} $ t.c. $ a-a_r=pt \Longleftrightarrow a-a_r+b-b=pt \Longleftrightarrow a+b \equiv_p a_r+b $
Inoltre $ a+b = a_r+b +pt \Longleftrightarrow (a+b)^9 = (a_r+b +pt)^9 \Longleftrightarrow $$ (a+b)^9=(a_r+b)^9+kp \Longleftrightarrow (a+b)^9 \equiv_p (a_r+b)^9 $, dove $ k \in \mathbb{Z} $ è la robaccia che esce dallo sviluppo del binomio di Newton, ed è tutta multipla di p. Nota bene che tutti i passaggi sono invertibili
Inoltre $ a+b = a_r+b +pt \Longleftrightarrow (a+b)^9 = (a_r+b +pt)^9 \Longleftrightarrow $$ (a+b)^9=(a_r+b)^9+kp \Longleftrightarrow (a+b)^9 \equiv_p (a_r+b)^9 $, dove $ k \in \mathbb{Z} $ è la robaccia che esce dallo sviluppo del binomio di Newton, ed è tutta multipla di p. Nota bene che tutti i passaggi sono invertibili
Più in astratto, dal fatto che addizione e moltiplicazione "funzionano" su 2 elementi, puoi dedurre, applicando più volte il risultato, che funzionano su qualunque composizione, complicata a piacere, di queste operazioni, tra cui quella citata da Angus:
$ \displaystyle \\ a \equiv a_{r} \pmod{p} \\ $
implica
$ \displaystyle \\ a+b \equiv a_{r}+b \pmod{p} \\ $
implica
$ \displaystyle \\ (a+b)(a+b) \equiv (a_{r}+b)(a+b) \pmod{p} \\ $
implica
$ \displaystyle \\ (a+b)(a+b) \equiv (a_{r}+b)(a_r+b) \pmod{p} \\ $
e così via...
implica
$ \displaystyle \\ (a+b)^g \equiv (a_{r}+b)^g \pmod{p} \\ $
$ \displaystyle \\ a \equiv a_{r} \pmod{p} \\ $
implica
$ \displaystyle \\ a+b \equiv a_{r}+b \pmod{p} \\ $
implica
$ \displaystyle \\ (a+b)(a+b) \equiv (a_{r}+b)(a+b) \pmod{p} \\ $
implica
$ \displaystyle \\ (a+b)(a+b) \equiv (a_{r}+b)(a_r+b) \pmod{p} \\ $
e così via...
implica
$ \displaystyle \\ (a+b)^g \equiv (a_{r}+b)^g \pmod{p} \\ $
Mettiamo ordine, ok?
Def: Fissato $ m $ numero intero, due interi $ a,\ b $ si dicono congrui modulo m e si scrive
$ a\equiv b\mod m $
se $ m\vert a-b $ (ovvero se m divide a-b).
Modi equivalenti di dirlo sono: $ a=b+km $ per qualche intero k; a,b hanno lo stesso resto nella divisione per m.
Somma, differenza, moltiplicazione
Se $ a\equiv b\mod m $ e $ c\equiv d\mod m $, allora
$ b+d=(a+c)+(h+k)m $
$ b-d=(a-c)+(k-h)m $
$ bd=ac+(ah+ck+hkm)m $
e queste sono proprio le tre conclusioni a cui volevamo arrivare.
Osservazione
Se $ p(x)=a_0x^n+\ldots+a_n $ è un polinomio a coefficienti interi, allora
$ a\equiv b\mod m $ implica $ p(a)\equiv p(b)\mod m $.
Dim: E' ben noto che $ a-b \vert p(a)-p(b) $ e dunque, se $ m\vert a-b $, allora $ m\vert p(a)-p(b) $.
(L'osservazione si può anche dimostrare osservando che valutare un polinomio in a vuol dire fare solo somme e prodotti; se dunque b è congruo ad a, facendo le stesse somme e gli stessi prodotti con b al posto di a si ottiene lo stesso risultato modulo m).
Generalizzazione 1
Se $ p(x,y) $ è un polinomio a coefficienti interi in due variabili, allora $ a\equiv b\mod m $ e $ c\equiv d\mod m $ implicano $ p(a,c)\equiv p (b,d)\mod m $.
Dim: Scriviamo
$ p(x,y)=\sum_{i,j} \alpha_{ij}x^iy^j $ (con $ \alpha_{ij} $ interi)
allora, se $ a\equiv b\mod m $ e $ c\equiv d\mod m $, si ha
$ a^i\equiv b^i\mod m $, $ c^j\equiv d^j\mod m $ e dunque
$ a^ic^j\equiv b^id^j\mod m $ e, poichè $ \alpha_{ij}\equiv \alpha_{ij}\mod m $ (ogni intero è congruo a se stesso), si ha
$ \alpha_{ij}a^ic^j\equiv \alpha_{ij}b^id^j\mod m $
per ogni monomio di p(x,y); quindi sommandoli tutti otteniamo
$ p(a,c)\equiv p(b,d)\mod m $.
(Questa cosa si estende al caso di polinomi in n variabili, purché a coefficienti interi).
Generalizzazione 2
Se $ a_i\equiv b_i\mod m $ per $ i=0,\ldots, n $, allora, posto
$ p(x)=a_0x^n+\ldots+a_n $ e $ q(x)=b_0x^n+\ldots+b_n $,
si ha che $ k\equiv h\mod m $ implica
$ p(k)\equiv q(h)\mod m $
Dim: $ k\equiv h\mod m $ e dunque $ k^i\equiv h^i\mod m $ e dunque $ a_{n-i}k^i\equiv b_{n-i}h^i\mod m $ e infine sommando su i si ottiene la tesi.
Si possono mettere assieme le due generalizzazioni, ma dovrebbe essere abbastanza ovvio, per cui evito di scriverlo con precisione; il succo è che se due polinomi in più variabili hanno i coefficienti dei monomi corrispondenti congrui modulo m e vengono calcolati in valori congrui modulo m, anche i risultati saranno congrui modulo m.
Esempi
1) $ x\equiv y\mod m $ implica $ x^n\equiv y^n\mod m $ per ogni n, quindi per sapere quali sono le n-esime potenze modulo m, basta calcolare quelle di m numeri che rappresentino tutti i possibili resti (ad esempio {0,1,...,m-1}).
2) $ (x+y)^p\equiv x^p+y^p\mod p $ con p numero primo.
Si ha $ (x+y)^p=\sum_{k=0}^p{p\choose k}x^ky^{p-k} $
e si osserva che $ p\not\vert k!(p-k)! $ se p>k>0 e dunque $ p\vert {p\choose k} $ se p>k>0. Quindi
$ (x+y)^p=x^p+ p(\ldots)+y^p $
ovvero
$ (x+y)^p\equiv x^p+y^p\mod p $
Esercizio Dimostrare che $ x^2-46x+1 $ è sempre un quadrato modulo 24. Ovvero che, per ogni x intero, esiste un y intero tale che $ x^2-46x+1\equiv y^2\mod 24 $.
Cosa non si può fare
Non si può dividere, in generale:
$ 2\equiv 12\mod 10 $ e $ 2\equiv 2\mod 10 $ ma $ 1\not\equiv6\mod 10 $.
$ 18\equiv 60\mod 14 $ e $ 6\equiv 6\mod 14 $ ma $ 3\not\equiv10\mod14 $
Non si può ridurre l'esponente di un elevamento a potenza modulo m:
$ 3\equiv 6\mod 3 $ e $ 2\equiv2\mod 3 $ ma $ 2^3\equiv2\mod 3 $ mentre $ 2^6\equiv1\mod 3 $
$ 9\equiv 2\mod 7 $ e $ 3\equiv 10\mod 7 $ ma $ 9^3\equiv1\mod 7 $ mentre $ 2^{10}\equiv2\mod 7 $
Quando si può dividere
Se $ (m,c)=1 $ allora esiste un numero $ d $ tale che $ cd\equiv 1\mod m $ (perché?); allora, se $ a\equiv b\mod m $, ha senso dire che $ a/c\equiv b/c\mod m $ intendendo che $ c^{-1}\equiv d\mod m $ (è quel numero che moltiplicato per c fa 1, è il suo inverso modulo m); dunque si sta solo dicendo che $ ad\equiv bd\mod m $.
Se dunque $ a\equiv b\mod m $ e $ x=(a,b) $, nel caso in cui $ (m,x)=1 $, allora si può dire $ a/x\equiv b/x\mod m $.
Ad esempio, $ 3\equiv24\mod 7 $ e poichè (3,7)=1 (dove 3=(3,24)), vale anche $ 1\equiv 8\mod 7 $.
Se invece c'è un fattore d comune ad a,b,m, ovvero se $ a=da',\ b=db',\ m=dm' $, e vale $ a\equiv b\mod m $ allora possiamo "dividere" solo dividendo anche il modulo:
$ (a/d)\equiv(b/d)\mod (m/d) $ ovvero $ a'\equiv b'\mod m' $.
Ad esempio, $ 2\equiv 10\mod 8 $ implica $ 1\equiv 5\mod 4 $.
Per ridurre gli esponenti il discorso si fa più complicato e probabilmente c'è già da qualche altra parte nel glossario.
Def: Fissato $ m $ numero intero, due interi $ a,\ b $ si dicono congrui modulo m e si scrive
$ a\equiv b\mod m $
se $ m\vert a-b $ (ovvero se m divide a-b).
Modi equivalenti di dirlo sono: $ a=b+km $ per qualche intero k; a,b hanno lo stesso resto nella divisione per m.
Somma, differenza, moltiplicazione
Se $ a\equiv b\mod m $ e $ c\equiv d\mod m $, allora
- $ a+c\equiv b+d\mod m $
- $ a-c\equiv b-d\mod m $
- $ ac\equiv bd\mod m $
$ b+d=(a+c)+(h+k)m $
$ b-d=(a-c)+(k-h)m $
$ bd=ac+(ah+ck+hkm)m $
e queste sono proprio le tre conclusioni a cui volevamo arrivare.
Osservazione
Se $ p(x)=a_0x^n+\ldots+a_n $ è un polinomio a coefficienti interi, allora
$ a\equiv b\mod m $ implica $ p(a)\equiv p(b)\mod m $.
Dim: E' ben noto che $ a-b \vert p(a)-p(b) $ e dunque, se $ m\vert a-b $, allora $ m\vert p(a)-p(b) $.
(L'osservazione si può anche dimostrare osservando che valutare un polinomio in a vuol dire fare solo somme e prodotti; se dunque b è congruo ad a, facendo le stesse somme e gli stessi prodotti con b al posto di a si ottiene lo stesso risultato modulo m).
Generalizzazione 1
Se $ p(x,y) $ è un polinomio a coefficienti interi in due variabili, allora $ a\equiv b\mod m $ e $ c\equiv d\mod m $ implicano $ p(a,c)\equiv p (b,d)\mod m $.
Dim: Scriviamo
$ p(x,y)=\sum_{i,j} \alpha_{ij}x^iy^j $ (con $ \alpha_{ij} $ interi)
allora, se $ a\equiv b\mod m $ e $ c\equiv d\mod m $, si ha
$ a^i\equiv b^i\mod m $, $ c^j\equiv d^j\mod m $ e dunque
$ a^ic^j\equiv b^id^j\mod m $ e, poichè $ \alpha_{ij}\equiv \alpha_{ij}\mod m $ (ogni intero è congruo a se stesso), si ha
$ \alpha_{ij}a^ic^j\equiv \alpha_{ij}b^id^j\mod m $
per ogni monomio di p(x,y); quindi sommandoli tutti otteniamo
$ p(a,c)\equiv p(b,d)\mod m $.
(Questa cosa si estende al caso di polinomi in n variabili, purché a coefficienti interi).
Generalizzazione 2
Se $ a_i\equiv b_i\mod m $ per $ i=0,\ldots, n $, allora, posto
$ p(x)=a_0x^n+\ldots+a_n $ e $ q(x)=b_0x^n+\ldots+b_n $,
si ha che $ k\equiv h\mod m $ implica
$ p(k)\equiv q(h)\mod m $
Dim: $ k\equiv h\mod m $ e dunque $ k^i\equiv h^i\mod m $ e dunque $ a_{n-i}k^i\equiv b_{n-i}h^i\mod m $ e infine sommando su i si ottiene la tesi.
Si possono mettere assieme le due generalizzazioni, ma dovrebbe essere abbastanza ovvio, per cui evito di scriverlo con precisione; il succo è che se due polinomi in più variabili hanno i coefficienti dei monomi corrispondenti congrui modulo m e vengono calcolati in valori congrui modulo m, anche i risultati saranno congrui modulo m.
Esempi
1) $ x\equiv y\mod m $ implica $ x^n\equiv y^n\mod m $ per ogni n, quindi per sapere quali sono le n-esime potenze modulo m, basta calcolare quelle di m numeri che rappresentino tutti i possibili resti (ad esempio {0,1,...,m-1}).
2) $ (x+y)^p\equiv x^p+y^p\mod p $ con p numero primo.
Si ha $ (x+y)^p=\sum_{k=0}^p{p\choose k}x^ky^{p-k} $
e si osserva che $ p\not\vert k!(p-k)! $ se p>k>0 e dunque $ p\vert {p\choose k} $ se p>k>0. Quindi
$ (x+y)^p=x^p+ p(\ldots)+y^p $
ovvero
$ (x+y)^p\equiv x^p+y^p\mod p $
Esercizio Dimostrare che $ x^2-46x+1 $ è sempre un quadrato modulo 24. Ovvero che, per ogni x intero, esiste un y intero tale che $ x^2-46x+1\equiv y^2\mod 24 $.
Cosa non si può fare
Non si può dividere, in generale:
$ 2\equiv 12\mod 10 $ e $ 2\equiv 2\mod 10 $ ma $ 1\not\equiv6\mod 10 $.
$ 18\equiv 60\mod 14 $ e $ 6\equiv 6\mod 14 $ ma $ 3\not\equiv10\mod14 $
Non si può ridurre l'esponente di un elevamento a potenza modulo m:
$ 3\equiv 6\mod 3 $ e $ 2\equiv2\mod 3 $ ma $ 2^3\equiv2\mod 3 $ mentre $ 2^6\equiv1\mod 3 $
$ 9\equiv 2\mod 7 $ e $ 3\equiv 10\mod 7 $ ma $ 9^3\equiv1\mod 7 $ mentre $ 2^{10}\equiv2\mod 7 $
Quando si può dividere
Se $ (m,c)=1 $ allora esiste un numero $ d $ tale che $ cd\equiv 1\mod m $ (perché?); allora, se $ a\equiv b\mod m $, ha senso dire che $ a/c\equiv b/c\mod m $ intendendo che $ c^{-1}\equiv d\mod m $ (è quel numero che moltiplicato per c fa 1, è il suo inverso modulo m); dunque si sta solo dicendo che $ ad\equiv bd\mod m $.
Se dunque $ a\equiv b\mod m $ e $ x=(a,b) $, nel caso in cui $ (m,x)=1 $, allora si può dire $ a/x\equiv b/x\mod m $.
Ad esempio, $ 3\equiv24\mod 7 $ e poichè (3,7)=1 (dove 3=(3,24)), vale anche $ 1\equiv 8\mod 7 $.
Se invece c'è un fattore d comune ad a,b,m, ovvero se $ a=da',\ b=db',\ m=dm' $, e vale $ a\equiv b\mod m $ allora possiamo "dividere" solo dividendo anche il modulo:
$ (a/d)\equiv(b/d)\mod (m/d) $ ovvero $ a'\equiv b'\mod m' $.
Ad esempio, $ 2\equiv 10\mod 8 $ implica $ 1\equiv 5\mod 4 $.
Per ridurre gli esponenti il discorso si fa più complicato e probabilmente c'è già da qualche altra parte nel glossario.
Inanzitutto ringrazio EvaristeG per la spiegazione...(come al solito XD)
Poi visto che siamo in argomento...E visto che mi sembra un argomento su cui è meglio andarci piano e fare attenzione a ogni singola affermazione...
Mi è venuto in mente un principio che viene utilizzato spesso nelle congrunze...
Sò per certo che è valido nelle congruenze a modulo primo ma non ho mai visto una dimostrazione e non mi pare nenache tanto evidente.
Tipo...il teorema di Wilson che afferma che
$ \dispaystyle (p-1)! \equiv -1 \pmod{p} $
e si dimostra con il concetto di inverso.
Qui voglio attrarre l'attenzione...
Nella normale aritmetica l'inverso (che è anche detto recirpoco) è quel numero che moltiplicato per un numero dato restituisce l'elemento neutro $ \dispaystyle 1 $
$ \displaystyle a \cdot b = 1 $
In questo caso$ \dispaystyle b $ è l'inverso di $ \dispaystyle a $e viceversa.
Nelle congruenze vale la stessa cosa...
$ \dispaystyle a \cdot b \equiv 1 \pmod{p} $
Bene...la domanda è questa...
Cosa ci garantisce che tra i residui (o scarti) ad ogni numero(esculo $ \dispaystyle 0 $ o $ \dispaystyle p $ che è lo stesso) esiste il reciproco?
Poi visto che siamo in argomento...E visto che mi sembra un argomento su cui è meglio andarci piano e fare attenzione a ogni singola affermazione...
Mi è venuto in mente un principio che viene utilizzato spesso nelle congrunze...
Sò per certo che è valido nelle congruenze a modulo primo ma non ho mai visto una dimostrazione e non mi pare nenache tanto evidente.
Tipo...il teorema di Wilson che afferma che
$ \dispaystyle (p-1)! \equiv -1 \pmod{p} $
e si dimostra con il concetto di inverso.
Qui voglio attrarre l'attenzione...
Nella normale aritmetica l'inverso (che è anche detto recirpoco) è quel numero che moltiplicato per un numero dato restituisce l'elemento neutro $ \dispaystyle 1 $
$ \displaystyle a \cdot b = 1 $
In questo caso$ \dispaystyle b $ è l'inverso di $ \dispaystyle a $e viceversa.
Nelle congruenze vale la stessa cosa...
$ \dispaystyle a \cdot b \equiv 1 \pmod{p} $
Bene...la domanda è questa...
Cosa ci garantisce che tra i residui (o scarti) ad ogni numero(esculo $ \dispaystyle 0 $ o $ \dispaystyle p $ che è lo stesso) esiste il reciproco?
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
-
¬[ƒ(Gabriel)³²¹º]¼+½=¾
- Messaggi: 849
- Iscritto il: 22 ott 2006, 14:36
- Località: Carrara/Pisa
Se non ho capito male chiedi qundo esiste l'inverso di un numero intero a modulo m..angus89 ha scritto:Bene...la domanda è questa...
Cosa ci garantisce che tra i residui (o scarti) ad ogni numero(esculo $ \dispaystyle 0 $ o $ \dispaystyle p $ che è lo stesso) esiste il reciproco?
è invertibile sse $ (a,m)=1 $ perchè lo trovi con la diofantea $ ab + km = 1 $
In definitiva è sempre invertibile?¬[ƒ(Gabriel)³²¹º]¼+½=¾ ha scritto: Se non ho capito male chiedi qundo esiste l'inverso di un numero intero a modulo m..
è invertibile se $ (a,m)=1 $ perchè lo trovi con la diofantea $ ab + km = 1 $
A...ancora una cosa...è per caso $ ab - km = 1 $?
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Oppure, per dimostrarlo direttamente senza ricorrere a Bezout, si dimostra che, se $ (a,p)=1 $, allora i numeri $ a $, $ 2a $, ..., $ (p-1)a $ sono tutti diversi tra di loro modulo p. Supponiamo per assurdo che non sia vero. Allora esistono $ h $ e $ k $ distinti, con $ 1 \leq k < h \leq (p-1) $ tali che $ p | (h-k)a $. Ma allora $ p | (h-k) $, cioè p divide un numero compreso tra 1 e (p-1).
Mah, dopo un po' che ci si sta intorno diventa abbastanza chiaro cosa si può fare e cosa non si può fare... Ci sono cose in cui bisogna essere molto più pignoli...E visto che mi sembra un argomento su cui è meglio andarci piano e fare attenzione a ogni singola affermazione...
Se (a,m)=1, allora l'inverso di a modulo m esiste sempre. Comunque si ragiona sempre sugli interi in generale, quindi compresi i negativi, perciò che sia +k o -k non cambia nulla...In definitiva è sempre invertibile?
A...ancora una cosa...è per caso ab - km = 1?
Va bè mi basta questo...anche perchè in definitiva (a,m)=1 è sempre valida per m primo...che è proprio il caso che tratta il teorema di wilson...grazie!!!Pigkappa ha scritto:Se (a,m)=1, allora l'inverso di a modulo m esiste sempre. Comunque si ragiona sempre sugli interi in generale, quindi compresi i negativi, perciò che sia +k o -k non cambia nulla...
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
bè avrete notato che ho cambiato il nume del post..tanto per esser più coerenti visto che si stà parlando di congruenze in generale...
Va bè questa volta un'osservazione(da confermare o eventualmente correggere) e una domanda...
Osservazione
se abbiamo una congruenza del tipo
$ \dispaystyle f(x) \equiv 0 \pmod{p} $
In base al grado di f(x) con il teorema di Lagrange possiamo afferermare che la congruenza ha al limite tante soluzioni in base al grado della conguenza.
Ma dato che stiamo utilizzando un modulo primo dove è applicabile fermat...non possiamo affermare che ci sono al limite (p-1) soluzioni?
Faccio un esempio veloce...il grado di f(x) è 10 (per Lagrange 10 soluzioni al massimo)
Il modulo è 7 (con la semplificazione del terorema di fermat p-1 soluzioni)
Allora?
E' possibile farlo?
E poi la domanda seria...
Il mio testo fà un mezzo casino per dimostrare il teorema di Chevalley...
Inanzitutto non ho neanche compreso bene l'enunciato...
Per farla breve il teorema afferma che data una funzione a più variabili
$ \displaystyle f(x_{1},x_{2},...,x_{n}) \equiv 0 \pmod{p} $
se il termine noto di f(x) è 0 allora la congruenze è sempre risolvibile oltre alla soluzione elementare
$ x_{1} \equiv x_{2} \equiv ... \equiv 0 \pmod{p} $
Pittosto che spiegare le perplessità che mi suscita il libro
...
Chiedo a chiunque conosca una semplice dimostrazione o abbia una dispensa...
Grazie in anticipo
Va bè questa volta un'osservazione(da confermare o eventualmente correggere) e una domanda...
Osservazione
se abbiamo una congruenza del tipo
$ \dispaystyle f(x) \equiv 0 \pmod{p} $
In base al grado di f(x) con il teorema di Lagrange possiamo afferermare che la congruenza ha al limite tante soluzioni in base al grado della conguenza.
Ma dato che stiamo utilizzando un modulo primo dove è applicabile fermat...non possiamo affermare che ci sono al limite (p-1) soluzioni?
Faccio un esempio veloce...il grado di f(x) è 10 (per Lagrange 10 soluzioni al massimo)
Il modulo è 7 (con la semplificazione del terorema di fermat p-1 soluzioni)
Allora?
E' possibile farlo?
E poi la domanda seria...
Il mio testo fà un mezzo casino per dimostrare il teorema di Chevalley...
Inanzitutto non ho neanche compreso bene l'enunciato...
Per farla breve il teorema afferma che data una funzione a più variabili
$ \displaystyle f(x_{1},x_{2},...,x_{n}) \equiv 0 \pmod{p} $
se il termine noto di f(x) è 0 allora la congruenze è sempre risolvibile oltre alla soluzione elementare
$ x_{1} \equiv x_{2} \equiv ... \equiv 0 \pmod{p} $
Pittosto che spiegare le perplessità che mi suscita il libro
...Chiedo a chiunque conosca una semplice dimostrazione o abbia una dispensa...
Grazie in anticipo
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Risolvere una congruenza del tipo
$ \displaystyle $ a \equiv b \pmod{p \cdot q \cdot r \cdot ...} $
con $ \displaystyle $ p,q,r,... $primi quivale a risolvere il sistema:
$ \displaystyle $ \begin{cases} a \equiv b \pmod{p}\\ a \equiv b \pmod{q}\\ a \equiv b \pmod{r} \\ ... \end{cases} $
risolvere invece una congruenza del tipo
$ \displaystyle $ a \equiv b \pmod{p^{\alpha}} $
A cosa equivale?
O più in generale
$ \displaystyle $ a \equiv b \pmod{p^{\alpha} \cdot q^{\beta} \cdot r^{\gamma} \cdot ...} $
A cosa equivale?
$ \displaystyle $ a \equiv b \pmod{p \cdot q \cdot r \cdot ...} $
con $ \displaystyle $ p,q,r,... $primi quivale a risolvere il sistema:
$ \displaystyle $ \begin{cases} a \equiv b \pmod{p}\\ a \equiv b \pmod{q}\\ a \equiv b \pmod{r} \\ ... \end{cases} $
risolvere invece una congruenza del tipo
$ \displaystyle $ a \equiv b \pmod{p^{\alpha}} $
A cosa equivale?
O più in generale
$ \displaystyle $ a \equiv b \pmod{p^{\alpha} \cdot q^{\beta} \cdot r^{\gamma} \cdot ...} $
A cosa equivale?
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Effettivamente ci stavo pensando adesso e l'unico vantaggio che si può trarre nell'usare un modulo con una potenza di un primo è nell'usare il piccolo teorema di fermat (con la variante della funzione di Eulero, e con il vantaggio di poter determinare la funzione per quella determinata potenza del numero primo)...Pigkappa ha scritto:Risolvere $ \displaystyle a\equiv b \pmod m $ equivale a risolvere $ \displaystyle a\equiv b $ modulo i fattori primi tra loro che dividono m. Se m è la potenza di un primo, in sostanza, non ci puoi fare niente...
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui