Lemmino sulla divisibilità delle potenze

[dario2994]

Uhm... questo lemmino facilotto l'ho trovato su Mathlinks... lo posto giusto perchè può far comodo
Dati $ $(n,a,b)\in\mathbb{N}^3 $ vale l'implicazione:
$ $ n|a^n-b^n\Rightarrow n|\sum_{i=0}^{n-1}a^ib^{n-i} $
Detto in parole spicce vuol dire che se n divide la differenza delle potenze n-esime allora divide anche quella sommatoria là

p.s. ovviamente da lasciare ai meno esperti

[Dani92]

Non reputandomi bravo in tdn (detto con sincerità visto cha martedì ho sbagliato tutto lo sbagliabile su questo argomento... ) ci provo io!

Guardando le congruenze modn e con Fermat dalla condizione ho che $ a \equiv b $ (modn)

Scrivendo per eteso la sommatoria (non serve ma mi piace di più ) vedo che $ b^n+ab^{n-1}+....+a^{n-1}b $ è un polinomio omogeneo di grado n, visto che ho detto che $ a \equiv b $ (modn), posso sostituire b con a ottenendo per Fermat $ a+a+a+....+a $ (modn). Questi termini sono $ \displaysyle n $ (sommatoria da 0 a n-1) quindi il tutto diventa $ n*a $, ovviamente divisibile per $ \displaysyle n $

[Reginald]

$ 9|5^9-2^9 $ ma 5 non è congruo a 2 modulo 9..

[trugruo]

Nessuno ha visto niente....

[Zorro_93]

Chiamo con S quella sommatoria
n | (a^n -b^n )
n | (a-b)*S

quindi n divide o (a-b) o S o entrambi
se divide S o entrambi si ha la tesi.
Supponiamo che non divida S,allora divide (a-b)
quindi a-b=0 (mod n) -> a=b (mod n)
e allora S diventa certamente divisibile per n.
E' giusto?

Secondo me è quasi giusto, nel senso che se n è composto il tuo ragionamento non vale, però, se si considera la fattorizzazione di n e si vede che :

-se tutti i primi che dividono n, dividono anche S allora ok.
-se c'è un primo che non divide S allora divide a-b e allora vale il tuo discorso.

[trugruo]

Chiamo con S quella sommatoria
n | (a^n -b^n )
n | (a-b)*S

quindi n divide o (a-b) o S o entrambi
se divide S o entrambi si ha la tesi.
Supponiamo che non divida S,allora divide (a-b)
quindi a-b=0 (mod n) -> a=b (mod n)
e allora S diventa certamente divisibile per n.
E' giusto?

Secondo me è quasi giusto, nel senso che se n è composto il tuo ragionamento non vale, però, se si considera la fattorizzazione di n e si vede che :

-se tutti i primi che dividono n, dividono anche S allora ok.
-se c'è un primo che non divide S allora divide a-b e allora vale il tuo discorso.

Sì ho scritto boiate....edito

[Reginald]

Ho trovato una soluzione originale credo, se funziona e non ho scritto castronate...=)

$ n=p_{a_1}^{a_1}*...p_m^{a_m} $ è la fattorizzazione di n.

Passo1: Dimostro prima di tutto che $ p_x^{a_x}|\sum_{i=0}^{n-1}{a_ib^{n-1-i}} $. Per ipotesi so che quel primo che chiamo d'ora in poi p^x divide a^n-b^n.
Distinguo ora in casi:
Caso 1:
$ p^x|a-b $. Ma allora ho la tesi, basta fare come ha fatto Dani92

Caso 2:
$ p^x\not | a-b $. Ma allora ho la tesi, perchè necessariamente in questo caso divide la sommatoria poichè divideva per ipotesi (a-b)(sommatoria)

Caso 3:
$ p^y|a-b $ con y minore di x.Mi sa che di questo punto ho trovato una dimostrazione carina se funge...
Allora, considero il polinomio $ a^{zp}-b^{zp} $ in modo che zp=n.. $ $a^{zp}-a^{zp}=(a^z-b^z)(\sum_{i=0}^{p-1}{a^{zi}b^{z(p-1+i)}}) $(1)..ora, posto che per ipotesi p|a-b allora divide anche a^z-b^z, quindi p dividerà anche la sommatoria della (1) perchè è come il caso 1.
Ora posso rifare la stessa operazione per ognuno dei divisori di z, che per mia fortuna, essendo $ z=p^{x-1}*k $, mi danno come minimo x-1 polimomi su cui fare quel lavoro, e quindi ho la tesi del passo 1 moltiplicando il tutto...

Rifaccio la stessa operazione per ogni primo che compare nella fattorizzazione di n ed ho che $ n|\sum_{i=0}^{n-1}{a^ib^{n-1-i}}\implies n|b*\sum_{i=0}^{n-1}{a^ib^{n-1-i}} $ che è la sommatoria ricercata..

[Dani92]

$ 9|5^9-2^9 $ ma 5 non è congruo a 2 modulo 9..

Perchè non vale Fermat? Cosa c'è che non va?

[trugruo]

ma per fermat intendi il piccolo teorema di fermat?
scusa l'ignoranza

[dario2994]

Uhm... prima di tutto mi scuso, ma il problema non è proprio facilotto-facilotto xD È che avevo sbagliato la soluzione xD Comunque ne esiste una più che abbordabile (se l'ho trovata io...)
@ Dani92: Fermat funge solo per i primi
@ trugruo: Il ragionamento funzionerebbe (o quasi) se n fosse libero da quadrati... prova a dimostrarlo, è una versione più debole di questo lemma
@ Reginald: Caso 1 perfetto; Caso 2 perfetto; Caso 3... alur

Posto $ $ zp=n $, considero il polinomio $ $a^{zp}-b^{zp} $
$ $a^{zp}-a^{zp}=(a^z-b^z)(\sum_{i=0}^{p-1}{a^{zi}b^{z(p-1+i)}}) $ (1)
Per ipotesi $ $ p|a-b\Rightarrow p|a^z-b^z $ quindi p dividerà anche la sommatoria della (1) perchè è come il caso 1.
Ora posso rifare la stessa operazione per ognuno dei divisori di z, che per mia fortuna, essendo $ $ z=p^{x-1}*k $, mi danno come minimo $ $ x-1 $ polimomi su cui fare quel lavoro, e quindi ho la tesi del passo 1 moltiplicando il tutto...

Ho riscritto, ma comunque c'è un bucone... quando dici di iterare il procedimento "per ognuno dei divisori di z" non capisco cosa intendi... ricorda che potresti ribeccare gli stessi primi e poi non capisco che intendi con moltiplicare tutto...
Comunque sei sulla buona strada (tra l'altro hai usato le mie stesse lettere xD)

[Dani92]

chiedo scusa... Mi ritiro nella mia ignoranza...

[Reginald]

@dario2994:non credo di aver capito bene cosa intendi...provo a scrivere meglio quello che dicevo..
Allora...voglio dimostrare che, detto p un primo tale che $ p^x||n $, $ p^x|\sum_{i=0}^{n-1}{a^ib^{n-1-i} $ sapendo che $ p^x|a^n-b^n $.

Per farlo faccio così:
l'idea di fondo è riscrivere $ \sum_{i=0}^{n-1}a^ib^{n-1-i} $, come il prodotto di tante sommatorie..

$ $a^n-b^n=a^{p^xz}-b^{p^xz}=(a^{z*p^{x-1}}-b^{z*p^{x-1}})(\sum_{i=0}^{p-1}{(a^{x*p^{x-1}})^i (b^{z*p^{x-1}})^{p-1-i}) $. A questo punto ho che p divide la sommatoria.
Ora considero solo il polinomio $ a^{z*p^{x-1}}-b^{z*p^{x-1}} $. Devo dimostrare che è divisibile per p^{x-1}*(a-b). per farlo faccio così:

$ $a^{p^{x-1}z}-b^{p^{x-1}z}=(a^{z*p^{x-2}}-b^{z*p^{x-2}})(\sum_{i=0}^{p-1}{(a^{x*p^{x-2}})^i (b^{z*p^{x-2}})^{p-1-i}) $, ora la nuova sommatoria è divisibile per p. Itero il processo(che effettivamente suona meglio di quello che ho scritto io ) fino a che ottengo una roba del tipo

$ $a^n-b^n=(a^z-b^z)\prod_{j=1}^x{(\sum_{i=0}^{p-1}{(a^{z*p^{j-1}})^i (b^{z*p^{j-1}})^{p-1-i}) $(spero di non aver sbagliato gli indici XD). Ora ogniuna di quelle sommatorie è divisibile per p quindi la produttoria enorme è divisibile per p^x.
D'altro canto visto che la produttoria enorme divide$ \sum_{i=0}^{n-1}a^ib^{n-1-i} $, ho che p^x divide questa sommatoria. Posso rifare questo procedimento per tutti i primi $ p_{a_i}^{a_i} $ che dividono n, ottenendo che ogni $ p_{a_i}^{a_i} $ divide $ \sum_{i=0}^{n-1}a^ib^{n-1-i} $, e quindi n divide la sommatoria..

[dario2994]

Woooooooo compliments, è identica alla mia.
Comunque posso darti un consiglio... INDUZIONE. Rende molto più facile da capire la soluzione.
Scrivo qui un lemma praticamente equivalente a quello dimostrato da te (direi uguale xD) e lo mostro per induzione (tralascio l'appartenenza delle variabili e smancerie varie):

Lemma: $ $p^x|a-b\Rightarrow p^{x+y}|a^{p^y}-b^{p^y} $

Induco su y.
Passo base: y=0 è l'ipotesi

Passo induttivo:
Fatto1: $ $ p|\sum_{i=0}^{p-1}\left(a^{p^y}\right)^i\left(b^{p^y}\right)^{p-1-i} $
Questo è ovvio ricordandosi che per ipotesi $ $ p|a-b $ e quindi analizzando mod p.

Fatto2: $ $ $p^{x+y}|a^{p^y}-b^{p^y} $
Questo è vero per ipotesi induttiva.

Unendo Fatto1 e Fatto2 ottengo:
$ $ p\cdot p^{x+y}|\left(\sum_{i=0}^{p-1}\left(a^{p^y}\right)^i\left(b^{p^y}\right)^{p-1-i}\right)\left(a^{p^y}-b^{p^y}\right) $
Svolgendo i conti da entrambe i lati ottengo:
$ $ p^{x+y+1}|a^{p^{y+1}}-b^{p^{y+1}} $
Che è il passo induttivo.

p.s. questo lemma serviva anche in uno degli esercizi di ammissione al wc
p.p.s. questa è la tipica dimostrazione caduta dal cielo, ovviamente per arrivarci si sfruttano i ragionamenti fatti da Reginald (o simili...)

[Dani92]

Unendo Fatto1 e Fatto2 ottengo:
$ $ p\cdot p^{x+y}|\left(\sum_{i=0}^{p-1}a^ib^{p-1-i}\right)\left(a^{p^y}-b^{p^y}\right) $
Svolgendo i conti da entrambe i lati ottengo:
$ $ p^{x+y+1}|a^{p^{y+1}}-b^{p^{y+1}} $
Che è il passo induttivo.

@Dario: mi puoi mostrare gentilmente i passaggi per arrivare da $ $\left(\sum_{i=0}^{p-1}a^ib^{p-1-i}\right)\left(a^{p^y}-b^{p^y}\right) $ a $ a^{p^{y+1}}-b^{p^{y+1}} $??

Ho provato molte strade ma non ci arrivo mai....-.-' Scusa il disturbo!

[dario2994]

Uhm deriva da questa fattorizzazione notevole (e nota):
$ $x^n-y^n=(x-y)\left(\sum_{i=0}^{n-1}x^iy^{n-1-i}\right) $ ***
Come si dimostra una cosa del genere??? Svolgendo i calcoli... svolgo la moltiplicazione ottenendo:
$ $\sum_{i=0}^{n-1}x^{i+1}y^{n-1-i}-\sum_{i=0}^{n-1}x^iy^{n-i} $
Ora noto che nella prima sommatoria sono presenti una sola volta tutti i monomi del tipo $ $x^ay^b $ con a,b interi positivi e a+b=n tranne $ $y^n $. Stessa cosa nella seconda sommatoria ma ad esclusione di $ $x^n $ tutti i monomi in comune li sottraggo... resta quindi $ $x^n-y^n $ che è proprio quello che volevo
Per svolgere il passaggio che non hai capito basta sfruttare *** ponendo
$ $n=p $
$ $x=a^{p^y} $
$ $y=b^{p^y} $