Problema do mês :: Problem of the month #1. (Valoração p-ádica :: p-adic valuation). Resolução :: Solution

ver/see Problema do mês Problem of the month

\bigskip

Problem: Let m be the greatest positive integer such that \dfrac{1}{13^m}\dbinom{13^5}{3^7}\in\mathbb{N}. Find with proof an upper bound for m.

Claim: 10 is an upper bound for m. Find a smaller one.

\bigskip

Problema: Seja m o maior inteiro positivo tal que \dfrac{1}{13^m}\dbinom{13^5}{3^7}\in\mathbb{N}.  Determine, justificando, um majorante de m.

Afirmação não demonstrada: 10   é um majorante de m. Encontre um mais pequeno.

Solution par Pierre Bernard, France

On sait que

 v_{p}\left( \dbinom{n}{k}\right) =\displaystyle\sum_{i=1}^{+\infty }\left( \left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor \right) .

De plus, chaque terme

 \left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor\dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor

vaut 0 ou 1 (on a toujours \left\lfloor x+y\right\rfloor -\left\lfloor x\right\rfloor -\left\lfloor y\right\rfloor qui vaut 0 ou 1).

Si i est assez grand, il est clair que

\left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor =0.

Précisément, puisque n\geq k, il suffit que p^{i}>n, c’est-à-dire i>\log _{p}(n) pour que

\left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor =0.

On a donc:

v_{p}\left( \dbinom{n}{k}\right) =\displaystyle\sum_{i=1}^{\left\lfloor \log_{p}(n)\right\rfloor }\underset{0\text{ ou }1}{\underbrace{\left( \left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor \right) }}\leq\left\lfloor \log _{p}(n)\right\rfloor

Donc

v_{13}\left( \dbinom{13^{5}}{3^{7}}\right) \leq \left\lfloor \log_{13}(13^{5})\right\rfloor =5

Et 5 c’est mieux que 10 :)

\bigskip

* * *

\bigskip

Solution by Pierre Bernard, France; translated by Américo Tavares

We know that

 v_{p}\left( \dbinom{n}{k}\right) =\displaystyle\sum_{i=1}^{+\infty }\left( \left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor \right) .

Furthermore, each  term

 \left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor\dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor

is 0 or 1 (we have allways \left\lfloor x+y\right\rfloor -\left\lfloor x\right\rfloor -\left\lfloor y\right\rfloor which is  0 or 1).

For i sufficiently large it is clear that we have

\left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor =0.

And because  n\geq k it is  sufficient that p^{i}>n, i. e. i>\log _{p}(n) to have [Translator’s note: slightly edited on July 22, 2009]

\left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor =0.

Therefore

v_{p}\left( \dbinom{n}{k}\right) =\displaystyle\sum_{i=1}^{\left\lfloor \log_{p}(n)\right\rfloor }\underset{0\text{ or }1}{\underbrace{\left( \left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor \right) }}\leq\left\lfloor \log _{p}(n)\right\rfloor

Thus

v_{13}\left( \dbinom{13^{5}}{3^{7}}\right) \leq \left\lfloor \log_{13}(13^{5})\right\rfloor =5

And 5 is better than 10 :)

Other solvers: fede (comments in Gaussianos‘s blog) and fatima

\bigskip

* * *

\bigskip

Resolução de Pierre Bernard, França;  tradução de Américo Tavares.

Sabe-se que

 v_{p}\left( \dbinom{n}{k}\right) =\displaystyle\sum_{i=1}^{+\infty }\left( \left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor \right) .

Além disso, cada termo

 \left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor\dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor

vale  0 ou 1 (tem-se sempre \left\lfloor x+y\right\rfloor -\left\lfloor x\right\rfloor -\left\lfloor y\right\rfloor   que é igual a  0 ou 1).

Para  i suficientemente grande é claro que se tem

\left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor =0.

Ora, dado que n\geq k, é suficiente que  p^{i}>n, isto é i>\log _{p}(n) para se ter

\left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor =0.

Portanto:

v_{p}\left( \dbinom{n}{k}\right) =\displaystyle\sum_{i=1}^{\left\lfloor \log_{p}(n)\right\rfloor }\underset{0\text{ ou }1}{\underbrace{\left( \left\lfloor \dfrac{n}{p^{i}}\right\rfloor -\left\lfloor \dfrac{k}{p^{i}}\right\rfloor -\left\lfloor \dfrac{n-k}{p^{i}}\right\rfloor \right) }}\leq\left\lfloor \log _{p}(n)\right\rfloor

Deste modo

v_{13}\left( \dbinom{13^{5}}{3^{7}}\right) \leq \left\lfloor \log_{13}(13^{5})\right\rfloor =5

E 5 é melhor do que 10 :)

Outros: fede (commentários no blogue Gaussianos) and fatima

\bigskip

* * *

\bigskip

Notas:

1. v_{p}(r) designa a valoração (ou valorização)  p-ádica (valuation p-adique) de  r: o expoente do número primo p na decomposição em factores primos do inteiro r. Por outras palavras,  p^{v_{p}(r)} divide r mas p^{1+v_{p}(r)} não divide r.

2. Também se usa a notação \text{ord}_p(r) (ordem ou ordinal de r em p) com o mesmo significado.

3. v_{p}\left(\dfrac{r}{s}\right) =v_{p}(r)-v_{p}(s) (com \dfrac{r}{s}\in\mathbb{Q}).

4. Teorema de Legendre: Qualquer que seja o inteiro positivo n, o expoente do número primo p na decomposição em números primos  de n! é igual a

\displaystyle\sum_{i\geq 1}\displaystyle\left\lfloor\dfrac{n}{p^i}\right\rfloor

\bigskip

Remarks:

1. v_{p}(r) denotes  the p-adic valuation of  r: the exponent of the prime p in the factorization into prime numbers of the integer r. In other words  p^{v_{p}(r)} divides r and p^{1+v_{p}(r)} does not divide r.

2. With the same meaning another notation is also used: \text{ord}_p(r) (order or ordinal of r at p)

3. v_{p}\left(\dfrac{r}{s}\right) =v_{p}(r)-v_{p}(s) (with \dfrac{r}{s}\in\mathbb{Q}).

4. Theorem (Legendre): For every positive integer n, the exponent of the prime number p in the factorization into prime numbers of  n! is

\displaystyle\sum_{i\geq 1}\displaystyle\left\lfloor\dfrac{n}{p^i}\right\rfloor

\bigskip

* * *

\bigskip

Aproveito para  relembrar que podem resolver o problema #2.

I take this opportunity to remember that you can solve the problem #2.

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Matemática, Math, Problem Of The Month, Problema do mês, Problemas com as etiquetas , , , , . ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s