Application nombre de diviseurs d'un entier
dans Arithmétique
Bonsoir,
Je réfléchis à cet exercice :
On note $d \, : \, \N^{*} \rightarrow \N^{*}$ l'application qui, à chaque $n$ de $\N^{*}$, associe le nombre de diviseurs supérieurs ou égaux à $1$ de $n$.
1. Soit $(k,m) \in (\N^{*})^2$ tels que $n=km$. Montrer que : $$a^n-1=(a^k-1)\sum_{i=0}^{m-1} (a^k)^i.$$
2. Montrer que l'application $f\,:\, \N^{*} \rightarrow \N^{*} \; ; \; k \mapsto a^k-1$ est injective ($a \geq 2$).
3. En déduire : $$\forall a \in \N-\{0\,;\,1\},\;\forall n \in \N^{*}, \; d(a^n-1) \geq d(n).$$
J'ai réussi à faire les deux premières questions mais je n'arrive pas à conclure en faisant la 3.
D'avance merci.
Je réfléchis à cet exercice :
On note $d \, : \, \N^{*} \rightarrow \N^{*}$ l'application qui, à chaque $n$ de $\N^{*}$, associe le nombre de diviseurs supérieurs ou égaux à $1$ de $n$.
1. Soit $(k,m) \in (\N^{*})^2$ tels que $n=km$. Montrer que : $$a^n-1=(a^k-1)\sum_{i=0}^{m-1} (a^k)^i.$$
2. Montrer que l'application $f\,:\, \N^{*} \rightarrow \N^{*} \; ; \; k \mapsto a^k-1$ est injective ($a \geq 2$).
3. En déduire : $$\forall a \in \N-\{0\,;\,1\},\;\forall n \in \N^{*}, \; d(a^n-1) \geq d(n).$$
J'ai réussi à faire les deux premières questions mais je n'arrive pas à conclure en faisant la 3.
D'avance merci.
Réponses
-
Réfléchis un peu :
La première question met en évidence des diviseurs de $a^n -1$
La seconde question permet de les dénombrer. -
Tous les termes de la forme $a^k-1$ sont des diviseurs de $a^n-1$.
$f$ est injective donc l'ensemble formé des $a^k-1$ a un cardinal supérieur à celui formé des $k$ ? J'ai du mal avec les injections... -
C'est celà, sauf que tous les termes $a^k-1$ ne sont pas des diviseurs de $a^n-1$, il y a une condition sur $k$...
De plus quand $f$ est injective de $E$ dans $F$, c'est une bijection de $E$ dans $f(E)$, qui est contenu dans $F$, donc :
$$\text{Card}(E) \leq \text{Card}[f(E)] \leq \text{Card}(F)$$
Tu as encore des problèmes à règler avec le dénombrement. -
Merci pour tes précisions gb, en effet, j'avais oublié que si $k|n$, alors $a^k-1|a^n-1$. Qu'en est-il de la réciproque ?
J'ai en effet du mal avec le dénombrement, les quelques exercices sur lesquels j'ai réfléchi m'ont paru vraiment difficile, je posterai d'ailleurs à ce sujet bientôt. -
Pour ta réciproque, effectue la division euclidienne de $n$ par $k$... et vois
-
Merci Alain ;-)
La réciproque est : si $a^k-1 \mid a^n-1$, alors $k \mid n$.
Comment effectuer la division euclidienne de $n$ par $k$ ? On ne sait pas justement si $k \mid n$. Ca doit être tout bête mais la je vois pas -
Surprise : $n = km + r$ avec $0 \leq r \leq k-1$
Donc $a^r - 1 = a^{km}a^r - 1 = a^r(a^{km} - 1) + a^r - 1$... -
Merci gb pour ton aide mais j'ai vraiment trop de mal ce soir, tu dois me trouver nul !
Si je reprends ce que tu as fait, si $a^k-1 \mid a^n-1$, alors $a^k-1 \mid a^r(a^{km} - 1) + a^r - 1$. Le but étant de savoir si $r$ est nul... -
Voilà, et l'on a un exemple algèbrique de la méthode de la "fausse position" si utilisée en géométrie : tu vas te servir de la proposition dans le sens direct, établi à la première question, pour démontrer la réciproque !
Autrement dit $A \Rightarrow B$ sert à prouver $B \Rightarrow A$. -
Je n'ai pas le souvenir d'avoir déjà utilisé cette "fausse proposition". Je vais y réfléchir, merci encore une fois
-
Je ne vois pas trop, je m'appuie sur le fait que $\displaystyle a^n-1=(a^k-1)\sum_{i=0}^{m-1} (a^k)^i$ ?
Dans ce cas, on a $\displaystyle a^r(a^{km} - 1) + a^r-1=(a^k-1)\sum_{i=0}^{m-1} (a^k)^i$. -
La méthode est classique dans les théorèmes tels Ménélaüs :
Si les points $A'$, $B'$, $C'$ pris sur les côtés d'un triangle sont alignés, alors on a $P(A',B',C')$
Réciproquement, si on a $P(A',B',C')$, soit $C''$ le point en lequel la droite $A'B'$ intersecte le troisième côté ; les points $A'$, $B', $C''$ sont alignés, donc on a $P(A',B',C'')$. Enfin, de $P(A',B',C')$ et $P(A',B',C'')$, on déduit $C' = C''$ et l'alignement voulu.
Pour ton arithémtique, on utilise le sens direct pour dire que $a^k - 1$ divise $a^{km} -1$. S'il divise $a^n-1$, il divise aussi $a^r -1$, avec $k>r$ d'où un malaise. Mais non, c'est bien sûr, $r = 0$ et $k$ divise $n$. -
La méthode est classique dans les théorèmes tels Ménélaüs :
Si les points $A',\ B',\ C'$ pris sur les côtés d'un triangle sont alignés, alors on a $P(A',B',C')$
Réciproquement, si on a $P(A',B',C')$, soit $C''$ le point en lequel la droite $A'B'$ intersecte le troisième côté ; les points $A',\ B',\ C''$ sont alignés, donc on a $P(A',B',C'')$. Enfin, de $P(A',B',C')$ et $P(A',B',C'')$, on déduit $C' = C''$ et l'alignement voulu.
Pour ton arithmétique, on utilise le sens direct pour dire que $a^k - 1$ divise $a^{km} -1$. S'il divise $a^n-1$, il divise aussi $a^r -1$, avec $k>r$ d'où un malaise. Mais non, c'est bien sûr, $r = 0$ et $k$ divise $n$. -
$ a^n - 1 = a^{km}a^r - 1 = a^r(a^{km} - 1) + a^r - 1$
-
Merci gb, j'ai conclu cet exo en disant ceci. Si on note $E$ l'ensemble des diviseurs de $n$ et $F$ celui des diviseurs de $a^n-1$, $f$ réalise une bijection de $E$ dans $f(E) \subset F$. On en tire $Card(E) \leq Card(f(E)) \leq Card(F)$, soit $d(n) \leq d(a^n-1)$.
J'espère que c'est bien ca ? -
Tout à fait ça !
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres