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

(Daqui e daqui)

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) .$

$\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$

Anúncios

## 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:

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$.

• beni22sof diz:

Another proof :) Using Kummer’s theorem (https://en.wikipedia.org/wiki/Kummer%27s_theorem) the valuation $v_p({n\choose m})$ is equal to the number of carries when adding $n-m$ and $m$ in base $p$. In our case we need to add the “numbers” $[12,12,0,0,10]$ and $[12,12,3]$ in base $13$. One may see immediately that there are indeed $5$ carries. :)

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