Dimostrare la seguente disuguaglianza:
$ \pi(n)\ge\pi(kn+n)-k\varphi(n) $
Per ogni $ (n,k) \in \mathbb{N}^2 $ con $ n>0 $, con $ \pi(n),\varphi(n) $ rispettivamente la funzione enumerativa dei primi e la funzione totiente di Eulero.
(own)
Disuguaglianza
Disuguaglianza
Aboliamo il latino nei licei scientifici!
Re: Disuguaglianza
credo ci sia un errore nell'argomento di $ \pi $nell'RHSGiulius ha scritto:Dimostrare la seguente disuguaglianza:
$ \pi(n)\ge\pi(kn+n)-k\varphi(n) $
Per ogni $ (n,k) \in \mathbb{N}^2 $ con $ n>0 $, con $ \pi(n),\varphi(n) $ rispettivamente la funzione enumerativa dei primi e la funzione totiente di Eulero.
(own)
MIND TORNA CON NOI
Lemma:
$ \varphi(n)\geq\pi(hn+n)-\pi(hn) $
Infatti, se prendo un primo p compreso tra hn e hn+n, questo è congruo ad un numero coprimo con n modulo n minore di n. Se così non fosse dovrebbe essere
$ p = kn+a $ con a e k aventi almeno un fattore in comune: assurdo, perché p è primo.
Allora ad ogni primo corrisponde a questo modo uno dei numeri coprimi con n (è evidente che due primi tra hn+n e hn sono congrui a numeri coprimi diversi) e il numero di primi è allora al massimo uguale al numero di coprimi minori di n: il lemma è dimostrato. Riscrivendo la disuguaglianza come
$ k\varphi(n)\geq\pi(kn+n)-\pi(n) $
questa risulta immediatamente dimostrata per il lemma.
$ \varphi(n)\geq\pi(hn+n)-\pi(hn) $
Infatti, se prendo un primo p compreso tra hn e hn+n, questo è congruo ad un numero coprimo con n modulo n minore di n. Se così non fosse dovrebbe essere
$ p = kn+a $ con a e k aventi almeno un fattore in comune: assurdo, perché p è primo.
Allora ad ogni primo corrisponde a questo modo uno dei numeri coprimi con n (è evidente che due primi tra hn+n e hn sono congrui a numeri coprimi diversi) e il numero di primi è allora al massimo uguale al numero di coprimi minori di n: il lemma è dimostrato. Riscrivendo la disuguaglianza come
$ k\varphi(n)\geq\pi(kn+n)-\pi(n) $
questa risulta immediatamente dimostrata per il lemma.