Un altro problema dalle gare preliminari delle Olimpiadi Baltiche 2003.
Essendo $ n \in \mathbb{Z}^+ $, si denotino rispettivamente con $ s $ e $ v $ la somma e il numero dei divisori interi positivi di $ n $ che siano pure $ < n $. Se $ n = s + v $, mostrare che $ n = 2m^2 $, per qualche $ m\in\mathbb{Z}^+ $.
Se n = somma + numero dei divisori < n, allora n = 2m^2
Noiosissima da scrivere...
Problema: Essendo $ n \in \mathbb{Z}^+ $, si denotino rispettivamente con $ s $ e $ v $ la somma e il numero dei divisori interi positivi di $ n $ che siano pure $ < n $. Se $ n = s + v $, mostrare che $ n = 2m^2 $, per qualche $ m\in\mathbb{Z}^+ $.
Lemma: La funzione $ \displaystyle\sigma_0(n) $ restituisce un numero dispari se e solo se $ \displaystyle n $ è un quadrato perfetto.
Dimostrazione del lemma:
Sia $ \displaystyle n=p_{1}^{\alpha_1}p_{2}^{\alpha_2}\dots p_{n}^{\alpha_n} $ dove i $ \displaystyle p_i $ sono fattori primi distinti, allora avremo $ \displaystyle\sigma_0(n)=(\alpha_1+1)(\alpha_2+1)\dots (\alpha_n+1) $; se $ n $ è un quadrato perfetto tutti gli $ \displaystyle\alpha_i $ sono pari, quindi $ \displaystyle\sigma_0(n) $ sarà dispari, essendo prodotto di fattori dispari; se n non è un quadrato perfetto esisterà almeno un $ \displaystyle\alpha_i $ dispari, quindi $ \displaystyle\sigma_0(n) $ sarà pari poiché conterrà almeno un fattore pari.
Dimostrazione del problema:
Per ipotesi $ \displaystyle s=\sigma_1(n)-n $; $ \displaystyle v=\sigma_0(n)-1 $ e quindi $ \displaystyle n=s+v $; dunque:
$ \displaystyle n=\sigma_0(n)+\sigma_1(n)-1-n $
$ \displaystyle 2n=\sigma_0(n)+\sigma_1(n)-1 $
$ \displaystyle n=\frac{\sigma_0(n)+\sigma_1(n)-1}{2} $
Supponiamo che $ \displaystyle n $ non sia un quadrato perfetto; $ \displaystyle\sigma_0(n) $ sarà pari, quindi, ricordando che $ \displaystyle n $ deve essere intero e considerando l'ultima uguaglianza ottenuta, possiamo dire che $ \displaystyle\sigma_1(n) $ deve essere necessariamente dispari.
Inoltre, sempre considerando l'ultima uguaglianza scritta possiamo dire che $ \displaystyle n=2^{\alpha_1}p_{2}^{\alpha_2}\dots p_{n}^{\alpha_n} $, quindi $ \displaystyle\sigma_1(n)=(2^{\alpha_1}+2^{\alpha_1-1}+\dots +1)(p_{2}^{\alpha_2}+p_{2}^{\alpha_2-1}+\dots +1) $
$ \displaystyle\dots (p_{n}^{\alpha_n}+p_{n}^{\alpha_n-1}+\dots +1) $; questo prodotto, come detto in precedenza, deve essere necessariamente dispari, quindi ciascuno dei suoi fattori deve essere dispari; $ \displaystyle \sum_{k=0}^{\alpha_1} 2^{\alpha_1-k} $ è sempre dispari qualsiasi valore assuma $ \displaystyle\alpha_1 $; ognuna delle somme $ \displaystyle\sum_{k=0}^{\alpha_i} p_{i}^{\alpha_i-k} $ è dispari se e solo se ciascun $ \displaystyle\alpha_i $ è pari; quindi possiamo scrivere $ \displaystyle n=2m^2 $ ($ 2 $ è contenuto un numero di volte dispari in $ n $ che altrimenti sarebbe un quadrato perfetto, contro l'ipotesi iniziale fatta).
Ora supponiamo che $ \displaystyle n $ sia un quadrato perfetto; $ \displaystyle\sigma_0(n) $ sarà dispari, quindi poiché $ \displaystyle n=\frac{\sigma_0(n)+\sigma_1(n)-1}{2} $ allora $ \displaystyle\sigma_1(n) $ deve necessariamente essere pari; ma $ \displaystyle\sigma_1(n)=(p_{1}^{\alpha_1}+p_{1}^{\alpha_1-1}+\dots +1)(p_{2}^{\alpha_2}+p_{2}^{\alpha_2-1}+\dots +1) $
$ \displaystyle\dots (p_{n}^{\alpha_n}+p_{n}^{\alpha_n-1}+\dots +1) $ è dispari, poiché in questo caso ogni $ \displaystyle\alpha_i $ è pari e quindi $ \displaystyle\sigma_1(n) $ è prodotto di fattori tutti dispari; da qui l'impossibilità che $ n $ sia un quadrato perfetto.
Ci ho perso la testa a scrivere queste poche righe...
Bye,
#Poliwhirl#
Lemma: La funzione $ \displaystyle\sigma_0(n) $ restituisce un numero dispari se e solo se $ \displaystyle n $ è un quadrato perfetto.
Dimostrazione del lemma:
Sia $ \displaystyle n=p_{1}^{\alpha_1}p_{2}^{\alpha_2}\dots p_{n}^{\alpha_n} $ dove i $ \displaystyle p_i $ sono fattori primi distinti, allora avremo $ \displaystyle\sigma_0(n)=(\alpha_1+1)(\alpha_2+1)\dots (\alpha_n+1) $; se $ n $ è un quadrato perfetto tutti gli $ \displaystyle\alpha_i $ sono pari, quindi $ \displaystyle\sigma_0(n) $ sarà dispari, essendo prodotto di fattori dispari; se n non è un quadrato perfetto esisterà almeno un $ \displaystyle\alpha_i $ dispari, quindi $ \displaystyle\sigma_0(n) $ sarà pari poiché conterrà almeno un fattore pari.
Dimostrazione del problema:
Per ipotesi $ \displaystyle s=\sigma_1(n)-n $; $ \displaystyle v=\sigma_0(n)-1 $ e quindi $ \displaystyle n=s+v $; dunque:
$ \displaystyle n=\sigma_0(n)+\sigma_1(n)-1-n $
$ \displaystyle 2n=\sigma_0(n)+\sigma_1(n)-1 $
$ \displaystyle n=\frac{\sigma_0(n)+\sigma_1(n)-1}{2} $
Supponiamo che $ \displaystyle n $ non sia un quadrato perfetto; $ \displaystyle\sigma_0(n) $ sarà pari, quindi, ricordando che $ \displaystyle n $ deve essere intero e considerando l'ultima uguaglianza ottenuta, possiamo dire che $ \displaystyle\sigma_1(n) $ deve essere necessariamente dispari.
Inoltre, sempre considerando l'ultima uguaglianza scritta possiamo dire che $ \displaystyle n=2^{\alpha_1}p_{2}^{\alpha_2}\dots p_{n}^{\alpha_n} $, quindi $ \displaystyle\sigma_1(n)=(2^{\alpha_1}+2^{\alpha_1-1}+\dots +1)(p_{2}^{\alpha_2}+p_{2}^{\alpha_2-1}+\dots +1) $
$ \displaystyle\dots (p_{n}^{\alpha_n}+p_{n}^{\alpha_n-1}+\dots +1) $; questo prodotto, come detto in precedenza, deve essere necessariamente dispari, quindi ciascuno dei suoi fattori deve essere dispari; $ \displaystyle \sum_{k=0}^{\alpha_1} 2^{\alpha_1-k} $ è sempre dispari qualsiasi valore assuma $ \displaystyle\alpha_1 $; ognuna delle somme $ \displaystyle\sum_{k=0}^{\alpha_i} p_{i}^{\alpha_i-k} $ è dispari se e solo se ciascun $ \displaystyle\alpha_i $ è pari; quindi possiamo scrivere $ \displaystyle n=2m^2 $ ($ 2 $ è contenuto un numero di volte dispari in $ n $ che altrimenti sarebbe un quadrato perfetto, contro l'ipotesi iniziale fatta).
Ora supponiamo che $ \displaystyle n $ sia un quadrato perfetto; $ \displaystyle\sigma_0(n) $ sarà dispari, quindi poiché $ \displaystyle n=\frac{\sigma_0(n)+\sigma_1(n)-1}{2} $ allora $ \displaystyle\sigma_1(n) $ deve necessariamente essere pari; ma $ \displaystyle\sigma_1(n)=(p_{1}^{\alpha_1}+p_{1}^{\alpha_1-1}+\dots +1)(p_{2}^{\alpha_2}+p_{2}^{\alpha_2-1}+\dots +1) $
$ \displaystyle\dots (p_{n}^{\alpha_n}+p_{n}^{\alpha_n-1}+\dots +1) $ è dispari, poiché in questo caso ogni $ \displaystyle\alpha_i $ è pari e quindi $ \displaystyle\sigma_1(n) $ è prodotto di fattori tutti dispari; da qui l'impossibilità che $ n $ sia un quadrato perfetto.
Ci ho perso la testa a scrivere queste poche righe...
Bye,
#Poliwhirl#
Re: Noiosissima da scrivere...
Lol! Soluzione impeccabile, mio simpaticissimo pokemon.Poliwhirl ha scritto:Ci ho perso la testa a scrivere queste poche righe...
Si vuole $ (\sigma_1(n) - n) + (\sigma_0(n) - 1) = n $, i.e. $ \sigma_1(n) + \sigma_0(n) = 2n+1 $, ove $ \{\sigma_k(\cdot)\}_{k \in \mathbb{R}} $ è la famiglia delle funzioni aritmetiche dei divisori. Sia pertanto $ n = 2^t \cdot q $, dove $ t \in \mathbb{N} $ e $ q \in 2\mathbb{N}+1 $. Se $ q = 1 $, ne risulta $ (2^{t+1} - 1) + (t+1) = 2^{t+1} + 1 $, che è vero sse $ t = 1 $, viz $ n = 2 \cdot 1^2 $.
Ammettiamo dunque $ q > 1 $ per il seguito e poniamo $ \displaystyle q = \prod_{i=1}^r p_i^{\alpha_i} $, dove $ r $ è un intero positivo; $ p_1, p_2, \ldots, p_r $ sono primi naturali dispari a due a due distinti e $ \alpha_i \in \mathbb{Z}^+ $, per ogni $ i = 1, 2, \ldots, r $. Si ha $ \sigma_1(n) + \sigma_0(n) = 2n+1 $ sse $ \displaystyle (2^t-1) \cdot \prod_{i=1}^r (1 + p_i + \ldots + p_i^{a_i}) + (1+t)\cdot \prod_{i=1}^r (1 + a_i) = 2n + 1 $, per dedurne che dev'essere $ \displaystyle t \cdot \prod_{i=1}^r (1+a_i) \equiv 1 \bmod 2 $. E allora $ t \equiv 1 \bmod 2 $ ed $ a_i \equiv 0 \bmod 2 $, per ogni $ i = 1, 2, \ldots, r $, cioè $ q =b^2 $ e $ t = 2s + 1 $, ove $ s, b\in\mathbb{N} $, i.e. $ n = 2m^2 $, con $ m = 2^s \cdot b $. Ne seguita la tesi, q.e.d.
Ammettiamo dunque $ q > 1 $ per il seguito e poniamo $ \displaystyle q = \prod_{i=1}^r p_i^{\alpha_i} $, dove $ r $ è un intero positivo; $ p_1, p_2, \ldots, p_r $ sono primi naturali dispari a due a due distinti e $ \alpha_i \in \mathbb{Z}^+ $, per ogni $ i = 1, 2, \ldots, r $. Si ha $ \sigma_1(n) + \sigma_0(n) = 2n+1 $ sse $ \displaystyle (2^t-1) \cdot \prod_{i=1}^r (1 + p_i + \ldots + p_i^{a_i}) + (1+t)\cdot \prod_{i=1}^r (1 + a_i) = 2n + 1 $, per dedurne che dev'essere $ \displaystyle t \cdot \prod_{i=1}^r (1+a_i) \equiv 1 \bmod 2 $. E allora $ t \equiv 1 \bmod 2 $ ed $ a_i \equiv 0 \bmod 2 $, per ogni $ i = 1, 2, \ldots, r $, cioè $ q =b^2 $ e $ t = 2s + 1 $, ove $ s, b\in\mathbb{N} $, i.e. $ n = 2m^2 $, con $ m = 2^s \cdot b $. Ne seguita la tesi, q.e.d.