Un petit exercice amusant
Salut,
[Selon http://www.les-mathematiques.net/phorum/read.php?5,2318540,2318938#msg-2318938 $ord_p(n)$ vaut $k$ si $p^k\mid n$ et $p^{k+1}\nmid n$. AD]
[Selon http://www.les-mathematiques.net/phorum/read.php?5,2318540,2318938#msg-2318938 $ord_p(n)$ vaut $k$ si $p^k\mid n$ et $p^{k+1}\nmid n$. AD]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Soit $n$ un entier naturel non nul.
\begin{align}
\sum_{\substack{a\in\Z/n\Z\\{\rm pgcd}(a,n)=1}}{\rm pgcd}(a-1,n)=\varphi(n)\tau(n),
\end{align} avec $\varphi(n)$ le nombre d'entiers positifs non nuls premiers à $n$ qui lui sont inférieurs et $\tau(n)$ le nombre de diviseurs de $n$.
(l'identité ci-dessus est l'identité de Menon)
Soit $p$ un nombre premier.
Si $p\leq n$ alors $2p\leq 2n$ ce qui veut dire que $p^2$ divise $(2n)!$.
Si $n<p< 2n$ alors $2p>2n$ donc $p$ divise $(2n)!$ mais $p^k$ ne divise pas $(2n)!$ pour $k\geq 2$.
(le plus petit multiple de $p$ qui n'est pas $p$ est $2p$)
On a donc $f\big(\left(2n\right)!\big)\leq \pi(2n)-\pi(n)$
Réciproquement, tous les nombres premiers $p$ tels que $n<p<2n$ ne peuvent pas avoir leur carré qui divise aussi $(2n)!$ car autrement on aurait $2p>2n$ (le plus petit multiple de $p$ qui n'est pas $p$ est $2p$).
Or, le nombre de nombres premiers $p$ dans l'intervalle $]n,2n[$ est $\pi(2n)-\pi(n)$ donc $f\big(\left(2n\right)!\big)\geq \pi(2n)-\pi(n)$.
Ainsi, on a bien $f\big(\left(2n\right)!\big)= \pi(2n)-\pi(n)$.
Merci jandri pour cette généralisation, j'ai une autre si ça vous intéresse.
Merci aussi à fin de partie pour l'identité de Menon c'est riche.
Dans la suite je préfère noter $v_p$ plutôt que $ord_p$.
La propriété $f_{k-1}((kn)!)=\pi(kn)-\pi(n)$ est immédiate quand $k=2$ (Fin de partie a explicité la démonstration).
Dans le cas général, on peut la démontrer assez rapidement en utilisant la formule de Legendre : $v_p(n!)=\displaystyle\sum_{k=1}^{+\infty}\lfloor n/p^k\rfloor$.
En effet, on déduit de la formule de Legendre que $\lfloor n/p\rfloor\leq v_p(n!)<\displaystyle\sum_{k=1}^{+\infty} n/p^k=\dfrac n{p-1}$.
Si $p\geq n+1$ alors $v_p((kn)!)<\dfrac{kn}{p-1}\leq k$ donc $v_p((kn)!)\leq k-1$.
Si $p\leq n$ alors $v_p((kn)!)\geq \lfloor kn/p\rfloor\geq k$.
On a démontré que $f_{k-1}((kn)!)=\pi(kn)-\pi(n)$.