ancora sulla phi

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
mario86x
Messaggi: 223
Iscritto il: 01 gen 1970, 01:00
Località: tricase

ancora sulla phi

Messaggio da mario86x »

Sia p un primo, dimostrare che:

$ \varphi(2^{p} - 1) \equiv 0 (mod p) $


P.S. Vietato agli studenti universitari di matematica
P.P.S. Stravietato agli studenti universitari di matematica matricole
P.P.P.S. Assolutamente vietato ai Lordgauss
ReKaio
Messaggi: 565
Iscritto il: 01 gen 1970, 01:00
Località: Terra degli Shura (pisa)
Contatta:

Re: ancora sulla phi

Messaggio da ReKaio »

mario86x ha scritto:Sia p un primo, dimostrare che:

$ \varphi(2^{p} - 1) \equiv 0 (mod p) $


P.S. Vietato agli studenti universitari di matematica
P.P.S. Stravietato agli studenti universitari di matematica matricole
P.P.P.S. Assolutamente vietato ai Lordgauss
rilancio

$ \varphi(a^{p} - 1) \equiv 0 (mod p)\ \ \forall a>1 $
_k_
mario86x
Messaggi: 223
Iscritto il: 01 gen 1970, 01:00
Località: tricase

Messaggio da mario86x »

bravo kayo :P
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Davvero scarsi... Se a > 1 è un intero, \varphi(a^n - 1) \equiv 0 \bmod n, per ogni n \in \mathbb{Z}^+.

@Kayo: you know... It's just for sake of knowledge. :wink:
ReKaio
Messaggi: 565
Iscritto il: 01 gen 1970, 01:00
Località: Terra degli Shura (pisa)
Contatta:

Messaggio da ReKaio »

HiTLeuLeR ha scritto:Davvero scarsi... Se a > 1 è un intero, \varphi(a^n - 1) \equiv 0 \bmod n, per ogni n \in \mathbb{Z}^+.

@Kayo: you know... It's just for sake of knowledge. :wink:
so ^^ in fondo per la dimostrazione che ho in mente serve a nulla che p sia primo
_k_
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Se pensi di usare quei certi risultati di teoria dei gruppi a cui sto pensando io, beh... puoi pure scordartelo! :evil:
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

Bello!!!!!!!!!!!!

Alllloooooooooooooooooova!

Lemma 1. in $ a^{p^{k+1}}-1 $ c'è almeno un primo diverso da $ a^{p^{k}}-1 $.

per dimostrarlo diciamo che $ q|a^{p^{k}}-1 $. Se $ p\neq q $, allora $ q $ non divide $ \displaystyle \frac {a^{p^{k+1}}-1}{a^{p^{k}}-1} = (a^{p^k})^{p-1} + (a^{p^k})^{p-2}+ ... + (a^{p^k}) +1 \equiv p \pmod{q} $ in quanto $ a^{p^k} \equiv 1 \pmod{q} $.

Se invece $ p=q $ allora si può guadagnare al più un fattore $ p $ infatti se $ a^{p^k}=1+sp^r $ con $ s $ non multiplo di $ p $ allora $ a^{p^{k+1}}=(1+sp^r)^p=1+s^pp^{r+1} + p^{r+2}t $. Ma questo è vero solo se $ p\neq2 $ e $ r\neq 1 $ per il quale si guadagnano due fattori $ p $ <-- da tenere a mente. Sapendo quindi che $ p $ è l'unico primo in comune tra $ \displaystyle \frac {a^{p^{k+1}}-1}{a^{p^{k}}-1}= (a^{p^k})^{p-1} + (a^{p^k})^{p-2}+ ... + (a^{p^k}) +1>2p $ (questa disuguaglianza è vero a parte nel caso in cui $ a=3 $ e $ p=2 $ che trattiamo a parte; ma questa affermazione rimane vera anche per $ p=2 $ e $ r=2 $ e $ a>3 $ che quindi "salviamo" come caso) e $ a^{p^{k}}-1 $. Questo vuol dire che $ a^{p^{k+1}}-1 $ ha almeno un fattore diverso primo diverso da quelli di $ a^{p^{k}}-1 $. Ok, mi sono dilungato un po' troppo... :D

Problema vero!!!!!!

vogliamo dimostrare che $ \varphi(a^{p^k} -1) \equiv 0 \pmod{p^k} $

Allora, da tutto lo sproloquio di prima (detto lemma 1) sappiamo che esiste un primo $ q $ tale che $ a^{p^k} \equiv 1 \pmod{q} $ e $ a^{p^{k-1}} \not \equiv 1 \pmod{q} $
Ora, sappiamo che $ p^k|ord_q ( a) $ e quindi $ ord_q(a)=p^r $ con $ r\leq k $. Supponiamo per assurdo che $ r<k $. avremo che $ a^{p^r} \equiv 1 $. ma elevando alla $ p^{k-r-1} $ che è un intero avremo che $ a^{p^{k-1}} \equiv 1^{p^{k-r-1}} \equiv 1 \pmod{q} $ cioè un assurdo. quindi $ ord_q(a)=p^k $ e quindi $ p^k=ord_q(a)|q-1=\varphi(q) | \varphi(a^{p^k}-1) $ (l'ultimo passaggio in quanto la $ \varphi(.) $ è moltiplicativa. Quindi è dimostrato in quanto $ p^k|\varphi(a^{p^k}-1) $.
L'esistenza di $ q $ non è assicurata solo nel caso $ p=2 $, $ a=3 $. però qui si può verificare che $ 2^{k+1}|3^{2^k} -1 $ (per induzione o seguendo il procedimento di prima e quindi $ 2^k|\varphi(3^{2^k}-1) $.

Ora, quando abbiamo $ a^n-1 $ con $ n $ generico possiamo considerare la scomposizione di $ n=p_1^{\alpha_1}p_2^{\alpha_2}...p_r^{\alpha_r} $ e quindi considerare $ a^n-1=(a^{p_2^{\alpha_2}...p_r^{\alpha_r}})^{p_1^{\alpha_1}}-1 $ e quindi $ p_1^{\alpha_1}|a^n-1 $ e così via per gli altri primi.

Spero di non aver dato troppe cose per scontate
ReKaio
Messaggi: 565
Iscritto il: 01 gen 1970, 01:00
Località: Terra degli Shura (pisa)
Contatta:

Messaggio da ReKaio »

$ \varphi(a^n - 1) \equiv 0 \bmod n $, per ogni $ n \in \mathbb{Z}^+ $

prendo $ \mathbb{Z}/(a^n-1) \mathbb{Z}^* $, $ (a,a^n-1)=1 $, allora $ a \in \mathbb{Z}/(a^n-1) \mathbb{Z}^* $. considero, che so, $ <a> $, vedo che $ 1, a, a^2 \dots a^{n-1} $ sono tutti minori di $ a^n-1 $ e distinti, allora individuano diverse classi di resto. Inoltre $ a^n=1 $, quindi $ |<a>|=n $, e $ n=|<a>|||\mathbb{Z}/(a^n-1) \mathbb{Z}^*|=\varphi(a^n-1) $. QED
_k_
Rispondi