p|sigma(p-1), problema 1

[jordan]

Sia $ \sigma(\cdot): \mathbb{N}_0 \to \mathbb{N}_0 $ la funzione che associa a ogni $ n \in \mathbb{N} $ la somma dei suoi divisori $ \sum_{d \mid n}{d} $ (ad esempio $ \sigma(6)=6+3+2+1 $ e $ \sigma(8)=8+4+2+1 $).
Trovare tutti i primi $ p \in \mathbb{P} $ tali che $ p \mid \sigma(p-1) $.
(Salvatore Tringali)

[kn]

Verificato che $ \displaystyle~p=2 $ non è una soluzione, consideriamo un ipotetico $ \displaystyle~p>2 $ che soddisfa la richiesta. $ \displaystyle~p-1>1 $, quindi ha una scomposizione con almeno un primo. È noto che $ \displaystyle~\sigma(\cdot) $ è una funzione moltiplicativa. Segue che se $ \displaystyle~p-1=q_1^{e_1}\cdot q_2^{e_2}\cdots q_m^{e_m} $ è la fattorizzazione di $ \displaystyle~p-1 $ (con $ \displaystyle~q_i\in\mathbb{P} $ e $ \displaystyle~e_i>0 $ per ogni $ \displaystyle~i $) dobbiamo avere $ \displaystyle~p\mid \sigma(q_1^{e_1})\cdot\sigma(q_2^{e_2})\cdots\sigma(q_m^{e_m}) $. Essendo $ \displaystyle~p $ primo l'ultima divisibilità implica che esiste un $ \displaystyle~i $ tale che $ \displaystyle~p\mid\sigma(q_i^{e_i}) $. Poniamo $ \displaystyle~q=q_i $ e $ \displaystyle~a=e_i $. Otteniamo $ \displaystyle~p\mid\sum_{d\mid q^a}d=\sum_{x=0}^a q^x=\frac{q^{a+1}-1}{q-1} $ (dato che $ \displaystyle~q^a $ è divisibile solo per potenze di $ \displaystyle~q $). Ora $ \displaystyle~q-1 $ non è divisibile per $ \displaystyle~p $ (se lo fosse allora varrebbe $ \displaystyle~q=tp+1 $ per qualche $ \displaystyle~t $; ma $ \displaystyle~q>1 $ quindi $ \displaystyle~t>0 $, da cui $ \displaystyle~q\ge p+1 $, assurdo dato che $ \displaystyle~q\le p-1 $). Ciò significa che il numero di fattori $ \displaystyle~p $ nella fattorizzazione di $ \displaystyle~\frac{q^{a+1}-1}{q-1} $ è uguale a quello nella fattorizzazione di $ \displaystyle~q^{a+1}-1 $, dunque $ \displaystyle~p\mid q^{a+1}-1 $. Dunque possiamo scrivere due equazioni:
$ \displaystyle~q^a\mid p-1 $ implica $ \displaystyle~jq^a=p-1 $ per qualche $ \displaystyle~j $
$ \displaystyle~p\mid q^{a+1}-1 $ implica $ \displaystyle~kp=q^{a+1}-1 $ per qualche $ \displaystyle~k $
La prima si può riscrivere come $ \displaystyle~jq^a+1=p $, o anche $ \displaystyle~jkq^a+k=kp $. Confrontando quest'ultima equazione con la seconda otteniamo $ \displaystyle~jkq^a+k=q^{a+1}-1 $ o $ \displaystyle~q^{a+1}-jkq^a=k+1 $. Dato che $ \displaystyle~q^a $ divide il primo membro di questa equazione deve dividere anche il secondo: $ \displaystyle~q^a\mid k+1 $. Da questo deduciamo $ \displaystyle~q^a\le k+1 $, cioè $ \displaystyle~q^a-1\le k $. Quindi
$ \displaystyle~q^a-1\le k=\frac{q^{a+1}-1}{p}<\frac{q^{a+1}-1}{q^a}=q-\frac{1}{q^a}<q $
da cui $ \displaystyle~q^a<q+1 $, o anche $ \displaystyle~q^a\le q $. Ma se $ \displaystyle~a>1 $ $ \displaystyle~q^a>q $ (essendo $ \displaystyle~q>1 $). Perciò $ \displaystyle~a=1 $. Ora, quanto scritto sopra diviene $ \displaystyle~q-1\le k<q $, per cui (dato che le tre espressioni sono intere) $ \displaystyle~k=q-1 $, che sostituito nell'equazione $ \displaystyle~kp=q^{a+1}-1 $ ci dà $ \displaystyle~(q-1)p=q^2-1 $, quindi $ \displaystyle~p=q+1 $. Ma due primi che differiscono di $ \displaystyle~1 $ possono essere solo $ \displaystyle~2 $ e $ \displaystyle~3 $. Deve perciò essere $ \displaystyle~p=3 $, che peraltro soddisfa la richiesta e dunque è l'unica soluzione.

[karlosson_sul_tetto]

4° volta...

[jordan]

4° volta...

Cerco di essere gentile: Quando la finirai di postare messaggi del genere nella sezione olimpica (il resto non è che mi importi più di tanto) farai un grosso favore non solo a me, ma a tutti gli utenti dell'Oliforum!
Spero di essere stato chiaro.

[karlosson_sul_tetto]

E mò ho un paradosso:se scrivo,jordan mi amazza,se non scrivo jordan nn capisce se ho letto o no;qualcuno mi aiuta a risolverlo?











P.S.tanto ho gia scritto quindi jordan mi uccide

[kn]

4^ volta cosa?

[dario2994]

Bella soluzione... io ero arrivato fino al punto del sistema di congruenze... da là non sono riuscito a concludere... bel metodo :)

@ Karlosson: io sono meno gentile di jordan... hai scassato il cazzo.

[karlosson_sul_tetto]

4^ volta cosa?

4° postaggio che ho letto

Bella soluzione... io ero arrivato fino al punto del sistema di congruenze... da là non sono riuscito a concludere... bel metodo

@ Karlosson: io sono meno gentile di jordan... hai scassato il cazzo.

Veramente l'ho scassato la settimana scorsa!!

[jordan]

@dario: sei diventato ufficialmente mio collega
@kn: leggo la tua soluzione appena ho5 minuti liberi,scusami
@Karlosson: inizia col cancellare gli altri 4 messaggi, e non è un consiglio.

[Maioc92]

la mia è praticamente identica a quella di kn, differisce solo nella parte centrale ma poi giungo alle stesse conclusioni. Domani la posto tutta, perchè è un po' lunghina (come la sua) e ora sono un po' stanco. Scusate

[exodd]

quesito bonus)
dimostrare che q=gpd(p-1), dove gpd sta per "massimo divisore primo"

[karlosson_sul_tetto]

la mia è praticamente identica a quella di kn, differisce solo nella parte centrale ma poi giungo alle stesse conclusioni. Domani la posto tutta, perchè è un po' lunghina (come la sua) e ora sono un po' stanco. Scusate

E poi mi dicono a me che il forum non è un chat...

[dario2994]

La bonus question l'avevo perfino dimostrata nel pdf ufficiale xD Sperando di guadagnarci qualche punto...
Si nota che che se q non è il massimo divisore primo allora $ q^{\alpha+1}<p $ e quindi non può essere congruo a 1.
Peccato che non servisse nella dimostrazione xD

[Maioc92]

la mia è praticamente identica a quella di kn, differisce solo nella parte centrale ma poi giungo alle stesse conclusioni. Domani la posto tutta, perchè è un po' lunghina (come la sua) e ora sono un po' stanco. Scusate

E poi mi dicono a me che il forum non è un chat...

almeno io faccio commenti che riguardano il problema, e scrivo in questo modo poche volte, mentre tu spammi abitualmente ovunque. Tra l'altro "mi dicono a me" è leggermente sbagliato dal punto di vista grammaticale.
Se vuoi un mio consiglio segui solo le sezioni più adatte a te, almeno finchè non sarai appena un po' più grande e riuscirai a scrivere qualcosa di sensato nelle altre

[exodd]

La bonus question l'avevo perfino dimostrata nel pdf ufficiale xD Sperando di guadagnarci qualche punto...
Si nota che che se q non è il massimo divisore primo allora $ q^{\alpha+1}<p $ e quindi non può essere congruo a 1.
Peccato che non servisse nella dimostrazione xD

invece a me è servito:
ho levato prima il caso q=2 (che portava a p=3) grazie a questa proprietà!
poi si poteva uscire in meno passaggi, dato che p e q erano entrambi dispari...