OliForum Matematico

Own. Siano $x,y,z$ tre potenze di primi e siano $a,b$ due interi positivi coprimi. Dimostrare che esiste un intero $1\le n\le 6$ tale che $an+b$ e' coprimo con $xyz$.

E' un sacco che non faccio esercizi a modino, quindi molto probabilmente è sbagliata.
Siano $x=p^a, y=q^b, z=r^c$, con $p,q,r\in \mathbb P$
Il problema è equivalente a mostrare che almeno uno fra i numeri dell'insieme $S={a+b, 2a+b, \dots, 6a+b}$ non è multiplo di nessuno fra $p,q,r$.
Per semplicità, andiamo prima ad analizzare la congruenza modulo $p$, consci del fatto di ripoter applicare gli stessi ragionamenti anche con gli altri primi $q$ e $r$ in maniera indipendente graze al teorema cinese.
Distinguiamo fra due casi:
1) $a\equiv 0 \pmod p$
Per ipotesi deve valere che $b\not \equiv 0\pmod p$ , da cui risulta che tutti i numeri di $S$ sono coprimi con $p$.
2) $a\not \equiv 0 \pmod p$
Si noti che se $a\not \equiv 0\pmod p$, allora la classe di resto $\pmod p$ di $na$ al variare di $n$ in $[1,p]$ è una permutazione di $\mathbb Z/p\mathbb Z$.
Segue quindi che anche $na+b$ è una permutazione delle classi di resto (aggiungere di fatto "shifta" le classi).
Nel nostro problema, $n$ varia fra $1$ e $6$, quindi abbiamo 2 sottocasi da analizzare: $p>6$ o $p<6$
Nel primo caso, per quanto detto abbiamo al più un numero fra i sei numeri da analizzare che sia multiplo di $p$.
Nel secondo abbiamo sicuramente 3 multipli di $p$ se $p=2$ e 2 multipli se $p=3$. Se $p=5$ ne abbiamo uno soltanto, oppure 2 esatti se $a+b\equiv 0 \pmod 5$ (è multiplo pure $6a+b$)

Torniamo al problema iniziale. Dalle varie possibilità elencate, si evince che il caso più sfortunato si ha per $p=2, q=3, r=5$ e $a$ coprimo con tutti. Si noti tuttavia fra gli elementi di S ve ne è uno che sicuramente è multiplo di $2$ e anche multiplo di $3$: segue dal fatto che, essendo $a$ coprimo con $2$ e con $3$, (e quindi anche con $6$), la moltiplicazione modulo 6 è una permutazione delle classi di resto modulo $6$. Se ora vi è solo un multiplo di 5 fra gli elementi di $S$, segue la tesi. Se invece $a+b\equiv 0 \pmod 5$, abbiamo 2 multipli di $5$. Tuttavia anche in questo caso uno dei due numeri in questione va a coincidere con un multiplo di $2$: infatti sicuramente un numero fra $a+b$ e $6a+b$ è multiplo di $2$ (fare la differenza fra i due per credere), da cui segue anche qui che vi sono solo 5 numeri "incriminati", e quindi la tesi.
E se $pqr\neq 2\cdot 3 \cdot 5$? E' ancora più facile dimostrare la tesi in quanto vi è al più un multiplo del primo considerato.
E se $a$ non è coprimo con qualche primo? Allora per quanto detto al punto 1, tutti gli elementi di $S$ sono coprimi con il primo considerato

Con i primi 3,5,7 puoi ancora farne 5 per il resto è' tutto giusto

E se consideriamo \(x_1= p_1^{\alpha_1}, \ldots, x_k=p_k^{\alpha_k}\), qual'è il più piccolo \(n_k\) tale che almeno uno degli \( an+b\) al variare di \(1 \le n \le n_k\) sia coprimo con \(x_1\cdot \ldots \cdot x_k\) ?

Si può mostrare in via elementare che questo valore e' minore di $3^k$ e con qualche cannone che è' minore di $2^k$. Chi riesce a fare di meglio?

Anzi, chi prova i due bound sopra?

Sia \(H=p_1 \cdot \ldots \cdot p_k\) il numero con cui cerchiamo un coprimo in \( S = \{a+b, \ldots, a \cdot n_k + b\} \). Per comodità poniamo \(c(n) := an+b\).
Supporremo che \(p_i \nmid a\) per ogni \(i\), altrimenti si avrebbe \(p_i \nmid aj+b\) per ogni \(j\).

First step. Innanzitutto dimostriamo che il numero di coprimi con \(H\) in \(S\) è uguale al numero di coprimi nell'intervallo \([m+1, m+n_k]\), per qualche \(m\) dipendente da \(a,b\).
1. Associamo ad ogni \(p_i\) un \(s_i\) tale che \(c(s_i)\) è il più piccolo numero divisibile per \(p_i\) in \(S\).
2. Notiamo che se \(am +b\) è divisibile per \(p_i\), allora \( p_i \mid a(m-s_i) \ \ \Rightarrow \ \ p_i \mid m-s_i\). Dunque tutti e soli i numeri divisibili per \(p_i\) sono quelli della forma \( c (s_i + mp_i) \).
3. Prendiamo un numero \(M\) tale che \( M + s_i \equiv 0 \pmod{p_i} \) per ogni \(i\). Per TCR siamo certi che esista.
Allora un numero nell'intervallo \(M+t \in [M+1, M+n_k]\) è divisibile per \(p\) se e solo se \( c(t)\) è divisibile per \(p\):
infatti se \(t= s_i+ mp_i\) - ossia quando \( c(t) \) è divisibile per \(p\) - allora \(M+s_i + mp_i \equiv 0 \pmod{p} \) per definizione di \(M\).

Second step. Nel documento qui (Coprimality in special intervals), si dimostra che i coprimi con un certo \(H\) in un intervallo di lunghezza \(n_k\), dove \(k= \omega(H) \), sono almeno:
\[ n_k \frac{ \varphi(H)}{H} - 2^{k-1} \]
da cui siamo sicuri che se un \(n_k\) soddisfa la disuguaglianza:
\[ n_k \ge ( 2^{k-1} +1 )\frac{H}{\varphi(H)} \]
allora di certo va bene. La funzione
\[\frac{H}{\varphi(H)} = \prod_{p \mid H} \frac{1}{1-p^{-1} } = f(p_1, \ldots, p_k) \]
è decrescente in \(p_i\) per tutti gli \(i\): se \(p_i\) cresce, \(p_i^{-1}\) decresce, \(1-p_i^{-1}\) cresce, \(\frac{1}{1-p_i^{-1} }\) decresce. Dunque il massimo di \(f\) si ottiene per \(p_i: =\) i-esimo primo. In G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers, volume 6. Oxford University Press., 2009. si stabilisce che, per ogni \( \varepsilon \in ] 1, \infty[ \), per \(H\) abbastanza grande vale:
\[ \frac{H}{\varphi(H)} \le e^{\gamma} \log \log H \cdot \varepsilon \]
dove \(\gamma\) è la costante di eulero-mascheroni.
Notiamo che \( \log H = \sum_{i=1}^k \log p_k\) è esattamente \(\vartheta(p_k) \), la prima funzione di chebyshev. Visto che
\[ \vartheta(p_k) \le 1.35 k \ln k\]
per \(k \ge 198\) (vedi riferimento, asymptotic bounds), possiamo dire che
\[ \frac{H}{\varphi(H)} \le e^{\gamma} \log \log H \cdot \varepsilon \le e^{\gamma}( \log 1.35 + \log k + \log \log k) \]
Dunque se \(n_k\) soddisfa
\[ n_k \ge ( 2^{k-1} +1 )e^{\gamma} ( \log k + \log \log k ) \varepsilon \]
Allora sicuramente va bene. Abbiamo stabilito perciò che \( n_k = O (2^k \log k)\). Ma si riesce a fare di meglio?

@Jordan, tu hai la dimostrazione per \(2^k\)? Non so, perchè mi viene il dubbio che si possa realizzare l'uguaglianza, con qualche modifica che non altera la crescita asintotica...

Gottinger95 ha scritto:@Jordan, tu hai la dimostrazione per \(2^k\)?

Per il caso $2^k$ ce l'ho assumendo che i $b$ siano nulli, ma credo si possa fare a meno del vincolo.. Vedo di leggermi la tua a breve, scusa il ritardo