Allora, sia a un intero congruo a 1 modulo p, dove p è un primo dispari.
Si dimostri che $ v_p(a^k-1)=v_p(a-1)+v_p(k) $
Dove $ v_p(roba) $ è l'esponente con cui p compare nella fattorizzazione di "roba in fattori primi.
Bonus: come si aggiusta il caso p=2?
Lemma stranoto
Lemma stranoto
"Sei la Barbara della situazione!" (Tap)
Provo:
$ v_p(a^k-1)=v_p((a-1)*(a^{k-1}+a^{k-2}+...+1)) ${a^{k-1}+a^{k-2}+...+1}\equiv k$ (p) $
se k non è divisibile per p la formula è banalmente vera.
se k è multiplo di $ p^n $ allora
$ a^{k-1}+a^{k-2}+...+1=xp^n=xp^{v_p(k)} a-1=yp^{v_p(a-1)} (a-1)*(a^{k-1}+a^{k-2}+...+1)=yp^{v_p(a-1)}*xp^{v_p(k)}=xyp^{v_p(a-1)+v_p(k)} $
con x e y che non sono multipli di k, quindi:
$ v_p(xyp^{v_p(a-1)+v_p(k)})=v_p(a)+v_p(k) $
quindi la tesi è dimostrata
probabilmente si può dimostrare meglio, quindi se qualcuno mi corregge o mi dà delle dritte mi fa felice, infatti sono un principiante e ho bisogno di imparare la scrittura rigorosa.
$ v_p(a^k-1)=v_p((a-1)*(a^{k-1}+a^{k-2}+...+1)) ${a^{k-1}+a^{k-2}+...+1}\equiv k$ (p) $
se k non è divisibile per p la formula è banalmente vera.
se k è multiplo di $ p^n $ allora
$ a^{k-1}+a^{k-2}+...+1=xp^n=xp^{v_p(k)} a-1=yp^{v_p(a-1)} (a-1)*(a^{k-1}+a^{k-2}+...+1)=yp^{v_p(a-1)}*xp^{v_p(k)}=xyp^{v_p(a-1)+v_p(k)} $
con x e y che non sono multipli di k, quindi:
$ v_p(xyp^{v_p(a-1)+v_p(k)})=v_p(a)+v_p(k) $
quindi la tesi è dimostrata
probabilmente si può dimostrare meglio, quindi se qualcuno mi corregge o mi dà delle dritte mi fa felice, infatti sono un principiante e ho bisogno di imparare la scrittura rigorosa.
se devo essere sincero quel passsaggio lascia perplesso pure me... considerando i fattori in mod (p) si ha una somma di k unità, e allora è ovvio; però mi rendo conto che questa non è una dimostrazione.julio14 ha scritto:Questo passaggio non mi è troppo chiaro... da dove salta fuori?
Probabilmente si riesce a dimostrarlo per p diverso da 2, ma non ci riesco. Suggerimenti?
(forse bisogna dimostrare che LHS-k è divisibile per $ p^n, n>=v_p(k) $)
lolgst_113 ha scritto:se devo essere sincero quel passsaggio lascia perplesso pure me...
Più che altro non è una cosa "intuitivamente giusta, ma non formalizzata", è proprio sbagliata. $ $1+1+...+1=12\equiv 9\pmod3 $ eppure $ $v_3(9)\neq v_3(12) $gst_113 ha scritto:considerando i fattori in mod (p) si ha una somma di k unità, e allora è ovvio; però mi rendo conto che questa non è una dimostrazione.
Induzione estesa?Giustino ha scritto:come si dimostra il lemma?
Va bene $ \displaystyle~\begin{cases}\upsilon_2(a^k-1)=\upsilon_2(a-1)+\upsilon_2(k)+\upsilon_2(\frac{a+1}{2})&\text{se k pari}\\\upsilon_2(a^k-1)=\upsilon_2(a-1)&\text{se k dispari}\end{cases} $Pietro ha scritto:come si aggiusta il caso p=2?
EDIT: Usiamo questo lemma per abbattere questo problema
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)