Altri lemmi (altrettanto ovvi) sui ciclotomici...

[piever]

Allora, una carrellata di fatti interessanti e forse utili sui e con i polinomi ciclotomici...

1) Sia p un primo:

$ \displaystyle p|\Phi_n(a)\Leftrightarrow \exists\; k\in\mathbb{N}:\frac{n}{ord_p(a)}=p^k $

2) Sia p un primo dispari:

$ \displaystyle\exists\; k\in\mathbb{N}^+:\frac{n}{ord_p(a)}=p^k\Rightarrow p||\Phi_n(a) $

3) Se $ n>2 $ allora, detto P l'insieme dei numeri primi, per ogni $ a\ge 2 $ si ha:

se $ \displaystyle\nexists\; p\in\mathbb{P}:ord_p(a)=n $ allora $ \displaystyle\Phi_n(a) $ e' il piu' grande divisore primo di n

4) Se $ n>2 $ allora, per ogni $ a>2 $:

$ \displaystyle\exists\; p\in\mathbb{P}:ord_p(a)=n $

5) Sia p un primo dispari, tale che $ d|p-1 $:

$ \displaystyle\Phi_d(n) $ ha al piu' $ \phi(d) $ radici modulo p

6) $ \displaystyle\prod_{d|p-1} \Phi_d(x)=x^{p-1}-1 $

7) Sia p un primo dispari, tale che $ d|p-1 $:

$ \displaystyle\Phi_d(n) $ ha esattamente $ \phi(d) $ radici modulo p


EDIT1: grazie della precisazione Evariste
EDIT2: o-ops, scusami edriv, mi ero sbagliato ora comunque ho corretto..

[EvaristeG]

"... dove
$ \Phi_n(x)=\displaystyle{\prod_{(k,n)=1}(x-\zeta_k)} $
con $ \zeta_k=e^{2i\pi k/n} $, è l'n-esimo polinomio ciclotomico."
Forse andava aggiunto, eh?

[edriv]

Partiamo dal 3), che sembra il più difficile.
Intanto provo con qualche caso piccolo, per capire come funziona.
Proviamo ad esempio a mettere a=2, n=6

[darkcrystal]

Visto che nessuno li considera, cominciamo a dare qualche idea, anche se incompleta...
Prima cosa che mi serve: $ \displaystyle \prod_{d|n}\Phi_d(x)=x^n-1 $, ossia la versione "potenziata" del 6.

Peraltro questo è abbastanza semplice: mi servono tutte le radici n-esime dell'unità: o queste stanno nell'n-esimo ciclotomico, oppure non erano primitive, e il loro ordine è un divisore di n, quindi stanno in uno degli altri ciclotomici.

Adesso, veniamo al punto 1.

Domanda: chi è il più piccolo j tale che $ \displaystyle p|\Phi_j(a) $? Beh, si ha che $ \displaystyle p|\Phi_j(a) \Rightarrow p|(a^j-1) \Rightarrow ord_p(a)|j $, dunque al minimo j è l'ordine moltiplicativo. Ma allora abbiamo anche: $ \displaystyle p|a^{ord_p(a)}-1 $ per definizione, e $ \displaystyle a^{ord_p(a)}-1=\prod_{d|ord_p(a)}\Phi_d(a) $, ma i polinomi sono tutti di ordine (o come si chiama) più piccolo dell'ordine moltiplicativo tranne uno, e dunque p deve dividere proprio quello: insomma, $ \displaystyle p|\Phi_{ord_p(a)}(a) $

E ora, però, mi sono accorto che devo andare a mangiare quindi finisco e formalizzo un po' più decentemente dopo.

Ciao!

[darkcrystal]

Ora abbiamo stabilito che il più piccolo j tale che $ \displaystyle p | \Phi_j(a) $ è $ j=ord_p(a) $. D'ora in poi perciò chiamerò j l'ordine moltiplicativo.

LEMMA. $ j | ord_{p^k}(a) | jp^k $. La prima delle due relazioni è ovvia (detto h l'ordine moltiplicativo modulo p alla k, h è tale che $ a^h \equiv 1 \pmod {p^k} \rightarrow a^h \equiv 1 \pmod p \rightarrow j|h $)

Per la seconda, notiamo che $ a^j \equiv 1 \pmod p \rightarrow a^j=(bp+1) \rightarrow $$ a^{jp^k}=(bp+1)^{p^k}=(...roba \cdot p^k + bp \cdot p^k + 1) \equiv 1 \pmod p^k $, e dunque l'ordine modulo p alla k divide $ j p^k $, come volevasi dimostrare.

Supponiamo ora che ci sia un $ j < n \leq j \cdot p $ tale che $ \displaystyle p | \Phi_n(a) $. Allora per quanto detto prima $ j|n \rightarrow n=j \cdot m $ per un qualche m, ed inoltre si può scrivere
$ \displaystyle p | \frac{a^n-1}{\displaystyle \prod_{d|n, 0<d<n}\Phi_d(a)} $. Noi sappiamo che al denominatore abbiamo il polinomio ciclotomico di ordine j, e dunque la valutazione p-adica del denominatore è esattamente 1; ne segue che deve essere $ p^2 | a^n-1 $, ossia l'ordine modulo $ p^2 $ di a divide n... ma dato che tale ordine è o j o $ j \cdot p $ (vedi lemma), abbiamo che o n è esattamente j o è esattamente $ j \cdot p $, il primo dei quali è escluso; ne viene che l'unico polinomio "buono" con ordine in quell'intervallo è $ \displaystyle \Phi_{jp}(a) $ (vedere che funziona è abbastanza semplice: la valutazione p-adica del numeratore è 2, quella del denominatore 1).

Andando avanti in modo simile, per induzione, si vede che i polinomi che ci servono sono esattamente quelli richiesti, ossia con $ n=p^k \cdot j $.


Il punto due si fa - sembrerebbe - in modo simile, in quanto se $ n=p^k \cdot j $ si ha: $ p || \frac{a^n-1}{\prod \Phi_d(a)} $ e al denominatore trovo termini la cui valutazione p-adica è maggiore o uguale a 1 se $ d=jp^k $ per qualche k, e 0 altrimenti. EDIT: avevo scritto una cavolata.
Però non ci vuole molto ad aggiustare la dimostrazione, quindi lascio che tentino gli altri: la strada delle valutazione p-adiche è comunque percorribile e - a meno che non mi sia sbagliato di nuovo - porta alla soluzione.

Chiedo scusa se scarseggia il LaTeX ma con la 56kb caricare anche solo le formule è un tormento

Bene, ora qualcuno può divertirsi a dirmi di tutto (ma quello anche prima di questo post) oppure a riempire i buchi...

Ciao a tutti!

[piever]

Ok, e ora sotto con gli altri lemmini...

Il 3 e il 4 sono risultati più interessanti.. Mi dice edriv che il 4 è una versione leggermente più debole di una cosa che va sotto l'altisonante nome di teorema di Szigmondy o come si scrive...