Arithmétique de L2

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour, j'ai commencé les cours d'arithmétique il y a peu et je dois démontrer une divisibilité entre deux membres et je n'y arrive pas . Voilà le problème :

Montrer par récurrence que, si a est un entier impaire, alors $2^{n+1}$ divise $a^{2^{n}}-1$

L'étape d'initialisation est simple, je vous montre ce que j'ai fais pour l'hérédité :

On suppose la propriété vraie, montrons qu'elle est vraie au rang n+1 :

$$2^{n+1}\mid a^{2^{n}}-1 \Leftrightarrow a^{2^{^n}} -1 = 2^{n+1} \times k$$
avec $k\in \mathbb Z$

soit :

$$2^{n+2} \mid a^{2^{n+1}}-1 \Leftrightarrow a^{2^{n+1}}-1 = 2^{n+1}\times k \times a^{2}$$

En faite j'ai l'impression de n'aboutir nulle part car je semble allez dans la mauvaise direction. Qu'est ce que le faite que a doit être impair apporte au problème ? J'ai penser à remplacer a par 2n+1 mais même problème … J'aimerai avoir quelques indications svp

PS : Désolé si j'ai mal écrit au niveau des équations c'est la première fois que j'écrit en mathJax.

Édité par Würtz

+0 -0

salut,

je ne vois pas comment tu obtiens ton $× a²$… comment exprimes‐tu $a^{2^{n+1}}$ en fonction de $a^{2^{n}}$ ? on en déduit facilement une relation entre les $a^{2^{\mathrm{truc}}} − 1$

[note qu’en général ce genre de problèmes semble plus facile à étudier avec des congruences :

$$ m \mathbin{|} a^{2^{n}} - 1 \Longleftrightarrow a^{2^{n}} \equiv_{m} 1 $$

ce qui te débarasse de la soustraction embêtante pour multiplier et élever à des puissances. ;-) bon ici ça n’aide pas beaucoup vu qu’il faut aussi augmenter $m$.]

Édité par Maëlan

écrire français sous Windows : fr-oss (azerty++) ou bépo (étudié pour le français) | <insérer un truc spirituel ici>

+0 -0

Pour répondre à cette question en particulier :

Qu'est ce que le faite que a doit être impair apporte au problème ?

ça sert au moment de l'initialisation. :) Par ailleurs, tu peux voir que si $a$ est pair, alors $a^{2^n} - 1$ est impair, donc ne risque pas d'être divisible par $2^{n+1}$ !

Sinon, tout comme Maëlan.

+0 -0

a est un entier impair. ;-)

Avec ce genre d'exercice, tu as deux manières d'aborder la chose : par récurrence ou avec les congruences et leurs propriétés. Certains prof au lycée te demande d'utiliser le raisonnement par récurrence même s'il s'agit de la méthode la moins rapide (ou si t'es pas en spé) :

Tu poses l'hypothèse de récurrence : Soit P un prédicat sur $\mathbb N$ avec $P(n) \Leftrightarrow a^{2^n}-1 = 2^n \times 2k \Leftrightarrow \exists k \in \mathbb Z, a^{2n} = 2^n \times 2k + 1$. En effet, on remarque que $2^{n+1} = 2^n \times 2$. On suppose P(n) vrai.

Quand tu montre l'hérédité de ta proposition, tu part de $a^{2^{n+1}} - 1$ et tu essayes de faire apparaître $a^{2n}$ et remplace le par $2^n \times 2k - 1$. Normalement, tu peux après dégager $a^{2^{n+1}} - 1 = 2^{n+2} \times$ [quelque chose].

Pour l'initialisation, tu regardes bien l'imparité de a.

Après tu parles de L2 math? Perso, ça me fait penser à un exo de L1 voire TS.

Edité pour abus de langage.

Édité par Ozmox

Si chaque jour tu n’a pas la sensation d’avoir appris quelque chose alors tu devrais te ressaisir au plus vite.

+0 -0
Staff

Après tu parles de L2 math? Perso, ça me fait penser à un exo de L1 voire TS.

Pour peu que tu fasses une L2 d'info.

Sinon l'arithmétique on en fait plus vraiment dans le système français de toute façon. À part l'identité de Bezout en terminale, j'en avais jamais fait avant le master.

+0 -0

Sinon l'arithmétique on en fait plus vraiment dans le système français de toute façon. À part l'identité de Bezout en terminale, j'en avais jamais fait avant le master.

Holosmos

Ah ouais, même pas en L1 (congruences dans Z, descente de fermat, …)?

Sinon, en TS si tu n'est pas en spé math tu ne fais pas vraiment d'arithmétique. Tu t'en approche au plus avec le raisonnement pas récurrence.

Édité par Ozmox

Si chaque jour tu n’a pas la sensation d’avoir appris quelque chose alors tu devrais te ressaisir au plus vite.

+0 -0
Staff

Bah après ça dépend ce qu'on appelle arithmétique. Si faire de la théorie des groupes ça compte comme, ça change ma réponse.

Mais sinon, nan, même pas ça. Les congruences dans $\mathbf{Z}$ on en faisait rien (à part peut-être montrer que $\sqrt 2$ était irrationnel).

+0 -0

Oui, c'est vrai que l'on peut étendre la définition de l'arithmétique à pleins de domaines en maths confondus. Je considère surtout l'arithmétique comme l'étude des nombres et de la numération.

Mais je n'étant qu'en TS, j'ai pas le bagage mathématique nécessaire pour en parler de manière concrète je pense. ^^

Si chaque jour tu n’a pas la sensation d’avoir appris quelque chose alors tu devrais te ressaisir au plus vite.

+0 -0

Je considère surtout l'arithmétique comme l'étude des nombres et de la numération.

À ce moment là ça commence dans les toutes petites classes …

Holosmos

Oui! :-D

Après, je pensais plutôt aux systèmes de numérations en différentes bases, par exemple.

Édité par Ozmox

Si chaque jour tu n’a pas la sensation d’avoir appris quelque chose alors tu devrais te ressaisir au plus vite.

+0 -0
Auteur du sujet

Désolé j'ai eu un problème avec mon ordinateur du coup j'ai du attendre d'aller à la fac pour vous répondre :'(

Merci Ozmox pour ta réponse qui m'a fortement aidé !

C'était juste un exercice de rappel sur la divisibilité , on a déjà enchaîner sur d'autres chapitres donc oui c'était pas vraiment de l'arithmétique de L2 :p

+0 -0

Yop, je déterre car l’OP ne semble pas s’être manifesté depuis quelques temps et j’ai rédigé une solution par récurrence. Je ne sais pas vraiment si elle est valide mais soit.

Soit $a$ un entier impair. Soit $P(n) \iff \exists k \in \mathbb Z, a^{2^n} - 1 = (2^{n+1})k$. Commençons par l’étape d’induction, supposons $P(n)$ vrai. Au rang suivant, nous pouvons écrire :

$a^{2^{n+1}} - 1 = (a^{2^n})^2 - 1 = ((2^{n+1})k + 1)^2 - 1 = (2^{2n+2})k^2 + (2^{n+2})k = 2^{n+1} [(2^{n+1})k^2 + 2k]$$(2^{n+1})k^2 + 2k$ est un relatif donc $P(n+1)$ est vrai, d’où $P(n) \implies P(n+1)$.

Pour l’initialisation, on prend n = 0. Cela nous indique que $a - 1$ est multiple de 2 et ceci pour $a$ impair. Dans le cas contraire, rejoindre le message de melepe. :-)

C’est édité.

Édité par Ozmox

Si chaque jour tu n’a pas la sensation d’avoir appris quelque chose alors tu devrais te ressaisir au plus vite.

+0 -0

Tu as un $-1$ qui devrait être un $+1$, et ça change la suite mais le raisonnement reste correct.

Je suis justement tombé sur cette propriété il y a un mois (je ne me souviens pas l’avoir vue ici). L’égalité demandée est une conséquence du petit théorème de Fermat, mais on peut renforcer un peu : $a^{2^n} \equiv 1 \mod 2^{n+2}$ (et là ce n’est plus une conséquence directe). On peut essayer de généraliser à $n+k$, je ne sais pas trop ce que ça donne.

Écoutez les suites de l’OEIS : http://oeis.org/play.html

+0 -0

Je propose d’écrire :

$a^{2^{n+1}} - 1 = (a^{2^n})^2 - 1 = ((a^{2^n}) - 1)((a^{2^n}) + 1)$.

Le premier facteur est divisible par $2^{n+1}$ par hypothèse de récurrence, le deuxième est divisible par $2$ car pair, d’où $a^{2^{n+1}} - 1$ divisible par $2^{n+2}$.

+0 -0

En effet, bien vu ! Par la même idée, tu peux montrer que $a^{2^n}$ est divisible par $2^{n+2}$, pas seulement $2^{n+1}$.

blo yhg

Pour que $a^{2^n} - 1$ soit divisible par $2^{n+2}$, il faut en plus imposer $n \geq 1$ ou $a \neq 3$, sinon l’initialisation ne marche pas.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte