Problème déroutant

[inviteb7c1e946]

Salut à tous. J'ai un DS bientot de Spé et pour cela mon prof m'a dit de faire un exercice qui me parait impossible a faire à mon niveau
L'énoncé est : Soit deux entiers n et m tels que 0<m<n avec n=mq+r (r<o<b)
1) démontrer que (2^n)-1 congru à (2^r)-1 modulo ( (2^m)-1)
2) démontrer que (2^r)-1 est le reste dans la DE de (2^n)-1 par (2^m)-1
3) En écrivant l'algoritmhe d'euclide démontrer que pgcd((2^n)-1;(2^m)-1)= (2^pgcd(n;m))-1

Si quelqu'un pouvait m'aider à resoudre cette horreur ça serait vraiment cool
-----

[invite179e6258]

pour 1) tu dois montrer que 2^m-1 divise 2^n-1 - (2^r-1) = 2^n-2^r = 2^(mq+r)-2^r = 2^r(2^mq-1) = (2^m)^q - 1^q = ...

[inviteb7c1e946]

J'ai un peu du mal à bien comprendre le raisonnement :$. Par contre quand tu ecris par exemple (2^m)^q tu représente avec ^ le pgcd ou la puissance ?

[gg0]

Quand tu écris "(2^n)-1", tu représente avec ^ le pgcd ou la puissance ?

[A voir en vidéo sur Futura]

[inviteb7c1e946]

Bah moi la puissance mais jcrois que certains utilisent ^pour le pgcd

[gg0]

Si tu as utilisé une notation, ceux qui te répondent utilisent ta notation, ou bien te demandent ce que tu veux dire.

En tout cas tu as eu une réponse presque complète, tu devrais pouvoir finir.

[invitedcb1627c]

Bonjour:
bon pour le moment j'ai just essay avec la 1ére question


replace est tu va trouve :

donc

d'ou

avec


D'ou

[invitedcb1627c]

Pour la 2éme et la 3éme c'est evidant :
2)
on a d'apres la 1ére question
donc
tel que
alors

d'ou le resultat.

[gg0]

Bonjour Badrbouas91.

C'est un peu dommage de faire les exercices à la place de ceux qui ont besoin de réfléchir et de les faire : On n'apprend pas à marcher à un bébé en marchant devant lui : On lui apprend en lui donnant la main. C'est d'ailleurs l'habitude de ce forum. Voir http://forums.futura-sciences.com/ma...ces-forum.html

Cordialement.

[inviteb7c1e946]

Ah ok bon bah c'est assez ignoble comme truc merci les gars. J'espère que ça tombera pas ^^

[inviteaf1870ed]

Bonjour:
bon pour le moment j'ai just essay avec la 1ére question


replace est tu va trouve :

donc

d'ou

avec


D'ou

Ca me parait bien compliqué. Il faut plutôt partir de l'idée de Toothpick Charlie et reconnaître une formule assez connue

[gg0]

Ah ok bon bah c'est assez ignoble comme truc

Absolument pas, et Toothpick-charlie a quasiment donné la solution (il reste le terme suivant à écrire).

Il est vrai qu'un élève de prépa actuel en sait moins en calcul qu'un élève de première S d'il y a 20 ans, par exemple ne connaît pas l'identité remarquable :

Qui généralise a²-b² et (celle-ci est aussi souvent ignorée !) a³-b³.

Cordialement.

NB : Le calcul presque complet :

donc ...
2 lignes pour un exercice, c'est ignoble ?

[inviteaf1870ed]

gg0, tu me paraphrases...

[gg0]

Tout à fait Ericc !

J'ai simplement voulu rassembler en un seul message comment un élève de terminale S de 1990 faisait.

Cordialement.

[inviteaf1870ed]

Et les élèves de 1950 résolvaient des triangles en 4ème

[gg0]

Disons plutôt en troisième, car les relations métriques vues en quatrième étaient bien pauvres.
Mais à l'époque, peu d'élèves allaient en quatrième (entre 15 et 30%), la plupart s'arrêtaient au certificat d'études, certains même (cas vécu) au cm2 à 13 ans n'entraient pas dans la classe du "certif".

Cordialement.

[invite7c60dca1]

Tiens c'est étonnant, je me suis récemment penché sur les programmes de spécialité mathématiques (pour mon fils de terminale), et il ne me semble pas avoir vu des exercices de ce type et de ce niveau de difficulté.
Oui le niveau de l'école se détériore dramatiquement ; même dans les enseignements censés être les plus difficiles ...
Bref, c'est un autre sujet, mais je me pose alors la question de comment et d'en quelles circonstances avez vous reçut cet exercice ?

[inviteb7c1e946]

Je ne vois pas du tout comment de la derniere ecriture on montrer ce que l'on cherche. J'ai beau essayer mais je ne trouve pas

[gg0]

Relis l'énoncé et sa traductions par Toothpick-charlie.

Cordialement.

[inviteb7c1e946]

AAAAAAAAAH ok c'est bon j'ai enfin vu le truc

[invitecb373bbe]

Pour le point 2), il faut encore montrer que 2^r – 1 est strictement inférieur au diviseur et positif, c'est-à-dire 2^r – 1 < 2^m – 1.
C'est le cas puisque n=mq + r avec 0<= r < m.

[invitecb373bbe]

Pour la partie 3), on voit qu'il y a une analogie entre l'algorithme d'Euclide qui permet de trouver le pgcd(n; m) et l'algorithme d'Euclide qui permet de trouver le pgcd(2^n – 1; 2^m – 1). L'avant-dernier reste non nul de l'algorithme dans le second cas sera donc 2^(pgcd(n; m)) – 1, d'où la conclusion.