A^n −1 divise a^m −1⇔n divise m avec a⩾2, m,n⩾1 entiers).

[Thomas91]

Bonjour, j'aimerais démontrer celà

a^n −1 divise a^m −1⇔n divise m avec a⩾2, m,n⩾1 entiers).

J'ai essayé de développer a^n-1=(a-1)(1+a+a^2+...+a^n-2+a^n-1)

Quelqu'un aurait une piste svp?

[zygomatique]

salut

[Thomas91]

on a n divise m donc m=nk

a^m -1 = a^nk -1 = (a-1)(1+a+a^2+...+a^nk-2+a^nk-1)

[Thomas91]

Que faire ensuite?

[zygomatique]

l'idée est là ... mais as-tu lu ce que j'ai écrit ?

[Thomas91]

Oui, du coup on a a^nk - 1 / a^n -1 appartient à Z donc a^n -1 divise a^nk - 1 = a^m -1) ?

Mais ça me semble pas évident que le quotient des deux est un entier relatif..

[zygomatique]

quelle est le problème ?

[Thomas91]

Ah je comprend, il fallait chercher à mettre a^n -1 en facteur pour montrer la divisibilité, c'est bien ça? Merci

[Ben314]

Salut,
Attention tout de même à ce que l'indication de zygomatique ne permet de montrer qu'une implication (laquelle ?) alors que ce qu'on te demande de montrer, c'est une équivalence.

[Thomas91]

Salut ben,

n divise m implique a^n-1 divise a^m-1 je suppose

Alors comment montrer l'autre implication?

[Ben314]

Personnellement, je ferais plus ou moins les deux équivalences en même temps en cherchant à évaluer le reste de la division de par sans faire d'hypothèses particulières concernant et .

Essaye sur quelques exemples (avec a=2 ou 3 et n et m moyennement grand) pour voir si tu arive à conjecturer le résultat. Si tu y arrive, ce n'est pas très difficile de le démontrer par récurrence, mais le problème des preuves par récurrence, c'est qu'il faut d'abord savoir quel est le résultat du bidule avant d'attaquer la démonstration...

[Thomas91]

Le reste est un entier relatif : a+a^n+a^2n+...+(a^n)^k-1
Mais j'ai ça en supposant à la base m=nq avec q un entier relatif ..

Sans faire d'hypothèse j'ai (a-1)(1+a+a^2+...+a^m-1) / (a-1)(1+a+a^2+...+a^n-1)
mais avec ça je ne peux pas dire qu'il s'agit d'un entier relatif

[Thomas91]

Je vais tenter la récurrence alors, mais je ne comprend pas, je fais une récurrence sur n? sur m? les deux?

[Pseuda]

Bonsoir,

Une autre piste : n divise m m =nq



Pour la réciproque (qui peut faire les 2), poser m = nq + r, on obtient , d'où ?

[Ben314]

Ce que j'espérait que tu ferais (mais visiblement c'est raté...), c'est de prendre par exemple a=2, n=3 donc puis de faire un petit tableau donnant, en fonction de m, les restes de la division de par 7 :

qui permet de conjecturer que le reste de la division de par , c'est où est le reste de la division de par .

Et une fois cette propriété conjecturée en faisant quelques essais, il est assez facile de la démontrer, soit par un calcul direct, soit par récurrence sur .

P.S. : je trouve un peu dommage que Pseuda t'ai donné directement la solution plutôt que de t'inciter à faire des "essais" pour la trouver toi même...

[Thomas91]

J'avais pas du tout pensé aux mod, j'essaie demain!

[Pseuda]

Personnellement, je ferais plus ou moins les deux équivalences en même temps en cherchant à évaluer le reste de la division de par sans faire d'hypothèses particulières concernant et .

Essaye sur quelques exemples (avec a=2 ou 3 et n et m moyennement grand) pour voir si tu arive à conjecturer le résultat. Si tu y arrive, ce n'est pas très difficile de le démontrer par récurrence, mais le problème des preuves par récurrence, c'est qu'il faut d'abord savoir quel est le résultat du bidule avant d'attaquer la démonstration...

Bonjour,

Désolée, mais je ne vois pas en quoi ta solution, basée sur une démonstration par récurrence (sur n ? sur m ? pour reprendre ce que dit Thomas91), incite à utiliser les modulo.

C'est ta suggestion de démonstration par récurrence, qui à mon avis, embarque sur une mauvaise piste, ou complique, qui m'a fait "donner" la solution.

[Ben314]

A mon sens, que tu démontre le résultat directement ou par récurrence (évidement une récurrence sur vu tableau ci dessus), ce n'est pas vraiment ça le problème.
Le problème, c'est d'arriver à "intuiter" a un moment donné qu'il faut effectuer la division euclidienne de m par n.

Ensuite, je voudrais bien que tu m'explique en quoi "ça complique" de faire une bête preuve par récurrence :
Si alors

et on termine en distinguant le cas et

Et si j'étais parti plutôt sur le principe de la récurrence, c'est que dans un cours d'arithmétique on peut parfaitement poser ce type d'exo. avant d'avoir vu la notion de congruence et que l'énoncé étant formulé en terme de divisibilité et pas de congruence, j'étais pas persuadé que la solution attendue soit celle avec des congruences.

[Pseuda]

Bonjour,

La divisibilité et la division euclidienne sont vues en 3ème, les congruences en TeS spé maths, donc à mon avis pour ce problème posé en supérieur, les congruences ont forcément déjà été vues...

Enfin la démo avec les congruences est quand même plus simple : il faut 1 ou 2 lignes, et plus facilement compréhensible, tandis que celle avec la récurrence est plus longue, on doit distinguer 2 cas pour le reste, elle n'est pas vraiment adaptée à ce problème, bref.

[Ben314]

Ah bon...
Ben on doit pas avoir le même public : dans le groupe de L1 math/physique dont je sort (qui, normalement ont eu le Bac...), il y en a une bonne moitié qui ont pas pris "spé-math" en terminale et qui donc ne connaissent pas les congruences mais sont capables (du moins je l'espère...) de prouver un tel résultat (... par récurrence bien sûr).