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?
123. $p!|a^{(p-1)!}-1$
Re: 123. $p!|a^{(p-1)!}-1$
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.
-
- Messaggi: 232
- Iscritto il: 07 mag 2012, 11:51
Re: 123. $p!|a^{(p-1)!}-1$
Bene! A te il testimone
p.s. per chi volesse trovarla, assicuro che esiste anche una dimostrazione che non fa uso del lemma LTE
p.s. per chi volesse trovarla, assicuro che esiste anche una dimostrazione che non fa uso del lemma LTE
Re: 123. $p!|a^{(p-1)!}-1$
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:
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
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:
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. "
Re: 123. $p!|a^{(p-1)!}-1$
Non ho letto completamente la tua dimostrazione, ma questo deriva banalmente dalla formula per un n generico della phi di eulero...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) $
E questo non è assolutamente vero! Solo per i primi vale, per un numero generico è sempre falso (a parte per 2p, con p primo)Ora, se é vero che $ x^2 \equiv 1 \pmod m \Rightarrow x \equiv \pm 1 \pmod m $
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)
Re: 123. $p!|a^{(p-1)!}-1$
Ahaha ma certo, che svistaDrago96 ha scritto:Infine, e cosa più importante, è l'esponente ad essere elevato alla seconda, non puoi "portarlo fuori"...
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. "
Re: 123. $p!|a^{(p-1)!}-1$
Quest'esempio non l'ho capito proprio..Drago96 ha scritto:Non ho letto completamente la tua dimostrazione, ma questo deriva banalmente dalla formula per un n generico della phi di eulero...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) $
The only goal of science is the honor of the human spirit.