Arithmétique : divisibilité
dans Arithmétique
Bonsoir,
Je travaille l'arithmétique et je bute sur cet exercice.
L'énoncé a le mérite d'être succinct :
Pour tout $n$ de $\N-\{0\,;\,1\}$, montrer que $2^n | 5^{2^{n-2}}-1$ et $2^{n+1} \not| 5^{2^{n-2}}-1$.
J'ai bien tenté de factoriser $5^{2^{n-2}}-1$ mais en vain...
Je voudrais juste une piste pour me débloquer.
Merci d'avance.
Je travaille l'arithmétique et je bute sur cet exercice.
L'énoncé a le mérite d'être succinct :
Pour tout $n$ de $\N-\{0\,;\,1\}$, montrer que $2^n | 5^{2^{n-2}}-1$ et $2^{n+1} \not| 5^{2^{n-2}}-1$.
J'ai bien tenté de factoriser $5^{2^{n-2}}-1$ mais en vain...
Je voudrais juste une piste pour me débloquer.
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$5^{2^{n-2}}=k2^n +1$
?
a+
$\phi(2^{n-1})=2^{n-1}(1-\frac{1}{2})=2^{n-2}$
$2^{n-1}$ et 5 sont premiers entre eux
theoreme de Fermat-Euler:
$5^{2^{n-2}}=1}$ modulo $2^{n-1}$
(sauf erreur)
On peut utiliser l'egalité:
x²-1=(x+1)(x-1)
si x est entier et impair x+1 et x-1 ont pour pgcd 2
On applique à x=5^(2^(n-3)) et on applique le theoreme de Fermat Euler
ou sinon on peut en effet trouver une factorisation de $5^{2^{n-2}}$ qui repose sur l'identite polynomiale $$\sum_{i=0}^{2^N-1}X^k=\prod_{i=0}^{N-1}(1+X^{2^i})$$.
En regardant alors la divisibilite par $4$ de chacun des facteurs du produit on a la reponse...
Sauf erreur :
Z/2^nZ est un corps muni de la multiplication et de l'addition
x²-1=(x+1)(x-1) dans ce corps signifie que ou bien x=+1 ou bien x=-1
dans ce corps.
Ce qui veut dire que si x²=1 alors x=1 ou -1 dans ce corps
Nous savons que 5^(2^(n-1))=1 dans z/2^nZ
d'après le th de Fermat Euler
Nous savons aussi que 5^(2^(n-2))-1 est divisible par 2^(n-1)
toujours d'après le théorème de Fermat Euler.
5^(2^(n-2))=1 ou -1 dans Z/2^n car son carré est 5^(2^(n-1))
Il reste à voir pourquoi ça ne peut être -1
Si c'était le cas ça signifierait que
5^(2^(n-2))+1 est divisible par 2^(n-1)
Mais c'est impossible car :
5^(2^(n-2))-1 est divisible par 2^(n-1)
et que
5^(2^(n-2))-1 et
5^(2^(n-2))+1
ont pour pgcd 2
(il faut supposer n assez grand)
Ce qui veut dire que si x^2=1 alors x=1 ou -1 dans ce corps
Donc a priori on ne sait pas si x^2=1 implique x=1 ou x=-1
Par récurrence:
On considere la relation à prouver pour tout n (suffisemment grand):
P(n)= " $5^{2^{n-2}}-1$ est divisible par $2^n$ mais pas par $2^{n+1}$"
Pour n=3
on a n-2=1
$5^2-1=24=3.8$ est divisible par $2^3$ mais pas par $2^4$
On suppose que pour n>3, P(n) c'est vraie.
(n+1)-2=n-1
$5^{2^{n-1}}-1=(5^{2^{n-2}}-1)(5^{2^{n-2}}+1)$
D'après l'hypothèse de récurrence
$5^{2^{n-2}}-1$ est divisible par $2^n$ mais pas par $2^{n+1}$
Comme deja mentionné plusieurs fois:
si x est impair x+1 et x-1 ont pour pgcd 2
Donc $5^{2^{n-2}}+1$ est divisible par 2 mais pas par 4
Ainsi:
$5^{2^{n-1}}-1$ est divisible par $2^{n+1}$ mais pas par $2^{n+2}$
Donc P(n+1) est vraie et la relation est prouvée pour tout n>=3
@ trolleybus : je n'ai pas encore abordé la fonction $\phi$, c'est la fonction indicatrice d'Euler ? Je vais me pencher sur ta récurrence...
disons que N=3. A gauche, on a les puissances
0, 1, 2, 3, 4, 5, 6, 7.
de X. A droite, on trouve
000, 001, 010, 011, 100, 101, 110, 111.
Cordialment
@ trolleybus : j'ai bien suivi ta récurrence, cela me convient. Par contre, peux-tu me proposer une preuve du fait que si $x$ est impair, alors $\text{pgcd}(x-1;x+1)=2$.
Je propose ceci, si vous avez plus simple ou plus clair cela m'intéresse !
Soit $x$ un entier naturel impair. $x-1$ et $x+1$ sont pairs donc $\text{pgcd}(x-1;x+1) \geq 2$. Il reste à montrer qu'ils ne sont pas tous deux divisibles par 4.
Supposons que $4 | x-1$. On a : $x-1 \equiv 0 \;[4]$, d'où $x+1 \equiv 2 \;[4]$ donc $4 \not| x+1$.
Supposons que $4 | x+1$. On a : $x+1 \equiv 0 \;[4]$, d'où $x-1 \equiv 2 \;[4]$ donc $4 \not| x-1$.
On en tire que $\text{pgcd}(x-1;x+1) = 2$.
oui tu peux prouver cette identite polynomiale simplement par recurrence.
Mais tu peux aussi constater qu'elle provient de l'existence et l'unicite d'ecriture des entiers en base $2$. (en regardant explicitement sur des petits $N$ ca vient naturellement).
<BR>
<BR>Voici quelques details supplémentaires:
<BR>
<BR>on constate qu'on peut representer un naturel <SPAN CLASS="MATH"><IMG WIDTH="40" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/11/14/101396/cv/img1.png" ALT="$ <= 7$"></SPAN> par trois bits. Le premier bit represente la valeur 1, le deuxieme, la valeur 2, et le troisieme, la valeur 4.
<BR>
<BR>Regardons en suite le produit a droite:
<BR>
<BR><SPAN CLASS="MATH"><IMG WIDTH="180" HEIGHT="34" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/11/14/101396/cv/img2.png" ALT="$ (1 + X) (1 + X^2) (1 + X^4)$"></SPAN>.
<BR>
<BR>On voit que <SPAN CLASS="MATH"><IMG WIDTH="57" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/11/14/101396/cv/img3.png" ALT="$ (1 + X)$"></SPAN> represente le premier bit, <SPAN CLASS="MATH"><IMG WIDTH="64" HEIGHT="34" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/11/14/101396/cv/img4.png" ALT="$ (1 + X^2)$"></SPAN> le deuxieme, et <SPAN CLASS="MATH"><IMG WIDTH="64" HEIGHT="34" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/11/14/101396/cv/img5.png" ALT="$ (1 + X^4)$"></SPAN> le troisieme.
<BR>
<BR>Par exemple, on obtient la puissance X^5 de X en prenant le deuxieme terme de <SPAN CLASS="MATH"><IMG WIDTH="57" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/11/14/101396/cv/img3.png" ALT="$ (1 + X)$"></SPAN>, le premier de <SPAN CLASS="MATH"><IMG WIDTH="64" HEIGHT="34" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/11/14/101396/cv/img4.png" ALT="$ (1 + X^2)$"></SPAN> et le deuxieme de <SPAN CLASS="MATH"><IMG WIDTH="64" HEIGHT="34" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/11/14/101396/cv/img5.png" ALT="$ (1 + X^4)$"></SPAN>, parce que <SPAN CLASS="MATH"><IMG WIDTH="76" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/11/14/101396/cv/img6.png" ALT="$ 5 = (101)_2$"></SPAN>.
<BR>
<BR>Cordialment<BR><BR><BR>
si x est impair c'est 2
si d divise x+1 et x-1 il divise leur difference c'est à dire: (x+1)-(x-1)=2
1 et 2 sont les seuls diviseurs de 2
(Le pgcd de deux nombre est un diviseur de ces nombres)
dans le cas x impair, x-1 et x+1 sont pairs c'est à dire divisibles par 2
<BR>J'avais en son temps proposé cette autre démonstration par récurrence :
<BR><a href=" http://www.les-mathematiques.net/phorum/read.php?f=2&i=46869&t=46825#reply_46869"> http://www.les-mathematiques.net/phorum/read.php?f=2&i=46869&t=46825#reply_46869</a>
<BR>
<BR>Alain<BR>
<BR>J'avais en son temps proposé cette autre démonstration par récurrence :
<BR><a href=" http://www.les-mathematiques.net/phorum/read.php?f=2&i=46869&t=46825#reply_46869"> http://www.les-mathematiques.net/phorum/read.php?f=2&i=46869&t=46825#reply_46869</a>
<BR>
<BR>Alain<BR>
@ Marko Riedel : merci également pour tes précisions, je vais essayer de trouver un cours présentant quelques rappels de numération en base 2
C'est drôle cette impression de parler dans le vide ;-)
L'histoire de la récurrence je l'ai proposé en première réponse (pour une fois !).
De manière très brève, certes, puisque je cite (Bati) :
"Je voudrais juste une piste pour me débloquer."
Bon c'est pas très grâve, je ne suis pas vexé !
a+
Bon c'est pas très grâve, je ne suis pas vexé !
............................................................................................................
tu as parfaitement raison, mais rassure toi ce n'était pas dans le vide car ils se sont tous inspiré de ta réponse..c'est trés bien.
A+
C'était l'idée la plus naturelle, en effet, et elle fonctionne.
Mais il fallait tout de même se farcir les details:
"Ya qua, faut que" ca marche seulement pour se faire (re)élire
quand on est politicien.
(oui je sais, il ne s'agissait que de donner des indications)
(ca me rappelle un assistant que j avais en td de calcul integral qui aimait brasser du vent et qui etait avare (trop paresseux?, indigne de lui?,incompetent?) pour donner les details d'un calcul, de la résolution d'un exercice.)
Cet exercice n'était pas si difficile après tout, puisqu'il ne demande que peu de connaissance en algebre/arithmétique.
@trolleybus : Moi j'ai bien aimé ta solution avec la fonction d'Euler.
Sinon je tiens à préciser que je ne suis pas paresseux ;-). Loin de la !
C'est mon côté "prof" qui est ressorti : Je passe souvent dans les rangs et la meilleure aide qu'on peut donner à un élève bloqué, c'est de lui en dire le moins possible.
Voilà pourquoi mon intervention était brève. Loin de moi l'idée d'éviter de rentrer dans les détails. La question de Bati aurait était : "Je suis paumé j'n'y comprend rien. Pouvez-vous me donner une solution détaillée", alors j'aurais détaillé davantage (mais sans tout dire !).
Voilà c'était juste pour dire que je ne suis politicien ;-)
a+
Au plaisir de te relire ;-)
Oui je comprends.
Lorsqu'un probleme est posé sur le forum et que je sais que je peux le resoudre , je me prete au jeu et j'en oublie un peu la demande initiale.
Apres tout, libre à celui qui a posé la question de recopier la solution telle quelle (qui peut comporter des erreurs, j 'ai ecrit beaucoup de betises dans ce fil de discussion, donc cela oblige celui qui l a recopie à être vigilant et avoir une lecture critique) ou bien de tenter de rediger sa propre solution (ce qui serait sans doute plus profitable)
@trolleybus
>Lorsqu'un probleme est posé sur le forum et que je sais que je peux le resoudre , je me prete au jeu et j'en oublie un peu la demande initiale.
Ce qui part d'un bon sentiment et d'un bon esprit !
Bon je retourne au foot...
a+
Je vous rappelle l'énoncé de cet exercice :
Pour tout $n$ de $\N-\{0\,;\,1\}$, montrer que $2^n | 5^{2^{n-2}}-1$ et $2^{n+1} \not| 5^{2^{n-2}}-1$.
J'ai encore besoin d'aide pour cet exercice. Je l'ai traité en faisant une récurrence directe, pas de souci.
Je souhaite le faire d'une autre façon, en m'appuyant sur l'identité polynomiale proposée par Ninoun, à savoir :
$$\forall N \in \N^{*}, \quad \sum_{k=0}^{2^N-1}X^k=\prod_{k=0}^{N-1}(1+X^{2^k}).$$
J'ai réussi à prouver ce résultat par récurrence. J'ai ensuite posé $N=n-2$ et $X=5$ pour aboutir à :
$$\forall n \in \N -\{0;1;2\}, \quad 5^{2^{n-2}}-1=4\prod_{k=0}^{n-3}(1+5^{2^k}).$$
J'ai remarqué que $1+5^{2^k}$ est pair et congru à 2 modulo 4 mais je n'arrive pas à conclure !
Merci de votre aide.
J'imagine que c'est ça.
Quant à la structure du groupe $(\Z/_{2^{n}\Z},\times)$, cela ne me parle pas trop...
@ Ninoun : je n'ai pas bien compris le lien entre l'identité polynomiale que tu m'as proposée, en particulier le fait qu'elle provienne {\it "de l'existence et l'unicite d'ecriture des entiers en base . (en regardant explicitement sur des petits ca vient naturellement)."}
J'ai testé pour de petites valeurs de $N$, cela donne :
- $N=1$ : 1=1
- $N=2$ : $1+X+X^2+X^3=(1+X)(1+X^2)$
- $N=3$ : $1+X+X^2+X^3+ \ldots +X^7=(1+X)(1+X^2)(1+X^4)$.
J'ai des souvenirs de mes cours d'info sur l'écriture des nombres en binaire mais j'a du mal à faire le lien ici.
Dans le cas où $N=3$, Marko Riedel m'a précisé que le premier bit représente la valeur 1, le deuxieme la valeur 2, et le troisieme la valeur 4. Qu'entends-tu par là exactement ? Ce sont des valeurs de $X$ ?
J'ai bien compris que le premier facteur correspond au premier bit, le deuxieme facteur au second bit, etc. Par exemple, comment attribuer la valeur du 1er bit, 0 ou 1 ? Il faut poser une valeur pour $X$ ?
D'avance merci de m'éclairer...
ou $a_i$ vaut $0$ ou $1$ si tu choisisses de prendre $1$ ou $X^{2^i}$ dans le terme $(1+X^{2^i})$.
Je suis vraiment pas sur d'etre clair . Enfin la recurrence est plus rigoureuse, mais cette approche rend un peu plus naturelle cette formule.
J'ai un peu de mal à te suivre mais la journée a été hard, pourrais tu me donner un exemple ? Ton approche m'intéresse !
$1+x+x^2+...+x^7=(1+x)(1+x^2)(1+x^4)$
par exemple en base 2 : $5=1.2^0+0.2^1+1.2^2$.
Dans la somme $x^5$ provient du produit de $x$ dans $(1+x)$ $(a_0=1)$, $1$ dans $(1+x^2)$ ($a_1=0), $x^2$ dans $(1+x^2)$ $(a_2=1)$.
Plus Generalement, si $n=a_0+...+a_k.2^k+..$ alors $x^n$ dans la somme s'obtient en choisissant dans $(1+x^{2^k})$ (lorsqu'on developpe) $1$ ou $x^{2^k}$ selon que $a_k=0$ ou $a_k=1$.
J'espere etre un peu plus clair. Bon courage et bon repos pour ce soir.
par exemple en base 2 : $5=1.2^0+0.2^1+1.2^2$.
Dans la somme $x^5$ provient du produit de $x$ dans $(1+x)$ $(a_0=1)$, $1$ dans $(1+x^2)$ $(a_1=0)$, $x^2$ dans $(1+x^2)$ $(a_2=1)$.
Plus Generalement, si $n=a_0+...+a_k.2^k+..$ alors $x^n$ dans la somme s'obtient lorsqu'on developpe en choisissant dans $(1+x^{2^k})$ le terme $1$ ou $x^{2^k}$ selon que $a_k=0$ ou $a_k=1$.
J'espere etre un peu plus clair. Bon courage et bon repos pour ce soir.
Dans la somme $x^5$ provient du produit de $x$ dans $(1+x)$ $(a_0=1)$, $1$ dans $(1+x^2)$ $(a_1=0)$, $x^2$ dans $(1+x^2)$ $(a_2=1)$.
Plus Généralement, si $n=a_0+\ldots+a_k.2^k+\ldots $ alors $x^n$ dans la somme s'obtient lorsqu'on développe en choisissant dans $(1+x^{2^k})$ le terme $1$ ou $x^{2^k}$ selon que $a_k=0$ ou $a_k=1$.
J'espère être un peu plus clair. Bon courage et bon repos pour ce soir.