Republicação de problema (e resolução) sobre valoração p-ádica :: Repost of a problem (and solution) on p-adic valuation

Publicado em 24 de Março de 2018 por Américo Tavares

(Daqui e daqui)

Enunciado do 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.

Problem Statement

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

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) e 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

Advertisement

Sobre Américo Tavares

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

2 respostas a Republicação de problema (e resolução) sobre valoração p-ádica :: Repost of a problem (and solution) on p-adic valuation

  1. beni22sof diz:
    31 de Março de 2018 às 22:56

    It is possible to prove that the exponent of 13 is exactly 5. The idea is that in the floors written in the valuations n=13^5 and p=13 so after simplifications we have just a sum of the form \lfloor 3^7/13^i \rfloor+\lfloor -3^7/13^i \rfloor. Using the fact that \lfloor x \rfloor + \lfloor -x \rfloor =-1 if x is not an integer we get that the valuation, and therefore the exponent of 13 in the binomial exponent is exactly equal to 5.

    Responder

Deixe uma Resposta

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

Gravatar
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 )

Cancelar

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.