Problema #1: provare che, per ogni $ n\in\mathfrak{P} $: $ n\sigma(n) \equiv 2 \bmod \varphi(n) $, ove $ \sigma(\cdot) $ denota qui la funzione $ \sigma_1(\cdot) $ dei divisori e $ \varphi(\cdot) $ (come di consueto) la funzione dei totienti di Eulero (click per maggiori informazioni).
Problema #2: mostrare ch'esiste $ v\in\mathbb{N} $ tale che, per ogni $ n > v $: $ n\sigma(n) \equiv 2 \bmod \varphi(n) $ solo se $ n\in\mathfrak{P} $.
La phi, la sigma e alcuni fatti meravigliosi
Re: La phi, la sigma e alcuni fatti meravigliosi
Proviamo con il primo:HiTLeuLeR ha scritto:Problema #1: provare che, per ogni $ n\in\mathfrak{P} $: $ n\sigma(n) \equiv 2 \bmod \varphi(n) $, ove $ \sigma(\cdot) $ denota qui la funzione $ \sigma_1(\cdot) $ dei divisori e $ \varphi(\cdot) $ (come di consueto) la funzione dei totienti di Eulero (click per maggiori informazioni).
Poiché $ \displaystyle n\in\mathfrak{P} $, allora abbiamo:
$ \displaystyle\sigma(n)=n+1 $ e $ \displaystyle\varphi(n)=n-1 $
Quindi la congruenza da verificare sarà:
$ \displaystyle n(n+1)\equiv 2 (\bmod\ n-1) $
Da cui:
$ \displaystyle n^{2}+n-2 \equiv 0 (\bmod\ n-1) $
Affinché questa congruenza sia vera, è necessario che:
$ \displaystyle (n-1)|(n^{2}+n-2) $
Quest'ultima affermazione è sicuramente vera giacché $ \displaystyle n^{2}+n-2=(n+2)(n-1) $. Così la tesi è dimostrata.
Bye,
#Poliwhirl#
un ip-ip-urrà per Whirl...
Sì, Whirl, esattamente. Adesso vediamo come te la cavi con l'altro, però...
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Innanzitutto riscriviamo l'identità come $ n\sigma (n)+k \varphi(n) =2 $ con $ k \in \mathbb{Z} $.
Consideriamo ora quante volte un fattore primo $ p $ è presente nella fattorizzazione di $ n $. Se abbiamo che $ p^j|n $ allora $ p^{j-1}|\varphi(n) $ e quindi avremo che $ p^{j-1}|n\sigma (n)+k \varphi(n)=2 $ e quindi $ p^{j-1}|2 $ cioè un primo dispari è presente al più una volta nella fattorizzazione di n e il 2 è presente al più 2 volte. Ora avremo che, se abbiamo $ m $ primi dispari distinti nella fattorizzazione di $ n $ allora $ 2^m|\sigma(n) $ e $ 2^m|\varphi(n) $ e quindi $ 2^m|2 $ quindi $ m=0 $ o $ m=1 $. Nel primo caso ci sono solo primi pari cioè $ n=2^x $ e nel secondo caso è presente un solo primo dispari che, per la prima osservazione, ha esponente 1, e quindi $ n=2^xp $. Ora, per il primo caso potrà essere solo n=1,2 o 4 per l'osservazione iniziale e in entrambe è verificata l'identità; nel secondo caso avremo:
.$ n=p $ già verificato;
.$ n=2p $ che implica $ 2p(p+1)(2+1) \equiv 2 \bmod {p-1} $ cioè, sapendo che $ p \equiv 1 \bmod {p-1} $, $ 10 \equiv 0 \bmod {p-1} $ cioè $ p-1|10 $ e, sapendo che p è dispari p=3 o 11. infatti n=6 e 22 verificano.
.$ n=4p $ che implica $ 4p(p+1)(4+2+1) \equiv 2 \bmod {2(p-1)} $ cioè, sapendo che $ 2p \equiv 2 \bmod {2(p-1)} $, $ 54 \equiv 0 \bmod {2(p-1)} $ cioè $ p-1|27 $ e, sapendo che p è dispari, non ci sono siffatti p.
In conclusione se n>22 allora l'identità è verificata se e solo se n è primo
Consideriamo ora quante volte un fattore primo $ p $ è presente nella fattorizzazione di $ n $. Se abbiamo che $ p^j|n $ allora $ p^{j-1}|\varphi(n) $ e quindi avremo che $ p^{j-1}|n\sigma (n)+k \varphi(n)=2 $ e quindi $ p^{j-1}|2 $ cioè un primo dispari è presente al più una volta nella fattorizzazione di n e il 2 è presente al più 2 volte. Ora avremo che, se abbiamo $ m $ primi dispari distinti nella fattorizzazione di $ n $ allora $ 2^m|\sigma(n) $ e $ 2^m|\varphi(n) $ e quindi $ 2^m|2 $ quindi $ m=0 $ o $ m=1 $. Nel primo caso ci sono solo primi pari cioè $ n=2^x $ e nel secondo caso è presente un solo primo dispari che, per la prima osservazione, ha esponente 1, e quindi $ n=2^xp $. Ora, per il primo caso potrà essere solo n=1,2 o 4 per l'osservazione iniziale e in entrambe è verificata l'identità; nel secondo caso avremo:
.$ n=p $ già verificato;
.$ n=2p $ che implica $ 2p(p+1)(2+1) \equiv 2 \bmod {p-1} $ cioè, sapendo che $ p \equiv 1 \bmod {p-1} $, $ 10 \equiv 0 \bmod {p-1} $ cioè $ p-1|10 $ e, sapendo che p è dispari p=3 o 11. infatti n=6 e 22 verificano.
.$ n=4p $ che implica $ 4p(p+1)(4+2+1) \equiv 2 \bmod {2(p-1)} $ cioè, sapendo che $ 2p \equiv 2 \bmod {2(p-1)} $, $ 54 \equiv 0 \bmod {2(p-1)} $ cioè $ p-1|27 $ e, sapendo che p è dispari, non ci sono siffatti p.
In conclusione se n>22 allora l'identità è verificata se e solo se n è primo
C'è un problema a livello linguistico, ma su questo punto probabilmente avrei pure potuto sorvolare, penserà qualcuno...Simo_the_wolf ha scritto:[...] Ora, per il primo caso potrà essere solo n=1,2 o 4 per l'osservazione iniziale e in entrambe è verificata l'identità; [...]
Se ci presti attenzione, ti accorgerai che l'ispezione diretta di questo caso avresti anche potuto risparmiartela, viste le tue osservazioni preliminari... Conclusione: il problema può dirsi risolto!Simo_the_wolf ha scritto:[...] $ n=4p $ che implica $ 4p(p+1)(4+2+1) \equiv 2 \bmod {2(p-1)} $ cioè, sapendo che $ 2p \equiv 2 \bmod {2(p-1)} $, $ 54 \equiv 0 \bmod {2(p-1)} $ cioè $ p-1|27 $ e, sapendo che p è dispari, non ci sono siffatti p.