Siano $ ~ a,b,n $ i soliti interi positivi.
Dimostrare che $ \displaystyle n \mid \phi(a^n-b^n) $.
Questo è carino! - divisibilità e phi
Con $ a>b $, intendevi 
.
Si puo' vedere che esiste un primo $ p|(a^n-b^n) $, ma che p non divide $ a^d-b^d $, per nessun divisore di $ n $, dunque $ n $ e' l'ordine di $ (a/b) $ modulo $ p $, che divide $ p-1 $, per il teorema di Euler, che a sua volta divide $ \phi(a^n-b^n) $.
.Si puo' vedere che esiste un primo $ p|(a^n-b^n) $, ma che p non divide $ a^d-b^d $, per nessun divisore di $ n $, dunque $ n $ e' l'ordine di $ (a/b) $ modulo $ p $, che divide $ p-1 $, per il teorema di Euler, che a sua volta divide $ \phi(a^n-b^n) $.
Why would anybody want empathy?
A Reese: no, "si può vedere che" non vuol dire un bel niente, anche perchè ogni fattore primo di
$ ~ 2^6-1 $ divide $ ~ 2^2-1 $ o $ 2^3-1 $.
Comunque benvenuto nel forum!
A Boll:
- volevi scrivere $ ~ \mbox{ord}_{a^n-b^n} \; ab^{-1} $
- che cavolo vuol dire che quella funzione è crescente?
ma soprattutto... ti stai pericolosamente hitleulerizzando
$ ~ 2^6-1 $ divide $ ~ 2^2-1 $ o $ 2^3-1 $.
Comunque benvenuto nel forum!
A Boll:
- volevi scrivere $ ~ \mbox{ord}_{a^n-b^n} \; ab^{-1} $
- che cavolo vuol dire che quella funzione è crescente?
ma soprattutto... ti stai pericolosamente hitleulerizzando
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Credo che Boll intendesse questo: so che $ (ab^{-1})^n \equiv 1 \pmod{a^n-b^n} $. Cogetturo che n sia l'ordinemoltiplicativo. se non lo fosse avremmo $ a^k-b^k $ multiplo di $ a^n-b^n $ per qualche k<n ma per la crescenza di quella funzione abbiamo $ a^k-b^k<a^n-b^n $ da cui l'assurdo. Poi $ ord_t ( k) | \phi(t) $ da cui con $ t=a^n-b^n $ e $ k=ab^{-1} $ si ricava il risultato
Vogliamo rafforzare un po' questa tesi deboluccia???
Dimostrare che se $ (a^n-b^n,n)=1 $ allora
$ n^{\sigma (n)} | (\phi (a^n-b^n) )^2 $
dove $ \sigma (n) $ sono il numero di divisori di n.
Vogliamo rafforzare un po' questa tesi deboluccia???
Dimostrare che se $ (a^n-b^n,n)=1 $ allora
$ n^{\sigma (n)} | (\phi (a^n-b^n) )^2 $
dove $ \sigma (n) $ sono il numero di divisori di n.
Beh, la rafforzatura meno interessante è invece importante per dimostrare la rafforzatura wolfiana!
By the way, per la tua dimostrazione, Reese, potevi citare il teorema di Zsigmondy, e io ti ho citato una delle uniche eccezioni.
Edit: come previsto, la mia dimostrazione non funziona!
Beh, lascio lo stesso quello che ho già scritto.
Ipotesi
$ ~ (a,b)=1 $
$ ~(a^n-b^n,n) = 1 $
Lemma 1
Sia $ ~ d $ un divisore di $ ~ n $. Allora
$ ~ \left( a^d-b^d, \frac{a^n-b^n}{a^d-b^d} \right) = 1 $.
Dimostrazione:
Poniamo $ ~x = a^d,y=b^d, k = \frac nd $. Bisogna dimostrare:
$ ~ \left( x-y, x^{k-1} + x^{k-2}y + \ldots + y^{k-1} \right) = 1 $
Per il teorema del resto, il resto della divisione del secondo coso per il primo è:
$ ~ y^{k-1} + y^{k-2}y + \ldots + y^{k-1} = ky^{k-1} = \frac nd a^{n-d} $
Se un primo divide x-y e anche $ ~ \frac{x^k-y^k}{x-y} $, divide anche $ ~ \frac nd a^{n-d} $, ma se $ ~ p \mid a $ viene fuori che $ ~ p \mid b $, impossibile, e se $ ~ p \mid \frac nd $ allora $ ~ p \mid n $, ma è anche $ ~p \mid a^n-b^n $, impossibile.
Lemma 2 (di Reese)
Per ogni d|n:
$ ~ d \mid \phi \left( \frac{a^d-b^d}{a-b} \right) $
La dimostrazione è uguale a quella di Boll. Abbiamo:
$ ~ a^d \equiv b^d \pmod{\frac{a^d-b^d}{a-b}} $
$ ~ (ab^{-1})^d \equiv 1 \pmod{\frac{a^d-b^d}{a-b}} $
Se l'ordine di a/b è k, $ ~ (ab^{-1})^k \equiv 1 $, quindi di nuovo
$ ~ \frac{a^d-b^d}{a-b} \mid a^k-b^k $.
Poichè abbiamo dimostrato che $ ~ (a-b, a^k-b^k) = 1 $ dovrà essere:
$ ~ a^d-b^d \mid a^k-b^k $, impossibile se k < d, perchè il primo membro sarebbe maggiore del primo.
Lemma 3
$ ~ \left( \prod_{d \mid n} d \right) ^2 = n^{\sigma(n)} $
Dimostrazione. Basta contare con che potenza troviamo un primo p che divide n nella produttoria. Se $ ~ n = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k} $ è la fattorizzazione di n, i divisori di n in cui $ ~ p_1 $ compare con esponente i ($ ~ 1 \le i \le e_1 $) sono $ ~ (e_2+1)(e_3+1) \cdots (e_k+1) $ (ovvero i modi di scegliere con che esponenti appaiono gli altri primi. Quindi, l'esponente che divide p_1 nella produttoria^2 è $ ~ 2(e_2+1)\cdots (e_k+1)(1+2+3+\ldots + e_1) = $$ ~ (e_2+1)\cdots (e_k+1)(e_1)(e_1+1) = e_1 \sigma(n) $ e tutto torna.
Ora. d è un divisore di n. Per ogni k che divide d, ed è diverso da d, poniamo $ ~ a_k = a^k-b^k $. Sia m(d) il minimo comune multiplo tra tutti gli a_k al variare di k tra i divisori di d (diversi da d).
Finalmente, sia $ ~ f(d) = \frac{a^d-b^d}{m(d)} $. (f(d) è abbastanza chiaramente un intero). Grazie al lemma 1, vediamo che questo è un modo bizzarro per dire: da $ ~ a^d-b^d $ tolgo tutti i fattori primi che sono contenuti in un$ ~ a^k-b^k $, con $ ~ k \mid d \land k < d $ (ovvero: considero solo i primi primitivi con le loro pontenze).
Sappiamo (per il lemma 2 leggermente modificato) che, per ogni $ ~ k \mid d, k \neq d $ abbiamo:
$ ~ d \mid \phi \left( \frac{a^d-b^d}{a^k-b^k} \right) $
Qua si ferma la dimostrazione, cioè, da qui non riesco a dimostrare che $ ~ d \mid \phi(f(d)) $. Se così fosse, visto che il prodotto di tutti gli $ ~ f(d) $, per d che varia tra i divisori di n, è proprio $ ~ a^n-b^n $ (e questi sono anche relativamente primi), moltiplicando tutto e usando il lemma 3 dimostrerei la tesi
By the way, per la tua dimostrazione, Reese, potevi citare il teorema di Zsigmondy, e io ti ho citato una delle uniche eccezioni.
Edit: come previsto, la mia dimostrazione non funziona!
Beh, lascio lo stesso quello che ho già scritto.
Ipotesi
$ ~ (a,b)=1 $
$ ~(a^n-b^n,n) = 1 $
Lemma 1
Sia $ ~ d $ un divisore di $ ~ n $. Allora
$ ~ \left( a^d-b^d, \frac{a^n-b^n}{a^d-b^d} \right) = 1 $.
Dimostrazione:
Poniamo $ ~x = a^d,y=b^d, k = \frac nd $. Bisogna dimostrare:
$ ~ \left( x-y, x^{k-1} + x^{k-2}y + \ldots + y^{k-1} \right) = 1 $
Per il teorema del resto, il resto della divisione del secondo coso per il primo è:
$ ~ y^{k-1} + y^{k-2}y + \ldots + y^{k-1} = ky^{k-1} = \frac nd a^{n-d} $
Se un primo divide x-y e anche $ ~ \frac{x^k-y^k}{x-y} $, divide anche $ ~ \frac nd a^{n-d} $, ma se $ ~ p \mid a $ viene fuori che $ ~ p \mid b $, impossibile, e se $ ~ p \mid \frac nd $ allora $ ~ p \mid n $, ma è anche $ ~p \mid a^n-b^n $, impossibile.
Lemma 2 (di Reese)
Per ogni d|n:
$ ~ d \mid \phi \left( \frac{a^d-b^d}{a-b} \right) $
La dimostrazione è uguale a quella di Boll. Abbiamo:
$ ~ a^d \equiv b^d \pmod{\frac{a^d-b^d}{a-b}} $
$ ~ (ab^{-1})^d \equiv 1 \pmod{\frac{a^d-b^d}{a-b}} $
Se l'ordine di a/b è k, $ ~ (ab^{-1})^k \equiv 1 $, quindi di nuovo
$ ~ \frac{a^d-b^d}{a-b} \mid a^k-b^k $.
Poichè abbiamo dimostrato che $ ~ (a-b, a^k-b^k) = 1 $ dovrà essere:
$ ~ a^d-b^d \mid a^k-b^k $, impossibile se k < d, perchè il primo membro sarebbe maggiore del primo.
Lemma 3
$ ~ \left( \prod_{d \mid n} d \right) ^2 = n^{\sigma(n)} $
Dimostrazione. Basta contare con che potenza troviamo un primo p che divide n nella produttoria. Se $ ~ n = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k} $ è la fattorizzazione di n, i divisori di n in cui $ ~ p_1 $ compare con esponente i ($ ~ 1 \le i \le e_1 $) sono $ ~ (e_2+1)(e_3+1) \cdots (e_k+1) $ (ovvero i modi di scegliere con che esponenti appaiono gli altri primi. Quindi, l'esponente che divide p_1 nella produttoria^2 è $ ~ 2(e_2+1)\cdots (e_k+1)(1+2+3+\ldots + e_1) = $$ ~ (e_2+1)\cdots (e_k+1)(e_1)(e_1+1) = e_1 \sigma(n) $ e tutto torna.
Ora. d è un divisore di n. Per ogni k che divide d, ed è diverso da d, poniamo $ ~ a_k = a^k-b^k $. Sia m(d) il minimo comune multiplo tra tutti gli a_k al variare di k tra i divisori di d (diversi da d).
Finalmente, sia $ ~ f(d) = \frac{a^d-b^d}{m(d)} $. (f(d) è abbastanza chiaramente un intero). Grazie al lemma 1, vediamo che questo è un modo bizzarro per dire: da $ ~ a^d-b^d $ tolgo tutti i fattori primi che sono contenuti in un$ ~ a^k-b^k $, con $ ~ k \mid d \land k < d $ (ovvero: considero solo i primi primitivi con le loro pontenze).
Sappiamo (per il lemma 2 leggermente modificato) che, per ogni $ ~ k \mid d, k \neq d $ abbiamo:
$ ~ d \mid \phi \left( \frac{a^d-b^d}{a^k-b^k} \right) $
Qua si ferma la dimostrazione, cioè, da qui non riesco a dimostrare che $ ~ d \mid \phi(f(d)) $. Se così fosse, visto che il prodotto di tutti gli $ ~ f(d) $, per d che varia tra i divisori di n, è proprio $ ~ a^n-b^n $ (e questi sono anche relativamente primi), moltiplicando tutto e usando il lemma 3 dimostrerei la tesi
Ultima modifica di edriv il 17 gen 2007, 21:57, modificato 3 volte in totale.
Sì, dovevo escludere qualche caso, mi sono accorto dopo. Aspetto che finisci la dimostrazione per leggerla.edriv ha scritto:By the way, per la tua dimostrazione, Reese, potevi citare il teorema di Zsigmondy, e io ti ho citato una delle uniche eccezioni.
Why would anybody want empathy?
Allora, nella quasi-dimostrazione che ho scritto prima, mi sono _veramente_ incasinato, in realtà si può concludere da lì. Invece che, da $ ~ d \mid \phi(a^k-b^k) $ e da questo cercare di dedurre che $ ~ d \mid \phi(f(d)) $, bastava subito partire dall'ordine moltiplicativo per dedurre questo!
Comunque, ho intenzione di riscriverla in modo più "degno" per un problema così carino, usando i polinomi ciclotomici.
Ci limiteremo per ora al caso b=1.
Indichiamo con $ ~ \Phi_n(x) $ l'n-esimo polinomio ciclotomico. L'n-esimo polinomio ciclotomico è il polinomio avente come radici tutte e sole le n-esime radici complesse dell'unità di ordine n (cioè che non sono radici k-esime per k < n). È un fatto noto (e figo) che i polinomi ciclotomici sono a coefficienti interi.
Provo a dimostrare questo lemma, che non so se è giusto (sembra troppo forte per essere vero).
Lemma 1
Per interi positivi distinti n,k e per ogni intero x abbiamo:
$ ~ \mbox{gcd}(\Phi_n(x), \Phi_k(x)) = 1 $
Proof.
Sia d il loro massimo comun divisore.
Poichè $ ~ \Phi_n(x) \mid x^n-1 $, avremo $ ~ x^n \equiv 1 \pmod d $ e $ ~ x^k \equiv 1 \pmod d $, per l'identità di Bezout troviamo due interi tali che $ ~ an + bk = (n,k) $, da cui elevando la prima conguenza ad a, la seconda a b, e moltiplicandole (notare che gli esponenti negativi sono ben definiti) otteniamo $ ~ x^{(n,k)} \equiv 1 \pmod d $ o $ ~ d \mid x^{(n,k)} - 1 $.
Poichè $ ~ \Phi_n(x) \mid \frac{x^n-1}{x^{(n,k)} - 1} $, sappiamo che $ ~ d \mid x^{(n,k)} - 1 \land d \mid \frac{x^n-1}{x^{(n,k)} - 1} $, quindi, usando il teorema del resto allo stesso modo in cui ho dimostrato il lemma 1 del post precedente, vediamo che $ ~ d \mid \frac{n}{(n,k)} $. Allo stesso modo si dimostra che $ ~ d \mid \frac{k}{(n,k)} $... ma d dividerebbe due interi che sono primi tra loro.
Lemma 2 (anche questo troppo forte per essere vero, sarà da aggiungere qualche ipotesi)
$ ~ n \mid \phi(\Phi_n(x)) $ (belle le due phi eh!).
Proof. Siccome $ ~ \Phi_n(x) \mid x^n-1 $ avremo $ ~ x^n \equiv 1 \pmod{\Phi_n(x)} $, ovvero $ ~ \mbox{ord} x \mid n $. Se l'ordine è minore, allora per k < n avremo: $ ~ x^k \equiv 1 \pmod{\Phi_n(x)} $, da cui di nuovo $ ~ \Phi_n(x) \mid x^k - 1 $, se un primo divide $ ~ \Phi_n(x) $ allora dovrà dividere anche un $ ~ \Phi_e(x) $ con e | k, contraddicendo il lemma 1.
Quindi l'ordine moltiplicativo di x modulo $ ~ \Phi_n(x) $ è n, da cui la tesi.
Lemma 3
Per ogni n e per ogni x intero abbiamo il teorema di simone:
$ ~ n^{\sigma(n)} \mid \phi(x^n-1)^2 $.
Proof. Usando il lemma 2, sappiamo che per ogni divisore d di n:
$ ~ d \mid \phi(\Phi_d(x)) $
Da cui, moltiplicando su tutti i divisori di n:
$ ~ \prod_{d\mid n}d \mid \prod_{d \mid n} \phi(\Phi_d(x)) $
Poichè abbiamo dimostrato che i valori dei polinomi ciclotomici sono relativamente primi, e per la moltiplicatività della phi:
$ ~ \prod_{d \mid n} \phi(\Phi_d(x)) = \phi \left(\prod_{d \mid n} \Phi_d(x) \right) $
$ ~ = \phi(x^n-1) $
Nel post precedente ho dimostrato l'identità:
$ ~ \left(\prod_{d\mid n}d \right) ^2 = n^{\sigma(n)} $
Unendo queste cose, abbiamo la tesi.
Vi prego di leggere e correggere la mia dimostrazione!
E anche, chi ha voglia, di estendere anche ai vari valori di b (qui l'ipotesi aggiuntiva di simone diventa indispensabile), (polinomi ciclotomici omogenei?).
Comunque, ho intenzione di riscriverla in modo più "degno" per un problema così carino, usando i polinomi ciclotomici.
Ci limiteremo per ora al caso b=1.
Indichiamo con $ ~ \Phi_n(x) $ l'n-esimo polinomio ciclotomico. L'n-esimo polinomio ciclotomico è il polinomio avente come radici tutte e sole le n-esime radici complesse dell'unità di ordine n (cioè che non sono radici k-esime per k < n). È un fatto noto (e figo) che i polinomi ciclotomici sono a coefficienti interi.
Provo a dimostrare questo lemma, che non so se è giusto (sembra troppo forte per essere vero).
Lemma 1
Per interi positivi distinti n,k e per ogni intero x abbiamo:
$ ~ \mbox{gcd}(\Phi_n(x), \Phi_k(x)) = 1 $
Proof.
Sia d il loro massimo comun divisore.
Poichè $ ~ \Phi_n(x) \mid x^n-1 $, avremo $ ~ x^n \equiv 1 \pmod d $ e $ ~ x^k \equiv 1 \pmod d $, per l'identità di Bezout troviamo due interi tali che $ ~ an + bk = (n,k) $, da cui elevando la prima conguenza ad a, la seconda a b, e moltiplicandole (notare che gli esponenti negativi sono ben definiti) otteniamo $ ~ x^{(n,k)} \equiv 1 \pmod d $ o $ ~ d \mid x^{(n,k)} - 1 $.
Poichè $ ~ \Phi_n(x) \mid \frac{x^n-1}{x^{(n,k)} - 1} $, sappiamo che $ ~ d \mid x^{(n,k)} - 1 \land d \mid \frac{x^n-1}{x^{(n,k)} - 1} $, quindi, usando il teorema del resto allo stesso modo in cui ho dimostrato il lemma 1 del post precedente, vediamo che $ ~ d \mid \frac{n}{(n,k)} $. Allo stesso modo si dimostra che $ ~ d \mid \frac{k}{(n,k)} $... ma d dividerebbe due interi che sono primi tra loro.
Lemma 2 (anche questo troppo forte per essere vero, sarà da aggiungere qualche ipotesi)
$ ~ n \mid \phi(\Phi_n(x)) $ (belle le due phi eh!).
Proof. Siccome $ ~ \Phi_n(x) \mid x^n-1 $ avremo $ ~ x^n \equiv 1 \pmod{\Phi_n(x)} $, ovvero $ ~ \mbox{ord} x \mid n $. Se l'ordine è minore, allora per k < n avremo: $ ~ x^k \equiv 1 \pmod{\Phi_n(x)} $, da cui di nuovo $ ~ \Phi_n(x) \mid x^k - 1 $, se un primo divide $ ~ \Phi_n(x) $ allora dovrà dividere anche un $ ~ \Phi_e(x) $ con e | k, contraddicendo il lemma 1.
Quindi l'ordine moltiplicativo di x modulo $ ~ \Phi_n(x) $ è n, da cui la tesi.
Lemma 3
Per ogni n e per ogni x intero abbiamo il teorema di simone:
$ ~ n^{\sigma(n)} \mid \phi(x^n-1)^2 $.
Proof. Usando il lemma 2, sappiamo che per ogni divisore d di n:
$ ~ d \mid \phi(\Phi_d(x)) $
Da cui, moltiplicando su tutti i divisori di n:
$ ~ \prod_{d\mid n}d \mid \prod_{d \mid n} \phi(\Phi_d(x)) $
Poichè abbiamo dimostrato che i valori dei polinomi ciclotomici sono relativamente primi, e per la moltiplicatività della phi:
$ ~ \prod_{d \mid n} \phi(\Phi_d(x)) = \phi \left(\prod_{d \mid n} \Phi_d(x) \right) $
$ ~ = \phi(x^n-1) $
Nel post precedente ho dimostrato l'identità:
$ ~ \left(\prod_{d\mid n}d \right) ^2 = n^{\sigma(n)} $
Unendo queste cose, abbiamo la tesi.
Vi prego di leggere e correggere la mia dimostrazione!
E anche, chi ha voglia, di estendere anche ai vari valori di b (qui l'ipotesi aggiuntiva di simone diventa indispensabile), (polinomi ciclotomici omogenei?).
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Ok, ho trovato l'errore!
Il lemma 1 dovrebbe essere riscritto come:
Se $ ~ (\Phi_n(x), \Phi_k(x)) \neq 1 $ allora $ ~ n \mid k $ o $ ~ k \mid n $. In tal caso il gcd divide $ ~ \frac nk $.
Infatti così nella mia dimostrazione viene fuori che $ ~ \Phi_k(x) \mid \frac{x^k-1}{x^k-1} $ che è assai poco probabile. Negli altri casi invece dovrebbe filare liscio.
Conseguenze del lemma? Eh, neanche il lemma 2 funziona più. Però aggiungendo la condizione $ ~ (n,x^n-1)=1 $ funziona di nuovo tutto (perchè troverei un primo che divide $ ~ \Phi_n(x) $ e $ ~ x^k - 1 $, ma quindi dividerebbe anche $ ~ \frac nk $.
Per il resto, i ciclotomici restano incredibilmente fighi!
Il lemma 1 dovrebbe essere riscritto come:
Se $ ~ (\Phi_n(x), \Phi_k(x)) \neq 1 $ allora $ ~ n \mid k $ o $ ~ k \mid n $. In tal caso il gcd divide $ ~ \frac nk $.
Infatti così nella mia dimostrazione viene fuori che $ ~ \Phi_k(x) \mid \frac{x^k-1}{x^k-1} $ che è assai poco probabile. Negli altri casi invece dovrebbe filare liscio.
Conseguenze del lemma? Eh, neanche il lemma 2 funziona più. Però aggiungendo la condizione $ ~ (n,x^n-1)=1 $ funziona di nuovo tutto (perchè troverei un primo che divide $ ~ \Phi_n(x) $ e $ ~ x^k - 1 $, ma quindi dividerebbe anche $ ~ \frac nk $.
Per il resto, i ciclotomici restano incredibilmente fighi!