OliForum Matematico

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)

Giulius 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)

credo ci sia un errore nell'argomento di $ \pi $nell'RHS

Nu è giusto ....

credevo ci fosse un errore di battitura.. come punizione dovro risolvere il problema! nn oggi pero,ho gia superato il mio limite di problemi giornalieri

Jacobi ha scritto:nn oggi pero,ho gia superato il mio limite di problemi giornalieri

Perché no? Se la guardi bene è una disuguaglianza immediata!

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.

Perfect

Pairo ha scritto:Se così non fosse dovrebbe essere

$ p = kn+a $ con a e k aventi almeno un fattore in comune: assurdo, perché p è primo.

Questa parte qui però non mi è chiara, forse intendevi p=hn+a con a e n aventi un fattore in comune, assurdo...

Sì, sì intendevo n invece di k