Dalle APMO 2003...

[Leonida]

Sia $ k \geq 14 $ un intero e sia $ \displaystyle p_k $ il più grande numero primo strettamente minore di $ k $. Sia $ n $ un numero composto. Dimostrare che:

• (a) se $ \displaystyle n= 2p_k $, allora $ n $ NON divide $ \displaystyle (n-k)! $
• (b) se $ \displaystyle n> 2p_k $, allora $ n $ divide $ \displaystyle (n-k)! $

(si può assumere per vera, senza dimostrarla, la disuguaglianza $ \displaystyle p_k \geq \frac{3k}{4} $)

[frod93]

a)
$ n-k=2p-k $
$ 2p-p=p $
$ k>p \implies 2p-k<p $
quindi $ p \not| (n-k) \implies p \not| (n-k)! $ proprio perché $ (n-k) $ è il fattore più grande e non è diviso da $ p $ e essendo primo neanche da tutti gli interi inferiori che vengono fuori dal fattoriale.

Sul secondo punto ho un dubbio:
se prendo $ k=19, p=17, n=35=2p+1 $ ho
$ n-k = 16 $ e $ 17 \not|16! $

[Leonida]

Bene il punto (a)
Riguardo il tuo dubbio, attenzione: tu vuoi dimostrare che $n$ divide $(n -k)!$, non che $p$ divide $(n -k)!$. Nel tuo caso si ha $35 \mid 16!$
che è vero.

[frod93]

Bene il punto (a)
Riguardo il tuo dubbio, attenzione: tu vuoi dimostrare che $n$ divide $(n -k)!$, non che $p$ divide $(n -k)!$. Nel tuo caso si ha $35 \mid 16!$
che è vero.

letto male

[ant.py]

Cmq provo io per il due:
Lemma 1)

Condizione necessaria e sufficiente affinché $ k| b! $ È che, per ogni fattore primo a che compare in k con un esponente c, sia $ b \ge ac $. Infatti ogni a numeri noi troviamo (almeno) un fattore a, per cui devono passare almeno c volte a numeri, da cui $ b \ge ac $ . Detto questo, in realtà basta che $ b \ge max(ac) $ al variare di a e c

Dimostrazione:

Voglio dimostrare che $ n | (n-k)! $
Ora, sia $ n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n} $, $ n > 2p_k \ge \frac{3k}{2} \ge 21 $ (essendo $ k \ge 14 $) quindi $ n > 21 $

siano ora $ q $ e $ \alpha_q $ la coppia fattore- esponente per cui la quantità $ q\alpha_q $ sia massima. Se dimostro che

$ n-k \ge q\alpha_q $, ho vinto per il lemma 1

Inizio notando che

$ n-k \ge \frac{n}{3} $: infatti si ha $ \frac{2n}{3} \ge k $ ovvero $ n \ge \frac{3k}{2} $ che è vera essendo $ n > 2p_k \ge \frac{3k}{2} $

Poi noto che $ \frac{n}{3} \ge q\alpha_q $

Infatti, sia $ n = sq^{\alpha_q} $; avrò $ sq^{\alpha_q} \ge 3q\alpha_q $ ovvero $ sq^{\alpha_q -1} \ge 3\alpha_q $

Se $ \alpha_q = 2 $ si ha $ sq \ge 6 $,
Se s = 1 allora si ha $ q \ge 6 $; essendo pero in questo caso $ n = q^2 $ e $ n > 21 $ allora si ha $ q \ge 5 $; quindi bisogna controllare a mano il caso $ n = 25 $ e si conclude; se $ s \ge 2 $ a maggior ragione

Se $ \alpha_q \ge 3 $, si ha che se s = 1 allora $ q^{\alpha_q-1}\ge 3 \alpha_q $è vera per $ q \ge 3 $; per q = 2 è vera solo se $ \alpha_q \ge 5 $, ma i casi $ \alpha_q = 3,4 $ si escludono perchè n sarebbe minore di 21

Rimane il caso $ \alpha_q = 1 $; in questo caso si ha $ s \ge 3 $, che è sempre soddisfatta a parte il caso in cui $ s= 2 $ (e non puo essere 1 perche in questo caso n non sarebbe composto )
In questo caso, $ n = 2q $ con q primo, di conseguenza si ha $ n = 2q > 2p_k $ quindi $ q > p_k $; ed essendo $ p_k $ il più piccolo numero primo minore di k, ne consegue che $ q > k $. E di conseguenza $ n-k > q \cdot 1 \Rightarrow 2q -q > k $ ovvero $ q > k $ che è vero.

Di conseguenza $ n-k \ge \frac{n}{3} \ge q\alpha_q \Rightarrow n-k \ge q\alpha_q $ che è quello che volevo dimostrare

Spero sia giusta, per quanto ho il sospetto che ne esista una molto più breve..

[Leonida]

Uhm, occhio ad alcuni passaggi: $\displaystyle s$ può anche essere 1! (se ho capito cosa è $\displaystyle s$)

[ant.py]

Hai ragione tu ho provato ad aggiustare, controlla se è giusto.. Ma mi piace sempre meno come soluzione, se ne hai una elegante postala

[jordan]

Sia $ k \geq 14 $ un intero e sia $ \displaystyle p_k $ il più grande numero primo strettamente minore di $ k $. Sia $ n $ un numero composto. Dimostrare che:

• (a) se $ \displaystyle n= 2p_k $, allora $ n $ NON divide $ \displaystyle (n-k)! $

Se fosse $p_k\mid 2p_k \mid (p_k-k)!$ allora $p_k\le 2p_k-k \implies p_k \ge k$, ma per definizione $p_k:=p_{\pi(k-1)} \le k-1$. []

[*] (b) se $ \displaystyle n> 2p_k $, allora $ n $ divide $ \displaystyle (n-k)! $[/list]
(si può assumere per vera, senza dimostrarla, la disuguaglianza $ \displaystyle p_k \geq \frac{3k}{4} $)

Dato che $n\in (\mathbb{N}\setminus \mathbb{P}) \cap [2p_k+1,\infty)$, abbiamo due sole possibilità:
i) $n=2p$ per qualche primo $p>p_k$: e in tal caso $n\mid (n-k)!$ sse $p\le 2p-k$ sse $p\ge k$, che e' vero dato che $p\ge p_{\pi(k-1)+1} \ge k$.
ii) $n=q^2$ per qualche intero $q\ge \sqrt{2p_k+1}$ allora $n\mid (n-k)!$ se $q<2q\le q^2-k$ sse $(q-1)^2\ge k+1$, sse $q\ge \sqrt{k+1}+1$, ma e' vero che $q\ge \sqrt{2p_k+1}\ge \sqrt{\frac{3}{2}k+1}$
iii) esisteranno due interi $3\le a< b$ tali che $n=ab$: allora e' sufficiente che $a<b\le(n-k)$ sse $n(1-\frac{1}{a})\ge k$, ma $n(1-\frac{1}{a})\ge \frac{2}{3}n >\frac{2}{3}\cdot 2p_k \ge \frac{2}{3}\cdot 2 \cdot \frac{3}{4}k =k$. []

[ant.py]

Potresti essere più esplicito? Non ho capito molti passaggi