Dato un insieme finito di primi $P$, sia $m(P)$ il numero massimo di interi consecutivi, ognuno dei quali divisibile per almeno un elemento di $P$
(i) Dimostrare che $|P|\le m(P)$, con uguaglianza se e solo se $\min(P)>|P|$
(ii) Dimostrare che $m(P)<(|P|+1)(2^{|P|}-1)$
Molto bello
Molto bello
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Re: Molto bello
Un vecchio RMM
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
-
Gerald Lambeau
- Messaggi: 920
- Iscritto il: 07/01/2015, 18:18
Re: Molto bello
Faccio il punto (i).
Sia $|P|=n$ e siano $p_1 < p_2 < \dots <p_n$ gli $n$ primi. Con il teorema cinese del resto è possibile trovare un intero $a$ t. c. $a+i-1 \equiv 0 \pmod{p_i}$ per $i=1, 2, \dots n$, per cui troviamo almeno $n$ numeri consecutivi di cui ciascuno multiplo di almeno uno dei primi, da cui $m(P) \ge |P|$. Ora la seconda parte.
Prima freccia: $min(P)>|P| \Rightarrow m(P)=|P|$. Supponiamo per assurdo che la tesi non sia vera. Allora possiamo trovare un intero $a$ tale che tutti i numeri da $a$ a $a+n$ sono divisibili per qualcuno di questi primi. Per pigeonhole, ne esistono due divisi dallo stesso primo, quindi anche la loro differenza lo è, ma la loro differenza è al più $n$. Quindi, detta $d$ la differenza, si ha che esiste $1 \le j \le n$ t. c. $p_j|d \Rightarrow p_j \le d \le n$, ma vale anche $p_1 \le p_j$ perciò $p_1 \le n$, cioè $min(P) \le |P|$, assurdo.
Seconda freccia: $m(P)=|P| \Rightarrow min(P)>|P|$. Ancora una volta per assurdo. Se $p_1 \le n$, allora posso trovare con il teorema cinese del resto un $a$ t. c.:
- $a+n \equiv 0 \pmod{p_1}$
- $a+i-1 \equiv 0 \pmod {p_{i+1}}$ per $1 \le i \le n-p_1$
- $a+i-1 \equiv 0 \pmod{p_i}$ per $n-p_1+2 \le i \le n$.
Intanto $n>n-p_1 \ge 0$. Inoltre vengono usati, nell'ordine, $p_1$, i primi da $p_2$ a $p_{n-p_1+1}$, infine quelli da $p_{n-p_1+2}$ a $p_n$, quindi ogni primo esattamente una volta. Si noti anche che se $n-p_1$ uguale $0$ il secondo caso non presenta congruenze possibili, mentre il terzo ne presenta $n-1$, sempre per un totale di $n-1$ congruenze impostate fra gli ultimi due casi. Abbiamo dunque che questo sistema di congruenze è lecito e quindi posso trovare un $a$ che ne è soluzione.
Abbiamo che $a+i-1$ è multiplo di almeno uno dei nostri primi tranne per $i=n-p_1+1$ (nonostante abbiamo usato $p_{n-p_1+1}$). Ma in tal caso $a+i-1=a+n-p_1+1-1=a+n-p_1=(a+n)-p_1 \equiv 0 \pmod{p_1}$ (se $n-p_1=0$ questo numero è $a$). Anche $a+n$ è multiplo di $p_1$, quindi tutti i numeri da $a$ a $a+n$ sono multipli di almeno uno dei primi, quindi $m(P) \ge n+1=|P|+1$, assurdo.
Sia $|P|=n$ e siano $p_1 < p_2 < \dots <p_n$ gli $n$ primi. Con il teorema cinese del resto è possibile trovare un intero $a$ t. c. $a+i-1 \equiv 0 \pmod{p_i}$ per $i=1, 2, \dots n$, per cui troviamo almeno $n$ numeri consecutivi di cui ciascuno multiplo di almeno uno dei primi, da cui $m(P) \ge |P|$. Ora la seconda parte.
Prima freccia: $min(P)>|P| \Rightarrow m(P)=|P|$. Supponiamo per assurdo che la tesi non sia vera. Allora possiamo trovare un intero $a$ tale che tutti i numeri da $a$ a $a+n$ sono divisibili per qualcuno di questi primi. Per pigeonhole, ne esistono due divisi dallo stesso primo, quindi anche la loro differenza lo è, ma la loro differenza è al più $n$. Quindi, detta $d$ la differenza, si ha che esiste $1 \le j \le n$ t. c. $p_j|d \Rightarrow p_j \le d \le n$, ma vale anche $p_1 \le p_j$ perciò $p_1 \le n$, cioè $min(P) \le |P|$, assurdo.
Seconda freccia: $m(P)=|P| \Rightarrow min(P)>|P|$. Ancora una volta per assurdo. Se $p_1 \le n$, allora posso trovare con il teorema cinese del resto un $a$ t. c.:
- $a+n \equiv 0 \pmod{p_1}$
- $a+i-1 \equiv 0 \pmod {p_{i+1}}$ per $1 \le i \le n-p_1$
- $a+i-1 \equiv 0 \pmod{p_i}$ per $n-p_1+2 \le i \le n$.
Intanto $n>n-p_1 \ge 0$. Inoltre vengono usati, nell'ordine, $p_1$, i primi da $p_2$ a $p_{n-p_1+1}$, infine quelli da $p_{n-p_1+2}$ a $p_n$, quindi ogni primo esattamente una volta. Si noti anche che se $n-p_1$ uguale $0$ il secondo caso non presenta congruenze possibili, mentre il terzo ne presenta $n-1$, sempre per un totale di $n-1$ congruenze impostate fra gli ultimi due casi. Abbiamo dunque che questo sistema di congruenze è lecito e quindi posso trovare un $a$ che ne è soluzione.
Abbiamo che $a+i-1$ è multiplo di almeno uno dei nostri primi tranne per $i=n-p_1+1$ (nonostante abbiamo usato $p_{n-p_1+1}$). Ma in tal caso $a+i-1=a+n-p_1+1-1=a+n-p_1=(a+n)-p_1 \equiv 0 \pmod{p_1}$ (se $n-p_1=0$ questo numero è $a$). Anche $a+n$ è multiplo di $p_1$, quindi tutti i numeri da $a$ a $a+n$ sono multipli di almeno uno dei primi, quindi $m(P) \ge n+1=|P|+1$, assurdo.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Cit. Marco (mio vero nome)