Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Maths sup
Partager :

arithmétiques

Posté par
bousselham 05-01-08 à 12:36

salut:
soit x et y deux nombres entiers naturelles:
montrer que:
      pgcd((2^x-1),(2^y-1))=2^(pgcd(x,y))-1

Posté par
Binouze_Flip64re : arithmétiques 05-01-08 à 13:07

Bonjour ,

Réécrivons plus proprement

PGCD(2^{x}-1 , 2^{y}-1) = 2^{PGCD(x,y)} - 1 , plutôt ça non?

Posté par
Binouze_Flip64re : arithmétiques 05-01-08 à 15:19

Tu as besoin d'une question subsidiaire pour aboutir je pense car cet exercice est présenté un peu brutalement.

Notons d = PGCD(2x - 1, 2y - 1)

1) Soit x = qy + r la division euclidienne de x par y. Démontrer que 2^{x} = 2^{r} (2^{y} - 1) (ce n'est pas le signe "=" mais le symbole de congruences avec une barre en plus je ne savais pas comment l'écrire en latex..).

2) En déduire que d = PGCD(a^{r} - 1, a^{y} - 1) puis d = 2^{PGCD(x,y)} - 1

Posté par
bousselhamarithétiques 05-01-08 à 15:22

salut:
et si en montre la double division càd montrer que toutes les deux divisent entre eux .

Posté par
Binouze_Flip64re : arithmétiques 05-01-08 à 15:24

Je reprends dsl :

2^{x} = 2^{r} [2^{y} - 1] (ie 2x - 1 est congru à 2r modulo 2y - 1 !)

Posté par
Binouze_Flip64re : arithmétiques 05-01-08 à 15:33

Ah ok montrer la double division pour aboutir à l'égalité, mais là je doute que l'on aboutisse, à voir..

Posté par
bousselhamarithmétiques 05-01-08 à 15:35

salut:
je vien de crée un forum de maths et je veut que quelqu'un m'aide à enrichire on forum :  voila l'addresse.
www.xyzmaths.discutforum.com

Posté par
Binouze_Flip64re : arithmétiques 05-01-08 à 16:34

as-tu potassé ma marche à suivre? arrives-tu au bout? En tout cas cela marche

Posté par
Binouze_Flip64re : arithmétiques 05-01-08 à 19:15

Voici ma méthode : en fait je vais montrer que pour m,n de , PGCD(a^{n} - 1, a^{m} - 1) = a^{PGCD(n,m)} - 1

1)Soit n = qm + r la division euclidienne de n par m avec (q,r) un couple de ²

a^{n} - a^{r} = a^{qm + r} - a^{r} = a^{r}(a^{qm}-1) = a^{r}[(a^{m})^{q} - 1]

Or on sait que : \forall p \in \mathbb{R}, b^{p} - 1 = (b-1)(b^{p-1} + b^{p-2} + ...+1)

d'où a^{n} - a^{r} = a^{r}(a^{m}-1)((a^{m})^{q-1} + (a^{m})^{q-2} + ...+1)

Il existe donc un entier naturel q tel que : a^{n} - a^{r} = q(a^{m}-1)

On a donc que (a^{m}-1)|[a^{n} - a^{r}] et le résultat

2) D'après 1) on a : a^{n} - a^{r} = q(a^{m}-1) ie a^{n} = q(a^{m}-1) + a^{r}
d'où a^{n} - 1 = q(a^{m}-1) + (a^{r} - 1)  

On a donc : PGCD(a^{n} - 1, a^{m} - 1) = PGCD(q(a^{m}-1) + (a^{r} - 1), a^{m} - 1) = PGCD(a^{r} - 1, a^{m} - 1) d'après le lemme d'Euclide ( rappel pgcd(A,B) = pgcd (B, R) )

Puisque PGCD(a^{n} - 1, a^{m} - 1) = PGCD(a^{r} - 1, a^{m} - 1) , a^{r} - 1 est le dernier reste non nul de la division euclidienne de  an - 1 par am - 1 et donc :

PGCD(a^{n} - 1, a^{m} - 1) = a^{r} - 1 = a^{PGCD(m,n)} - 1

Sauf erreur

Posté par
bousselhamarihméiques 05-01-08 à 19:28

merçi:
  vous avez visiter le site que je 'es donner .www.xyzmaths.discutforum.com


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !