OliForum Matematico

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

mi fai quasi venire nostaglia di HiTLeuLeR... Il famoso Lemma di Knuth!!!

Boll ha scritto:mi fai quasi venire nostaglia di HiTLeuLeR... Il famoso Lemma di Knuth!!!

non so se sia il lemma di questo tizio, ma è un esercizio semplice e bellino

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 $

Mio Dio
ma la soluzione 'olimpica' è di due righe ti sei molto complicato la vita

"olimpica" ?? non mi sembra che quel che ha usato stoppa esca di molto dalle olimpiadi (a parte il criterio della derivata).

EvaristeG ha scritto:"olimpica" ?? non mi sembra che quel che ha usato stoppa esca di molto dalle olimpiadi (a parte il criterio della derivata).

sì, mi riferivo a quello... comunque esiste una soluzione molto più semplice che richiede pochissime conoscenze di base. se qualcuno la vuole provare a trovare ...

Non sapendo se fosse olimpico non ho utilizzato il criterio della derivata, per dimostrere l'osservazione ho trovato esplicitamente le radici e ho applicato il teorema fondamntale dell'algebra...

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

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)

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.

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)

Si, io chiedevo l'1, anche perchè avevo detto:

salva90 ha scritto:interi positivi $ a\ge2 $

Comunque prendendo $ P(x)=x $ è comunque dimostrato anche quelllo che io chiedevo...

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

salva90 ha scritto:

edriv ha scritto:Comunque prendendo $ P(x)=x $ è comunque dimostrato anche quelllo che io chiedevo...

Non ho capito cosa intendi, potresti spiegare?

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 $