123. $p!|a^{(p-1)!}-1$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

123. $p!|a^{(p-1)!}-1$

Messaggio da Ido Bovski » 14 ago 2012, 11:56

Sia $p$ un numero primo. Dato un $a\in\mathbb{Z}$ tale che $\gcd(a, p!)=1$, dimostrare che $p!|a^{(p-1)!}-1$.
Se a $p$ primo si sostituisce un $n\in\mathbb{N}$ libero da quadrati, l'enunciato è ancora vero?

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 123. $p!|a^{(p-1)!}-1$

Messaggio da jordan » 14 ago 2012, 19:07

Ido Bovski ha scritto:Sia $p$ un numero primo. Dato un $a\in\mathbb{Z}$ tale che $\gcd(a, p!)=1$, dimostrare che $p!|a^{(p-1)!}-1$.
Se a $p$ primo si sostituisce un $n\in\mathbb{N}$ libero da quadrati, l'enunciato è ancora vero?

Dai due interi $a,b$ possiamo affermare che $a \mid b$ se e solo se $\upsilon_q(a)\le \upsilon_q(b)$ per ogni $q \in \mathbb{P}$.
Adesso e' necessario (e sufficiente) mostrare tale disuguaglianza per tutti i primi $q\le p$: fissato un tale $q$ infatti abbiamo in particolare che $q\mid p! \implies \text{gcd}(a,q)=1$ per cui $\displaystyle \upsilon_q(a^{(p-1)!}-1)=$ $\displaystyle \upsilon_q((a^{q-1})^{(p-1)!/(q-1)}-1)=$ $ \displaystyle \upsilon_q(a^{q-1}-1)+\upsilon_q(\frac{(p-1)!}{q-1})$ $=\displaystyle \upsilon_q(a^{q-1}-1)+\upsilon_q((p-1)!)$ (per LTE e T.di Fermat). Affinche' $\upsilon_q(p!) \le \upsilon_q(a^{(p-1)!}-1)$ dobbiamo quindi mostrare in modo equivalente che $\upsilon_q(p!) \le \upsilon_q(a^{q-1}-1)+\upsilon_q((p-1)!)$ che e' vera se e solo se $\upsilon_q(p) \le \upsilon_q(a^{q-1}-1)$ per ogni primo $q \le p$ e intero $a$ coprimo con $p!$.

E' ovvio adesso che, se $\mu(p)\neq 0$ allora la divisibilità e' sempre verificata, difatti $\displaystyle \upsilon_q(p) \in \{0,1\}$ e $\upsilon_q(a^{q-1}-1) \ge 1$. []
The only goal of science is the honor of the human spirit.

Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Re: 123. $p!|a^{(p-1)!}-1$

Messaggio da Ido Bovski » 14 ago 2012, 22:16

Bene! A te il testimone :D

p.s. per chi volesse trovarla, assicuro che esiste anche una dimostrazione che non fa uso del lemma LTE

ant.py
Messaggi: 140
Iscritto il: 18 set 2011, 11:36

Re: 123. $p!|a^{(p-1)!}-1$

Messaggio da ant.py » 15 ago 2012, 17:50

Allora premetto che non sono sicuro di molte delle cose che dirò, quindi è probabile che la dimostrazione sia cannata

Allora

Sia $ \phi $ la funzione totiente di eulero, per cui sappiamo che se $ \gcd(a,n) = 1 $ alloa $ a^{\phi(n)} \equiv 1 \pmod n $

1) $ \phi(p!) = \prod{C_i}\prod{(p_i -1)} $ dove $ C_i $ sono composti mentre i vari $ p_i $ sono primi
Esempio $ \phi(10!) = 10 \cdot 9 \cdot 8 \cdot (7-1) \cdot 6 \cdot (5-1) \cdot 4 \cdot (3-1) \cdot (2-1) $
Dimostrazione:
Testo nascosto:
La dimostrazione non è mia ma appartiene a Carlos Rivera e l'ho trovata qui: http://tech.groups.yahoo.com/group/prim ... sage/17701
In ogni caso la riscrivo qui perche li è scritta davvero male
$ n! = \prod{C_i}\prod{p_j}\prod{p_k} $ dove $ p_j $ = primo tale che $ \gcd(\prod{C_i}, p_j) > 1 $, mentre $ p_k $ primo tale che $ \gcd(\prod{C_i}, p_k) =1 (p_j, p_k, C_i < n) $
$ \phi(\prod{p_k}) = \prod{p_k -1} $ ($ \phi $ è moltiplicativa)

Ma $ \prod{C_i} = \prod{p_j^{a_j}} $ ($ a_j $ sono ovviamente le volte in cui $ p_j $ occorre nel prodotto $ \prod{C_i} $)
Quindi $ \prod{C_i}\prod{p_j} = \prod{p_j^{a_j + 1}} $
Essendo poi $ \phi(p^b) = (p-1)p^{b-1} $ si ha

$ \phi(\prod{C_i}\prod{p_j}) = \phi(\prod{p_j^{a_j + 1}}) = \prod{p_j^{a_j}(p_j -1)} = \prod{p_j^{a_j}}\cdot\prod{(p_j -1)} = \prod{C_i}\prod{(p_j-1)} $

Quindi $ \phi(n!) = \prod{C_i}\prod{(p_j-1)}\prod{(p_k-1)} = \prod{C_i}\prod{(p_i-1)} $ []
Detto questo, si dimostra facilmente che $ \phi(p!) | (p-1)!^2 $ (se p primo; infatti il fattore p non é presente in nessuno dei due membri, mentre tutti i fattori in $ \phi(p!) $ sono minori di p, ripetuti al massimo due volte (quando si sottrae uno ad un primo, come nell'esempio precedente)

Quindi $ \phi(p!)\cdot\alpha = (p-1)!^2 $ con $ \alpha $ intero
Quindi noi sappiamo che
$ a^{\phi(p!)} \equiv 1 \pmod{p!} \Rightarrow a^{\phi(p!)\cdot \alpha} \equiv 1 \pmod{p!} \Rightarrow a^{(p-1)!^2} \equiv 1 \pmod{p!} $
Ora, se é vero che $ x^2 \equiv 1 \pmod m \Rightarrow x \equiv \pm 1 \pmod m $,mi basta dimostrare che $ a^{(p-1)!} $non può essere congruo a $ -1 \pmod {p!} $ e ho concluso
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "

Avatar utente
Drago96
Messaggi: 1143
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 123. $p!|a^{(p-1)!}-1$

Messaggio da Drago96 » 15 ago 2012, 19:04

1) $ \phi(p!) = \prod{C_i}\prod{(p_i -1)} $ dove $ C_i $ sono composti mentre i vari $ p_i $ sono primi
Esempio $ \phi(10!) = 10 \cdot 9 \cdot 8 \cdot (7-1) \cdot 6 \cdot (5-1) \cdot 4 \cdot (3-1) \cdot (2-1) $
Non ho letto completamente la tua dimostrazione, ma questo deriva banalmente dalla formula per un n generico della phi di eulero...
Ora, se é vero che $ x^2 \equiv 1 \pmod m \Rightarrow x \equiv \pm 1 \pmod m $
E questo non è assolutamente vero! Solo per i primi vale, per un numero generico è sempre falso (a parte per 2p, con p primo) ;)

Infine, e cosa più importante, è l'esponente ad essere elevato alla seconda, non puoi "portarlo fuori"...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

ant.py
Messaggi: 140
Iscritto il: 18 set 2011, 11:36

Re: 123. $p!|a^{(p-1)!}-1$

Messaggio da ant.py » 15 ago 2012, 21:01

Drago96 ha scritto:
Infine, e cosa più importante, è l'esponente ad essere elevato alla seconda, non puoi "portarlo fuori"...
Ahaha ma certo, che svista :lol:
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 123. $p!|a^{(p-1)!}-1$

Messaggio da jordan » 15 ago 2012, 23:30

Drago96 ha scritto:
1) $ \phi(p!) = \prod{C_i}\prod{(p_i -1)} $ dove $ C_i $ sono composti mentre i vari $ p_i $ sono primi
Esempio $ \phi(10!) = 10 \cdot 9 \cdot 8 \cdot (7-1) \cdot 6 \cdot (5-1) \cdot 4 \cdot (3-1) \cdot (2-1) $
Non ho letto completamente la tua dimostrazione, ma questo deriva banalmente dalla formula per un n generico della phi di eulero...
Quest'esempio non l'ho capito proprio..
The only goal of science is the honor of the human spirit.

Rispondi