molto semplice, quindi sconsigliato agli esperti
gcd agli esponenti
gcd agli esponenti
Provare che $ gcd(a^m-1, a^n-1)=a^{gcd(m, n)}-1 $ per tutti gli interi positivi $ a \ge 2, m, n $
molto semplice, quindi sconsigliato agli esperti
molto semplice, quindi sconsigliato agli esperti
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
-
Stoppa2006
- Messaggi: 51
- Iscritto il: 28 nov 2006, 20:12
Ho trovato solo questa dimostrazione un pò "standard", ma dato che nessuno risponde la posto lo stesso:
Per semplicità di notazione pongo $ p_i(x)=x^{m_i}-1 $ allora $ \forall i=1,2 \ $:
$ (m_1,m_2)|m_i\Rightarrow \exists m_i'\in\mathbb{N}:\ x^{m_i}-1= $$ x^{(m_1,m_2)m_i'}-1= \left( x^{(m_1,m_2)}-1\right)\displaystyle\sum_{k=0}^{m_i-1}x^{(m_1,m_2)k} $
Allora:
$ x^{(m_1,m_2)}-1|x^{m_i}-1 $
Osservazione: I polinomi $ p_i(x) $ non hanno radici doppie (Si può fare anche con il criterio della derivata... ma non so se è olimpico).
Sia $ \xi_{m_i} $ una radice complessa $ m_i $-esima primitiva dell'unità, allora $ \{\xi_{m_i}^k|k=1,...,m_i\} $ e l'insieme delle radici di $ p_i(x) $ infatti $ \forall k\ p_i(\xi_{m_i}^k)=0 $ e sono esattamente $ m_i $. Per essere pignoli bisognerebbe dimostrare che queste radici sono tutte distinte ma è un fatto che dovrebbe essere noto a tutti...
Sia ora $ h(x) $ un divisore comune dei $ p_i $ e sia $ \alpha $ una radice complessa di $ h(x) $ allora $ p_i(\alpha)=0 $ quindi:
$ \forall i=1,2\ \alpha ^{m_i}-1=0\Rightarrow Ord(\alpha)|m_i $
E quindi $ Ord(\alpha)|(m_1,m_2)\Rightarrow (x-\alpha)|x^{(m_1,m_2)}-1 $
Allora poichè ogni radice di $ h(x) $ (che è una radice semplice per l'osservazione) è anche radice di $ x^{(m_1,m_2)}-1 $ allora:
$ h(x)|x^{(m_1,m_2)}-1 $
Per semplicità di notazione pongo $ p_i(x)=x^{m_i}-1 $ allora $ \forall i=1,2 \ $:
$ (m_1,m_2)|m_i\Rightarrow \exists m_i'\in\mathbb{N}:\ x^{m_i}-1= $$ x^{(m_1,m_2)m_i'}-1= \left( x^{(m_1,m_2)}-1\right)\displaystyle\sum_{k=0}^{m_i-1}x^{(m_1,m_2)k} $
Allora:
$ x^{(m_1,m_2)}-1|x^{m_i}-1 $
Osservazione: I polinomi $ p_i(x) $ non hanno radici doppie (Si può fare anche con il criterio della derivata... ma non so se è olimpico).
Sia $ \xi_{m_i} $ una radice complessa $ m_i $-esima primitiva dell'unità, allora $ \{\xi_{m_i}^k|k=1,...,m_i\} $ e l'insieme delle radici di $ p_i(x) $ infatti $ \forall k\ p_i(\xi_{m_i}^k)=0 $ e sono esattamente $ m_i $. Per essere pignoli bisognerebbe dimostrare che queste radici sono tutte distinte ma è un fatto che dovrebbe essere noto a tutti...
Sia ora $ h(x) $ un divisore comune dei $ p_i $ e sia $ \alpha $ una radice complessa di $ h(x) $ allora $ p_i(\alpha)=0 $ quindi:
$ \forall i=1,2\ \alpha ^{m_i}-1=0\Rightarrow Ord(\alpha)|m_i $
E quindi $ Ord(\alpha)|(m_1,m_2)\Rightarrow (x-\alpha)|x^{(m_1,m_2)}-1 $
Allora poichè ogni radice di $ h(x) $ (che è una radice semplice per l'osservazione) è anche radice di $ x^{(m_1,m_2)}-1 $ allora:
$ h(x)|x^{(m_1,m_2)}-1 $
sì, mi riferivo a quello... comunque esiste una soluzione molto più semplice che richiede pochissime conoscenze di base. se qualcuno la vuole provare a trovareEvaristeG ha scritto:"olimpica" ?? non mi sembra che quel che ha usato stoppa esca di molto dalle olimpiadi (a parte il criterio della derivata).
...[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
-
Stoppa2006
- Messaggi: 51
- Iscritto il: 28 nov 2006, 20:12
ok stoppa, la tua soluzione va bene in ogni caso 
comunque ripeto, ti sei incasinato la vita per un problemino facile
non serve algebra
non servono teoremoni
solo una piccola curiosità base
provateci su
comunque ripeto, ti sei incasinato la vita per un problemino facile
non serve algebra
non servono teoremoni
solo una piccola curiosità base
provateci su
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
Secondo me invece la dimostrazione di Stoppa ha qualcosa che non va...
Siano $ ~ m,n $ interi positivi.
1) dimostrare che, per ogni intero a > 1, si ha $ ~ (a^m-1,a^n-1) = a^{(m,n)} - 1 $
2) dimostrare che $ ~ (a^m-1,a^n-1) = a^{(m,n)} - 1 $.
Si noti che nel punto 1 parlo di un gcd di interi, nel punto 2 un gcd di polinomi (ho lasciato apposta la a al posto della x). Secondo me salva ha chiesto il punto 1), mentre Stoppa ha dimostrato il 2).
E comunque, il metodo di Stoppa per dimostrare il 2), cioè dare un'occhiata alle radici complesse, mi sembra molto naturale per quel problema. (il criterio della derivata e il th fondamentale dell'algebra non servono, che radici ci sono si può vederlo a mano)
Siano $ ~ m,n $ interi positivi.
1) dimostrare che, per ogni intero a > 1, si ha $ ~ (a^m-1,a^n-1) = a^{(m,n)} - 1 $
2) dimostrare che $ ~ (a^m-1,a^n-1) = a^{(m,n)} - 1 $.
Si noti che nel punto 1 parlo di un gcd di interi, nel punto 2 un gcd di polinomi (ho lasciato apposta la a al posto della x). Secondo me salva ha chiesto il punto 1), mentre Stoppa ha dimostrato il 2).
E comunque, il metodo di Stoppa per dimostrare il 2), cioè dare un'occhiata alle radici complesse, mi sembra molto naturale per quel problema. (il criterio della derivata e il th fondamentale dell'algebra non servono, che radici ci sono si può vederlo a mano)
-
Stoppa2006
- Messaggi: 51
- Iscritto il: 28 nov 2006, 20:12
Hai ragione, io ho considerato i polinomi e non gli interi. Poi vero, non ho usato proprio il teorema fondamentale dell'algebra, ma il fatto che in $ \mathbb{C} $ un polinomio di grado n non ha più di n radici contate con relativa molteplicità (principio di identità dei polinomi + Ruffini), e questo non è un fatto che vale in generale ma sfrutta le specifiche caratteristiche di $ \mathbb{C} $, ad esempio in $ \mathbb{Z}_6 $ questo non è vero, prendi ad esempio $ 3x=0 $ che ha come soluzioni 0,2,4 eppure è un polinomio di primo grado, quindi per dimostrare che tutte le radici sono distinte non basta trovbarle a mano perchè senza questi fatti nessuno garantisce che non ce ne siano altre.
Si, io chiedevo l'1, anche perchè avevo detto:edriv ha scritto:Secondo me invece la dimostrazione di Stoppa ha qualcosa che non va...
Siano $ ~ m,n $ interi positivi.
1) dimostrare che, per ogni intero a > 1, si ha $ ~ (a^m-1,a^n-1) = a^{(m,n)} - 1 $
2) dimostrare che $ ~ (a^m-1,a^n-1) = a^{(m,n)} - 1 $.
Si noti che nel punto 1 parlo di un gcd di interi, nel punto 2 un gcd di polinomi (ho lasciato apposta la a al posto della x). Secondo me salva ha chiesto il punto 1)
Comunque prendendo $ P(x)=x $ è comunque dimostrato anche quelllo che io chiedevo...salva90 ha scritto:interi positivi $ a\ge2 $
Ricordo comunque l'esistenza di una soluzione elementare FACILE, che fa uso solo di una piccolissima conoscenza di TdN, senza scomodare teoremoni et similia, e vi invito a provare a trovare quella, visto che è anche bellino come esercizio
volendo, con lo stesso identico metodo si può dimostrare che funziona anche coi polinomi, ma vediamo di restare IT che siamo in TdN
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Visto che nessuno lo caga o vuole scrivere una soluzione..
Sia $ b=a^{(m,n)} $
$ m=(m,n)(k) $
$ n=(m,n)(j) $
con $ k>j $ e $ (k,j)=1 $
Scomponendo:
$ (a^n-1,a^m-1)=(b-1)(1+\dots+b^{j-1},1+\dots+b^{k-1}) $
Sottraendo al termine maggiore il minore e raccogliendo:
$ =(b-1)(1+\dots+b^{j-1},b^{j}(1+\dots+b^{k-j-1})) $
Buttando via uin fattore coprimo con la prima sommatoria:
$ =(b-1)(1+\dots+b^{j-1},1+\dots+b^{k-j-1}) $
Chiamo ora $ j_1-1=j-1 $ e $ k_1-1=k-j-1 $.
Domanda: posso reiterare (abbassare sempre il grado del massimo esponente di b che incontro nell'espressione fino a che diventi 0?)
Risposta: si a meno che i gradi massimi di entrambe le sommatorie siano ad un certo punto uguali.
Se così fosse otterrei $ j_i-1 =k_i-1 $ e anche $ j_i=k_i $ .
Ma se noto bene i termini $ j_i $ e $ k_i $ sono ottenuti applicando l'algorimo di euclide ai precedenti (nome altisonante per dire che sottraggo al maggiore il minore e il gcd rimane uguale) e saranno quindi distinti o saranno tutti e due $ 1=(k,j) $ .
Posso quindi reiterare ottenendo:
$ (b-1)(1+\dots+b^{j-1},1+\dots+b^{k-j-1}) = $
$ (b-1)(1+\dots+b^{(k,j)-1},1+\dots+b^{(k,j)-1})=(b-1) (1,1)=b-1 $
Si si, mi sono accorto che se non scomponevo si faceva veramente in due righe ma vabbè non ho voglia di riscrivere
Non so se sono solo i meiei ricordi del wc che mi ingannano ma..
Rilanciamo dai
$ (a^m-b^m,a^n-b^n)=a^{(m,n)}-b^{(m,n)} $ con $ (a,b)=1 $
Sia $ b=a^{(m,n)} $
$ m=(m,n)(k) $
$ n=(m,n)(j) $
con $ k>j $ e $ (k,j)=1 $
Scomponendo:
$ (a^n-1,a^m-1)=(b-1)(1+\dots+b^{j-1},1+\dots+b^{k-1}) $
Sottraendo al termine maggiore il minore e raccogliendo:
$ =(b-1)(1+\dots+b^{j-1},b^{j}(1+\dots+b^{k-j-1})) $
Buttando via uin fattore coprimo con la prima sommatoria:
$ =(b-1)(1+\dots+b^{j-1},1+\dots+b^{k-j-1}) $
Chiamo ora $ j_1-1=j-1 $ e $ k_1-1=k-j-1 $.
Domanda: posso reiterare (abbassare sempre il grado del massimo esponente di b che incontro nell'espressione fino a che diventi 0?)
Risposta: si a meno che i gradi massimi di entrambe le sommatorie siano ad un certo punto uguali.
Se così fosse otterrei $ j_i-1 =k_i-1 $ e anche $ j_i=k_i $ .
Ma se noto bene i termini $ j_i $ e $ k_i $ sono ottenuti applicando l'algorimo di euclide ai precedenti (nome altisonante per dire che sottraggo al maggiore il minore e il gcd rimane uguale) e saranno quindi distinti o saranno tutti e due $ 1=(k,j) $ .
Posso quindi reiterare ottenendo:
$ (b-1)(1+\dots+b^{j-1},1+\dots+b^{k-j-1}) = $
$ (b-1)(1+\dots+b^{(k,j)-1},1+\dots+b^{(k,j)-1})=(b-1) (1,1)=b-1 $
Si si, mi sono accorto che se non scomponevo si faceva veramente in due righe ma vabbè non ho voglia di riscrivere
Non so se sono solo i meiei ricordi del wc che mi ingannano ma..
Rilanciamo dai
$ (a^m-b^m,a^n-b^n)=a^{(m,n)}-b^{(m,n)} $ con $ (a,b)=1 $
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.