$\varphi(2^n-1)/(2^n-1)$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

$\varphi(2^n-1)/(2^n-1)$

Messaggio da jordan »

Sia $\varepsilon>0$ fissato.

(a) Mostrare che esistono infiniti $n$ tali che
$$
\frac{\varphi(2^n-1)}{2^n-1}< \varepsilon.
$$

(b) Mostrare che esistono infiniti $n$ tali che
$$
\frac{\varphi(2^n-1)}{2^n-1}> 1-\varepsilon.
$$
The only goal of science is the honor of the human spirit.
Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da Troleito br00tal »

Molto carino!

Ricordiamo la seguente formula:
\begin{equation}
\frac{\phi(n)}{n} = \prod_{p|n} (1-\frac{1}{p})
\end{equation}

a)
Sia $n \ge 3$ un intero positivo. Poniamo $x_n=\prod_{i=1}^n (p_i-1)$ dove $p_i$ è l'$i$-esimo primo. Notiamo che, per ogni $1 < i \le n$, $p_i$ divide $2^{x_n}-1$ per il piccolo teorema di Fermat, poiché $p_i-1$ divide $x_n$. Di conseguenza:
\begin{equation}
\frac{\phi(2^{x_n}-1)}{2^{x_n}-1} \le \prod_{i=2}^n (1-\frac{1}{p_i}) < \frac{2}{-1+\log{n}}
\end{equation}
dove la seconda disuguaglianza è un utile esercizio. Perciò, se $n>e^{1+2{\varepsilon}^{-1}}$, $\frac{\phi(2^{x_n}-1)}{2^{x_n}-1} < \varepsilon$.

b)
Vale il seguente utile fatto, dove $p$ e $q$ sono primi: se $p$ divide $2^q-1$, allora $q$ divide $p-1$. Questo implica banalmente $p>q$. In particolare, il numero di primi distinti che dividono $2^q-1$ è al più $\log_q{2^q}=q\log_q{2}$, poiché $2^q-1$ è prodotto di fattori maggiori di $q$. Perciò:
\begin{equation}
\frac{\phi(2^q-1)}{2^q-1} = \prod_{p|2^q-1}^n (1-\frac{1}{p}) \ge (1-\frac{1}{q+1})^{q\log_q{2}} = (1+\frac{1}{q})^{-q\log_q{2}} > e^{-\log_q{2}} \ge 1-\log_q{2}
\end{equation}
poiché $(1+\frac{1}{q})^{q} < e$ e $e^x \ge 1+x$. Entrambi sono lasciati come esercizi (mi dispiace lasciare tutti questi conti, ma forse è più utile se li scrive qualcuno che non abbia già visto un corso di Analisi I). Perciò, se $q>2^{\varepsilon^{-1}}$, vale $\frac{\phi(2^q-1)}{2^q-1}>1-\varepsilon$.
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da Gerald Lambeau »

Facciamo gli esercizi gentilmente lasciatici da Troleito.
Inizio da $e^x \ge x+1$. Consideriamo $e^x-x$. Voglio mostrare che $\displaystyle \lim_{x \rightarrow \pm\infty} e^x-x=+\infty$.
Se $x$ tende a meno infinito si ha $\displaystyle \lim_{x \rightarrow -\infty} e^x-x=\lim_{x \rightarrow -\infty} e^x+\lim_{x \rightarrow -\infty} -x=0+\infty=+\infty$. Per l'altro limite invece ci serviamo di un altro passaggio: $e^x \ge 2x$ per $x$ sufficientemente grande. Lo dimostreremo passando prima per l'induzione sui naturali. $e^1 \ge 2 \cdot 1$, quindi il passo base è ok. $e^{n+1}=e \cdot e^n \ge e \cdot 2 \cdot n \ge 4 \cdot n \ge 2(n+1)$ per $n\ge1$, quindi anche il passo induttivo è ok.
Ora, scelto $1<y<2$, voglio $e^{n+y}>2(n+y)$ per $n$ sufficientemente grande (si noti che così vado a dimostrarlo per $x \ge n+1$ dove $n$ è quello che vedremo, ma poco importa perché a noi la disuguaglianza ci serve per dimostrare un limite all'infinito).
$e^{n+y}=e^n \cdot e^y \ge e^y \cdot 2n$. Ora, $e^y \cdot 2n \ge 2(n+y) \Leftrightarrow e^y \ge 1+2\dfrac{y}{n}$, ma questa è sempre vera per $n \ge \dfrac{4}{e-1}$ per come è stato scelto $y$.
Bene, $e^x \ge 2x \Rightarrow e^x-x \ge x$, e siccome $\displaystyle \lim_{x \rightarrow +\infty} x=+\infty$, anche la nostra funzione si comporta così, che è quello che ci piaceva.
Che ci facciamo con tutta questa roba? Semplice, il fatto che $e^x-x$ sia continua (è differenza di funzioni continue) in $\mathbb{R}$ e che all'infinito, da entrambe le parti, diventi molto grossa (e non molto piccola, che sennò era un problema), ci permette di scegliere un intervallo sufficientemente largo, diciamo $[-10^{100}, 10^{100}]$, e direi che possiamo stare sicuri di trovare il minimo lì dentro.
Non sto a verificare tutte le ipotesi, ma direi che siamo tutti d'accordo che il minimo si trova, per Weierstrass, o sugli estremi (ma li abbiamo scelti belli larghi quindi chissene) o dove la derivata si annulla.
La derivata è $e^x-1$ che è nulla in $x=0$ e in nessun altro punto, quindi il minimo di $e^x-x$ è $e^0-0=1$, perciò $e^x \ge x+1$ e siamo tutti felici.

Adesso liquidiamo $\left(1+\dfrac{1}{q}\right)^q<e$ ponendo $q=\dfrac{1}{e^x-1}$ con $x \not=0$, che si può fare senza problemi perché $q \ge 2$. La disuguaglianza diventa $e^{\frac{x}{e^x-1}}<e \Leftrightarrow \dfrac{x}{e^x-1}<1 \Leftrightarrow x+1<e^x$ (quest'utlimo passaggio è legale perché, essendo $q$ positivo, anche $e^x-1$ deve esserlo, e dunque moltiplicare non cambia il verso della disuguaglianza) e direi che è sempre vero per quanto detto prima. L'uguale si può trovare solo nei punti di minimo di $e^x-x$, ma abbiamo visto che l'unico è $x=0$ che abbiamo escluso, quindi... Volendo si può dire che se $x$ tende a $0$, cioè se $q$ tende a infinito, quel minore diventa un uguale, ottenendo così il limite noto $\displaystyle \lim_{x \rightarrow +\infty} \left(1+\frac{1}{x}\right)^x=e$.

Scusate se sono sceso troppo nel dettaglio, ma (anche per la scuola, diciamo) voglio farle bene queste cose, quindi se c'è qualche castroneria ditemelo.

Il primo esercizio lasciato invece ancora mi sfugge, ma se qualcuno volesse un'altra strada per dimostrare che $\displaystyle \prod_{i=2}^{\infty} \left(1-\frac{1}{p_i}\right)=0$, vi suggerisco questa che ho trovato che è molto carina:
Testo nascosto:
sfruttare una certa connessione tra l'inverso di quel prodotto e la seria armonica
.
"If only I could be so grossly incandescent!"
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da jordan »

Molto bene! :) Allora vi lascio anche un bonus:

(c) Mostrare che per ogni intervallo $0\le a<b\le 1$ esistono infiniti $n$ tali che
$$
\frac{\varphi(2^n-1)}{2^n-1} \in (a,b).
$$
The only goal of science is the honor of the human spirit.
Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da <enigma> »

Gerald Lambeau ha scritto: 05 nov 2017, 19:02 Il primo esercizio lasciato invece ancora mi sfugge
È un Mertens povero affatto semplice, perlomeno tecnicamente per un concorrente delle olimpiadi: la via più veloce che conosco è
Testo nascosto:
dimostrare l'identità $\sum_{n \leq x} \log n=\sum_{n \leq x}\Lambda(n) \left \lfloor x/n \right \rfloor$; sommare per parti $\sum_{n \leq x }\Lambda(n)/n$ e dedurne stime su $\sum _{p \leq x}1/p$; esponenziare e concludere
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da Troleito br00tal »

Posto la mia dimostrazione di
\begin{equation}
\prod_{i=2}^n (1-\frac{1}{p_i}) < \frac{2}{-1 + \log{n}}
\end{equation}
che tra l'altro segue la linea di dimostrazione accennata di Gerald Lambeau. Consideriamo l'inverso dell'LHS
\begin{equation}
(1-\frac{1}{2})^{-1} \prod_{i=2}^n (1-\frac{1}{p_i})^{-1} = \sum_{f(k) \le p_n} \frac{1}{k} \ge \sum_{i=1}^{p_n} \frac{1}{i} > \log{p_n} > \log{n}
\end{equation}
dove $f(m)$ è il più grande primo che divide $m$. Perciò
\begin{equation}
\prod_{i=2}^n (1-\frac{1}{p_i}) < \frac{2}{\log{n}} < \frac{2}{-1 + \log{n}}
\end{equation}
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da Gerald Lambeau »

jordan ha scritto: 06 nov 2017, 12:33 (c) Mostrare che per ogni intervallo $0\le a<b\le 1$ esistono infiniti $n$ tali che
$$
\frac{\varphi(2^n-1)}{2^n-1} \in (a,b).
$$
Un hint?
"If only I could be so grossly incandescent!"
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da jordan »

Visto che è un po' difficile, c'è la soluzione su quest'articolo di Florian Luca (le domande "elementari" erano le prime due)
The only goal of science is the honor of the human spirit.
Rispondi