an+b coprimo con xyz
an+b coprimo con xyz
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$.
The only goal of science is the honor of the human spirit.
Re: an+b 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
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
"We' Inge!"
LTE4LYF
LTE4LYF
Re: an+b coprimo con xyz
Con i primi 3,5,7 puoi ancora farne 5 
per il resto è' tutto giusto
per il resto è' tutto giustoThe only goal of science is the honor of the human spirit.
-
Gottinger95
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: an+b coprimo con xyz
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\) ?
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: an+b coprimo con xyz
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?
The only goal of science is the honor of the human spirit.
Re: an+b coprimo con xyz
Anzi, chi prova i due bound sopra?
The only goal of science is the honor of the human spirit.
-
Gottinger95
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: an+b coprimo con xyz
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...
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...
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: an+b coprimo con xyz
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 ritardoGottinger95 ha scritto:@Jordan, tu hai la dimostrazione per \(2^k\)?
The only goal of science is the honor of the human spirit.