Sia $ n>4 $ un intero composto tale che $ n \mid \varphi(n)\sigma(n)+1 $. Mostrare che $ \omega(n) \ge 3 $.
Nb. Qui $ \varphi(n)=|\{a \in \mathbb{N}_0:(a,n)=1\}|, \sigma(n)=\sum_{d|n}{d},\mathbb{P}:=\{2,3,5,\ldots\} $ e $ \omega(n)=|\{p \in \mathbb{P}:p|n\}| $.
n| phi(n)sigma(n) +1 allora omega(n)>2
n| phi(n)sigma(n) +1 allora omega(n)>2
The only goal of science is the honor of the human spirit.
Allora...
Prima di tutto se $ \displaystyle n=\prod_{i=1}^k{p_i^{a_i}} $ è la fattorizzazione di n, si ha $ \displaystyle \phi(n)=n\prod_{i=1}^k{\frac{p_i-1}{p_i}} $ e $ \displaystyle \sigma(n)=\prod_{i=1}^k{\frac{p_i^{a_i+1}-1}{p_i-1}} $, da cui $ \displaystyle \phi(n)\sigma(n)=\prod_{i=1}^k{p_i^{a_i-1}(p_i^{a_i+1}-1)} $.
Supponiamo per assurdo esista un n fattorizzabile in $ n=p^uq^v $ che soddisfa le ipotesi, si avrà necessariamente $ \displaystyle\phi(n)\sigma(n)+1\equiv 0 \pmod p $ ovvero $ p^{u-1}q^{v-1}(p^{u+1}-1)(q^{v+1}-1)+1\equiv 0 \pmod p $.
Per $ u\geq 2 $ si perviene ad un assurdo in quanto deve essere $ 1\equiv 0 \pmod p $, quindi $ u=1 $. Un discorso analogo porta a concludere $ v=1 $.
In conclusione $ p,q $ devono soddisfare $ (p^2-1)(q^2-1)+1\equiv (1-q^2)+1\rightarrow q^2\equiv 2 \pmod p $ lo stesso discorso si può fare per $ \displaystyle p\rightarrow p^2\equiv 2\pmod q $.
La tesi diviene $ pq|p^2+q^2-2\rightarrow \frac{p^2+q^2-2}{pq} (*) $ è intero e $ p,q $ sono primi distinti.
Supponiamo quindi per assurdo che p sia diverso da q; $ (P,Q) $ sia la soluzione della $ (*) $ che minimizza $ p+q $ e sia wlog $ P>Q $.
Cosideriamo ora l'equazione associata $ p^2+Q^2-2=kpQ\rightarrow p^2-kQp+Q^2-2=0 $; di tale quadratica conosciamo la soluzione $ p_1=P\rightarrow p_2=kQ-P=\frac{Q^2-2}{P} $ dalle formule di Vieta; poichè si è assunto $ P>Q\geq 1 $ risulterà necessariamente $ 1\leq \frac{Q^2-2}{P}<P $, ma ciò è in contraddizione con l'ipotesi che $ P+Q $ sia minimo; ne seque $ p=q $, assurdo in quanto $ p, q $ sono primi distinti.
è molto probabile che abbia commesso qualche errore...
Prima di tutto se $ \displaystyle n=\prod_{i=1}^k{p_i^{a_i}} $ è la fattorizzazione di n, si ha $ \displaystyle \phi(n)=n\prod_{i=1}^k{\frac{p_i-1}{p_i}} $ e $ \displaystyle \sigma(n)=\prod_{i=1}^k{\frac{p_i^{a_i+1}-1}{p_i-1}} $, da cui $ \displaystyle \phi(n)\sigma(n)=\prod_{i=1}^k{p_i^{a_i-1}(p_i^{a_i+1}-1)} $.
Supponiamo per assurdo esista un n fattorizzabile in $ n=p^uq^v $ che soddisfa le ipotesi, si avrà necessariamente $ \displaystyle\phi(n)\sigma(n)+1\equiv 0 \pmod p $ ovvero $ p^{u-1}q^{v-1}(p^{u+1}-1)(q^{v+1}-1)+1\equiv 0 \pmod p $.
Per $ u\geq 2 $ si perviene ad un assurdo in quanto deve essere $ 1\equiv 0 \pmod p $, quindi $ u=1 $. Un discorso analogo porta a concludere $ v=1 $.
In conclusione $ p,q $ devono soddisfare $ (p^2-1)(q^2-1)+1\equiv (1-q^2)+1\rightarrow q^2\equiv 2 \pmod p $ lo stesso discorso si può fare per $ \displaystyle p\rightarrow p^2\equiv 2\pmod q $.
La tesi diviene $ pq|p^2+q^2-2\rightarrow \frac{p^2+q^2-2}{pq} (*) $ è intero e $ p,q $ sono primi distinti.
Supponiamo quindi per assurdo che p sia diverso da q; $ (P,Q) $ sia la soluzione della $ (*) $ che minimizza $ p+q $ e sia wlog $ P>Q $.
Cosideriamo ora l'equazione associata $ p^2+Q^2-2=kpQ\rightarrow p^2-kQp+Q^2-2=0 $; di tale quadratica conosciamo la soluzione $ p_1=P\rightarrow p_2=kQ-P=\frac{Q^2-2}{P} $ dalle formule di Vieta; poichè si è assunto $ P>Q\geq 1 $ risulterà necessariamente $ 1\leq \frac{Q^2-2}{P}<P $, ma ciò è in contraddizione con l'ipotesi che $ P+Q $ sia minimo; ne seque $ p=q $, assurdo in quanto $ p, q $ sono primi distinti.
è molto probabile che abbia commesso qualche errore...
Ultima modifica di travelsga il 05 mag 2009, 19:10, modificato 1 volta in totale.
Credo che hai abbondato di $ pq $travelsga ha scritto:In conclusione $ p,q $ devono soddisfare $ pq(p^2-1)(q^2-1)+1\equiv (1-q^2)+1\rightarrow q^2\equiv 2 \pmod p $
Good..travelsga ha scritto:Cosideriamo ora l'equazione associata $ p^2+Q^2-2=kpQ\rightarrow p^2-kQp+Q^2-2=0 $
Solo con $ Q=1 $ non credo puoi affermare quella disuguaglianza; ci spieghi meglio comunque perchè è una contraddizione?travelsga ha scritto:...poichè si è assunto $ P>Q\geq 1 $ risulterà necessariamente $ 1\leq \frac{Q^2-2}{P}<P $, ma ciò è in contraddizione con l'ipotesi che $ P+Q $ sia minimo..
In ogni caso non è finita..
The only goal of science is the honor of the human spirit.
Re: n| phi(n)sigma(n) +1 allora omega(n)>2
Sembra oramai di leggere Tringali e il suo formalismo bizantino.jordan ha scritto:Sia $ n>4 $ un intero composto tale che $ n \mid \varphi(n)\sigma(n)+1 $. Mostrare che $ \omega(n) \ge 3 $.
Nb. Qui $ \varphi(n)=|\{a \in \mathbb{N}_0:(a,n)=1\}|, \sigma(n)=\sum_{d|n}{d},\mathbb{P}:=\{2,3,5,\ldots\} $ e $ \omega(n)=|\{p \in \mathbb{P}:p|n\}| $.
...
Avevo completamente dimenticato di analizzare il caso $ \omega(n)=1 $ 
Vediamo di concludere il lavoro...
Come si è notato in precedenza ogni primo che compare nella fattorizzazione di n ha esponente 1, infatti $ \forall 1\leq i\leq k $ si ha $ \displaystyle\prod_{1\leq i\leq k}{p_i^{a_i-1}(p_i^{a_i+1}-1)}+1\equiv 0 \pmod {p_i}\rightarrow \forall 1\leq i\leq k, a_i=1 $.
Pertanto se $ \omega(n)=1 $, $ n=p $ contro l'ipotesi che n sia composto.
Vediamo di concludere il lavoro...
Come si è notato in precedenza ogni primo che compare nella fattorizzazione di n ha esponente 1, infatti $ \forall 1\leq i\leq k $ si ha $ \displaystyle\prod_{1\leq i\leq k}{p_i^{a_i-1}(p_i^{a_i+1}-1)}+1\equiv 0 \pmod {p_i}\rightarrow \forall 1\leq i\leq k, a_i=1 $.
Pertanto se $ \omega(n)=1 $, $ n=p $ contro l'ipotesi che n sia composto.