OliForum Matematico

Trovare tutte le coppie di interi positivi $(a,b)$ tali che $a^{b-1} \mid b!$

Se $b=1$ le ipotesi valgono per ogni $a$, se invece $b=2$ devo avere che $a|2$, che vale se $a=1$ o $a=2$.

Considero quindi ora il caso in cui $b$ è maggiore di 2.
Sia $p$ un primo che divide $a$. Ho che $\displaystyle\upsilon_p(b!)=\sum_{i=1}^{b}{\upsilon_p(i)}=\sum_{i=1}^{\infty}{\left\lfloor \frac{b}{p^i} \right\rfloor}\leq \sum_{i=1}^{\infty}{\frac{b}{p^i}}\leq \frac{b}{p-1}$, ma per $p>2$ ho che $\displaystyle\frac{b}{p-1}<b-1$ (perchè $b>2$).
Quindi per $p>2$ vale $\displaystyle\upsilon_p(b!)\leq \frac{b}{p-1}<b-1\leq \upsilon_p(a^{p-1})$, ma quindi $a$ deve essere una potenza di 2 e in particolare deve essere uguale a 2 perchè $\displaystyle\upsilon_p(b!)\leq b<2(b-1)$ che è minore di $ \upsilon_p(a^{p-1})$, se la valutazione $p$-adica di $a$ è maggiore di 1.

Quindi voglio trovare i $b$ per cui $2^{b-1}|b!$.

So che $\upsilon_2(2^{n+1}!)=2\upsilon_2(2^n!)+1$, ma quindi per induzione su $n$ ho che $\upsilon_2(2^n!)=2^n-1$ (perchè $\upsilon_2(2!)=1$ e poi facilmente).
In particolare le potenze di 2 sono gli unici $b$ per cui $\upsilon_2(b!)=b-1$, in quanto $\upsilon_2(b!)=\upsilon_2(2^{t_b}!)+\upsilon_2(2^{t_{b-2^{t_b}}}!)+...$ (con $2^{t_i}$ la più grande potenza di 2 minore di $i$), che è minore di $b-1$, in quanto $2^{t_b}+2^{t_{b-2^{t_b}}}+...\leq b$.

Quindi le possibile coppie di interi positivi $(a,b)$ t.c. $a^{b-1}|b!$ sono $(a,1)$, $(1,2)$ e $(2,2^n)$, per ogni scelta di $a$ ed $n$.

(scritta parecchio male spero almeno non sia sbagliata)

Sostanzialmente corretta, ma se fossi in gara prenderesti al massimo 6/7.. (a,n)=(1,2000)?

funzionano anche $(1,b)$ per ogni $b$...

Posto anche la mia, visto che già l'avevo scritta, ma le idee base sono le stesse di quelle di sopra:

Mostriamo che $ (a,n) $ e' soluzione se e solo se $ \min\{a,n\}=1 $, oppure $ a=2 $ e $ n $ e' un potenza di $ 2 $: abbiamo che la tesi e' valida se e solo se $ \upsilon_p(a^{n-1})\le \upsilon_p(n!) $ per ogni $ p\in \mathbb{P} $. Se $ a=1 $ allora possiamo scegliere qualunque $ n\in \mathbb{N}_0 $. D'altra parte, se $ n=1 $ allora possiamo scegliere qualunque $ a\in \mathbb{N}_0 $. Dunque per il seguito ammettiamo $ \min\{a,n\}\ge 2 $.Se $ \text{gpf}(a):=q \ge 3 $ allora $ n-1 \le \upsilon_q(a^{n-1})\le \upsilon_q(n!)= $ $ \sum_{i\in \mathbb{N}_0}{\lfloor nq^{-i}\rfloor} $ $ <\sum_{i\in \mathbb{N}_0}{nq^{-i}}= $ $ \frac{n}{q-1} \le \frac{n}{2} $, assurdo visto che abbiamo assunto $ n\ge 2 $: quindi $ a=2^k $ per qualche $ k \in \mathbb{N}_0 $. Resta da verificare che $ \upsilon_2(a^{n-1})\le \upsilon_2(n!) $ che e' equivalente a $ k(n-1) \le \sum_{i\in \mathbb{N}_0}{\lfloor n2^{-i}\rfloor} < \sum_{i\in \mathbb{N}_0}{n2^{-i}}=n $, allora $ k< \frac{n}{n-1}=1+\frac{1}{n-1}\le 2 $: dato che $ k \in \mathbb{N}_0 $, allora $ k=1 $. Restano da trovare tutti e i soli interi positivi $ n $ tali che $ 2^{n-1} \mid n! $. Esistono (ed unici) degli interi $ 0\le a_1<a_2<a_3<\ldots<a_t $ tali che $ n=\sum_{j=1}^t{2^{a_j}} $, per qualche $ t\in \mathbb{N}_0 $ (in pratica, e' la sua rappresentazione binaria). Dobbiamo verificare che $ n-1 \le \upsilon_2(n!)= $ $ \sum_{i\in \mathbb{N}_0}{\sum_{j=1}^t{\lfloor 2^{a_j-i}\rfloor}} $ $ =\sum_{j=1}^t{\sum_{i\in \mathbb{N}_0}{\lfloor 2^{a_j-i}\rfloor}} $ $ =\sum_{j=1}^t{\left(2^{a_j}-1\right)}=n-t $ che e' sufficiente a concludere $ t=1 $, cioè $ n $ e' una potenza di $ 2 $. []