Les pgcd et ppcm
dans Arithmétique
Bonjour
Je ne comprends pas la formule donnée dans la dernière ligne.
Je ne comprends pas la formule donnée dans la dernière ligne.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
-- Schnoebelen, Philippe
Edit: Grillé !
comment arrives-tu à te convaincre que pgcd*ppcm = a*b ?
C'est que dans le pgcd, chaque exposant est à sa valeur la plus faible.
(pour être un diviseur commun, il ne faut pas qu'il aille au-delà, pour être le plus grand, il faut au moins cela)
Et que dans le ppcm, chaque exposant est à sa valeur la plus grande.
(pour être un multiple, il faut au moins cela, pour être le plus petit, il ne doit pas aller au-delà)
Le produit des 2 est le produit de a par b.
Cordialement
En fait tu fais une lecture totalement passive.
Si tu avais réellement LU ACTIVEMENT chacune des lignes, en challengeant le texte, et te posant ligne à ligne la question : qu'est-ce qu'on me raconte ? C'est dès la première ou la 2ème ligne que tu arrèterais la lecture, et tu demanderais : qu'est-ce qu'on me raconte ?
Le point 2 en dessous de l'encadré, ( celui que tu ne comprends pas) c'est une redite, une copie du point 2 dans l'encadré ( que tu as compris, vu que tu ne demandes pas d'explication). Tu as gobé le point 2 dans l'encadré ... comme ça, comme une lettre à la poste... et tu te réveilles au moment de la dernière ligne : Tiens, au fait, je ne comprends rien de ce que j'ai lu.
@Math Coss
Je sais calculer le PGCD avec la décomposition en facteurs premiers. Je demandais comment passer de la formule 2 de la proposition à la formule 2 de la remarque.
Le PGCD est $2 \times 3^2$.
@Lourran
Le point 2 de la proposition est démontré dans le livre, alors que le point 2 qui suit ne l'est pas, c'est pour cela que je demande.
Je ne trouve pas comment utiliser $v_p( PGCD(a,b))=\min (v_p(a),v_p(b))$ pour montrer que $PGCD(a,b)=\displaystyle\prod_{i=1}^k p_i ^{\min (\alpha_i,\beta_i)}$
C'est le plus grand des entiers naturel $k$ tels que $p^k$ divise $a$. Si $p$ ne divise pas $a$ alors $v_p(a)=0$.
Maintenant comme on sait qu'on peut écrire n'importe quel entier naturel $a$ non nul comme produit de puissances des nombres premiers qui le divisent de façon unique (il faudrait préciser le sens mais j'imagine que tu comprends le sens ici) à l'ordre des facteurs près alors on a une façon commode d'écrire cette factorisation de $a$ avec les nombres $v_p(a)$.
Cette remarque jointe aux propriétés énoncées dans 2) permet d'obtenir la remarque 2)
Cordialement
Donc PGCD(a,b) (qui est un entier naturel) est égal au produit des premiers qui le composent (du coup ceux qui composent a et b) exposant la valuation p adique de PGCD(a,b)
A ce moment la tu utilise le point 2 de la proposition et c'est terminé ! Je te laisse le faire.
Ça en devient effrayant la...
Que peut-on en conclure pour X et Y ?
Sachant qu'on peut toujours reconstituer le nombre en réunissant les tranches.
Connaissant les tranches de $a$ et $b$ on peut connaître facilement ce que seront les tranches du pgcd de a et b et leur ppcm. C'est le sens des résultats énoncés dans l'extrait copié.
PS:
Une "tranche" pour un nombre $a$ est le couple $(p,v_p(a))$
@Lourran
Que $X$ et $Y$ sont égaux.
La valuation $p$-adique est la puissance sur les $p_i$ dans la décomposition en facteurs premiers.
On a $a= \displaystyle\prod_{i=1}^k p_i ^{v_{p_i(a)}}$ et $b= \displaystyle\prod_{i=1}^k p_i ^{v_{p_i(b)}}$
J'étais entêté à vouloir utiliser les décompositions de $a$ et $b$ alors que c'est inutile ici.
On écrit $PGCD(a,b)= \displaystyle\prod_{i=1}^k p_i ^{v_{p_{i} (PGCD(a,b))}}$
Or $v_{p_{i} (PGCD(a,b))}= \min ( v_{p_i(a)}, v_{p_i(b)})$
Donc $\boxed{PGCD(a,b)= \displaystyle\prod_{i=1}^k p_i ^{ \min ( v_{p_i(a)}, v_{p_i(b)})}}$.
Inutile de chercher en voilà un :
Démontrer que $v_p(n!)=\sum_{k=1}^\infty E(\dfrac{n}{p^k}) $
Voici mon raisonnement.
Remarquons que $\dfrac{n}{p^k} <1 \Leftrightarrow E(\dfrac{n}{p^k})=0$
On a $\dfrac{n}{p^k}n<1 \Leftrightarrow n<p^k \Leftrightarrow k> E(\dfrac{n}{p^k})$
Posons $m= E(\dfrac{n}{p^k})$.
Comme $v_p(n!)=\displaystyle\sum_{k=1}^n v_p(k)$, il s'agit de montrer que $\boxed{\displaystyle\sum_{k=1}^n v_p(k)=\displaystyle\sum_{k=1}^m E(\dfrac{n}{p^k})}$
Et ici je bloque.
Peux tu expliquer pourquoi $n< p^k$ est équivalent à $k>E(n/p^k)$?
J'ai vu la preuve de wikipédia mais je ne l'ai pas comprise, ils vont trop vite.
Ok je reprends. J'ai été trop vite et j'ai écrit des bêtises.
$\dfrac{n}{p^k} <1 \iff n < p^k \iff \ln \ n < k \ln \ p \iff k > \dfrac{ \ln \ n }{\ln \ p}$
Or $k > \dfrac{ \ln \ n }{\ln \ p} \iff k > \left\lfloor \dfrac{ \ln \ n }{\ln \ p} \right\rfloor$
Posons $m= \left\lfloor \dfrac{ \ln \ n }{\ln \ p} \right\rfloor$ ainsi si $k \geq m$ alors $\left\lfloor \dfrac{ n }{p^k} \right\rfloor=0$.
Première étape que j'ai lu dans wikipédia mais qui n'est pas démontrée :
1) Dénombrons les multiples de $p^k$ qui appartiennent à $[|1,n|]$.
Soit $q \in \N^{*}$.
On a $1 \leq p^k q \leq n \iff \dfrac{1}{p^k} \leq q \leq \dfrac{n}{p^k} \iff 1 \leq q \leq \left\lfloor \dfrac{n}{p^k} \right\rfloor$
Il y a $ \left\lfloor \dfrac{n}{p^k} \right\rfloor$ multiples de $p^k$ dans $[|1,n|]$.
2) $v_p(n!)=v_p(1)+v_p(2) + \cdots +v_p(n)=\displaystyle\sum_{d=1}^n v_p (d)$
Je bloque ici.
D’abord, tu as les nombres pairs, présent dans 2, 4, 6, 8, 10, 12, 14 et 16 (il y en a 17//2=8 en notation pythonesque).
Oui mais les multiples de 4 ? Tu as 4, 8, 12 et 16 (il y en a 17//4=4).
Oui mais les multiples de 8 ? Tu as 8 et 16 (il y en a 17//8=2).
Oui mais les multiples de 16 ? Il y a 16 (17//16=1).
Oui mais… non, ça dépasse.
-- Schnoebelen, Philippe
J'ai trouvé une épreuve de concours BECEAS qui détaille mieux la question.
Je sais faire toutes les questions sauf la question b) qui me bloque.
$v_p(n!)=\displaystyle\sum_{l=1}^n v_p(l)$
Il doit y avoir une histoire de partition mais je ne la vois pas.
\left\lfloor \dfrac{ \ln \ n }{\ln \ p}
\right\rfloor$"
Bonjour OShine,
Cette équivalence est fausse.
Ici k est entier.
formule?
Ta formule ci-dessus est problématique: que sont $d,n$?
Par contre, l'idée qu'on peut partitionner l'ensemble des entiers naturels non nuls suivant la plus grande puissance de $p$ qui divise un entier ($v_p(n)$) me semble correcte*.
Si $E_p(k):=\{\text{ensemble des entiers $n$ tels que $\displaystyle v_p(n)=k$}\}$
On a bien que $\displaystyle \mathbb{N^\star}=\sqcup_{k=0}^\infty E_p(k)$
*: loué soit le théorème fondamental de l'arithmétique.
Question 7.a :
Soit $n \in \N^{*}$. Soit $p$ un nombre premier et $k \in \N$. Dénombrons les multiples de $p^k$ qui appartiennent à $[|1,n|]$.
Soit $q \in \N^{*}$. Alors $1 \leq qp^k \leq n \iff \dfrac{1}{p^k} \leq q \leq \dfrac{n}{p^k} \iff 1 \leq q \leq E(n/p^k)$
Donc $\boxed{\alpha_k=E(\dfrac{n}{p^k} )}$
Question 7.b :
$v_p(n!)=\displaystyle\sum_{d=1}^n v_p(d)=\displaystyle\sum_{k=0}^{+\infty} \left( \displaystyle\sum_{d \in [|1,n|] \ \ v_p(d)=k} v_p(d) \right)=\displaystyle\sum_{k=1}^{+\infty} k \left( \displaystyle\sum_{d \in [|1,n|] \ \ v_p(d)=k} 1 \right) \\
= \displaystyle\sum_{k=1}^{+\infty} k \beta_k$
Question 7.c :
On remarque que $\beta_k=\alpha_k-\alpha_{k+1}$
Donc $v_p(n!)=\displaystyle\sum_{k=1}^{+\infty} k (\alpha_k-\alpha_{k+1}) \\
=\displaystyle\sum_{k=1}^{+\infty} k \alpha_k-\displaystyle\sum_{k=1}^{+\infty} k \alpha_{k+1} \\
= \displaystyle\sum_{k=1}^{+\infty} k \alpha_k-\displaystyle\sum_{k=2}^{+\infty} (k-1) \alpha_{k} \\
= \alpha_1 +\displaystyle\sum_{k=2}^{+\infty} \alpha_k$
Finalement $\boxed{v_p(n!)=\displaystyle\sum_{k=1}^{+\infty} \alpha_k= \displaystyle\sum_{k=1}^{+\infty} E(\dfrac{n}{p^k} )}$