Accélèrer l'algorithme d'Euclide (spé maths)

Bonjour , j'ai un exercice que je dois faire c'est de la spé maths et je n'y arrive vraiment pas malgres avoir lu et relu le cours mainte fois , voici l'énoncé en espérant avoir de l'aide merci :

a et b désignent deux nombres entiers naturels tel que a>b.La division euclidienne de a par b donne l'existence d'un unique couple (q;r) de nombres entiers naturels tel que a=bq+r avec 0<r<b et r=a-bq. On se propose de construire un nouvel algorithme qui permet d'obtenir le PGCD(a;b) plus rapidement que l'algorithme d'Euclide.
Dans la division de a par b,on nomme r le reste par défaut et r'=b(q+1)-a,le reste par excès.
Ainsi r+r'=b

a)Démonter que les diviseurs communs à a et b sont les mêmes que les diviseurs communs à a et r'.
b)En déduire un algorithme qui permet d’accélérer celui d’Euclide.
c)Avec c'est deux algorithmes,déterminer: PGCD(435,548
d)Démontrer qu'avec ce nouvel algorithme,chaque reste est inférieur ou égal à la moitié du précédent.
e)k désigne l'exposant de la plus haute puissance de 2 inférieure ou égale a b.Démontrer que le nombre d'étapes de l'algorithme est inférieur ou égal à k+1.

Je n'arrive même pas a faire le a) , ni la suite.Si quelqu'un pouvait m'aider,merci

Bonjour,
a) Si d est un diviseur commun à a et b, il divise b, donc il divise b(q+1).
Et puisqu'il divise également a, il ....

Mais il doit y avoir une erreur dans l'énoncé : la réciproque est fausse : si d divise a et r', il ne divise pas forcément b.
Je crois que l'énoncé correct est : les diviseurs communs à a et b sont les mêmes que ceux de r et r'.

Je ne comprends pas ton raisonnement pourquoi d divise alors b(q+1) ?

Parce que s'il divise b, il divise n'importe quel multiple de b.

{\rtf1\ansi\ansicpg1252
{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
{\colortbl;\red255\green255\blue255;\red255\green255\blue255;\red0\green0\blue0;}
\deftab720
\pard\pardeftab720\partightenfactor0

\f0\fs22 \cf0 \cb2 \expnd0\expndtw0\kerning0
\outl0\strokewidth0 \strokec3 $C\'est une d'e9monstration d\'un exercice$ }

Voici ce que j'ai fais , je le suis inspiré d'une démonstration de mon cour , et j'ai toujours du mal à comprendre ta logique

Comme je l'ai signalé, la seconde partie (réciproque) est fausse : regarde l'exemple donné.
Quant à la première, tu ne justifies pas :
Citation
Comme d | a et d | b alors d | r'= b(q+1) - a
C'est pour cela, puisque tu avais dit ne pas pouvoir commencer la a), que j'ai détaillé pourquoi d divise b(q+1).
Et puisqu'il divise aussi a, il divise b(q+1) - a = r'.
Il s'agit de ce que tu as fait en plus détaillé.

Bonjour Mathtous et firstchil974,

Comme le forum est calme, je regarde un peu.

Effectivement, comme tu le dis Mathtous, il y a une erreur dans la première question. Faute de frappe entre a et b ?

Il me semble que cette question devrait être :

Démonter que les diviseurs communs à a et b sont les mêmes que les diviseurs communs à b et r',

c'est à dire :

Démontrer que

$\tex{d(a,b)=d(b,r')$

Effectivement, en appliquant cette méthode , la recherche du PGCD est plus rapide qu'avec l'algorithme "normal".

firstchil974 donnera peut-être de nouvelles informations sur cet énoncé.

Bonjour Mtschoon, et bonne année.
Je pencherais plutôt pour D(a,b) = D(r,r').
En regardant quelques exemples, il semble que cela revienne au même, mais je n'en suis pas certain : je vais voir.
En outre, les questions sont ambiguës et mal posées : comment par exemple prouver qu'un "reste" est inférieur ou égal à la moitié du précédent si on ignore de quel reste il s'agit : reste par défaut ou reste par excès ?
En outre, je ne vois pas comment prouver que tel nouvel algo sera plus rapide que l'algo classique avant au moins d'avoir établi la dernière question.
On peut juste le constater sur l'exemple donné, ce qui ne prouve rien.

C'est pourquoi je pense qu'il me faudra proposer un algo à Firstchil974.

Merci et Bonne année à toi Mathtous !

Je viens de trouver l'énoncé sur le web (le monde est petit...)

http://u.jimdo.com/www20/o/sbe273f6bb7d2ef4e/download/m58d7e0a8a260082a/1415564662/TS+sp%C3%A9+Ex.+sur+le+PGCD+14-11-2013+bien.pdf

C'est l'énoncé n° 22 .
A la première question, l'énoncé propose de démontrer D(a,b) = D(b,r').

A la suite des énoncés, il y a les corrections des exercices , dont celle de celui là.
(vers la page 14 ou 15 , je n'ai pas noté exactement la page) .

Je n'ai pas consulté, donc j'ignore la qualité de la correction.

Bonne lecture et bonne réflexion, si tu as le temps ( et bonne journée ! )

J'ai regardé le corrigé : après avoir établi (c'est simple, Firstchil974 devrait pouvoir le faire sans aide) D(a,b) = D(b,r'), l'algo qu'ils proposent consiste à remplacer a par b et b par inf(r,r') (ou min(r,r') ce qui est la même chose).

Partant moi de D(a,b) = D(r,r'), je remplace aussi b par inf(r,r') mais je remplace a par sup(r,r') : on obtient la même chose.

Quant au fait que cela accélère l'algo classique, ils l'admettent.

Bonjour et bonne année à vous ! desole de vous répondre en retard mais je n'étais pas chez moi pendant les fêtes.
Alors j'ai pas compris , qu'elle est le bon énoncé de l'exercice au finale ?
La correction proposé est t-elle exactement la même ?

Bonsoir et bonne année à toi.

Ayant trouvé l'exercice 22 (voir lien) qui est le même, on peut déduire que la première question est : démontrer D(a,b) = D(b,r') , mais je te suggère de demander à ton professeur quel est le bon énoncé, vu qu'il y a visiblement une erreur.
C'est lui qui décide de l'énoncé...pas nous...

Evidemment, tu peux consulter la correction pour t'aider à répondre, mais seulement pour consulter. C'est toi qui dois faire l'exercice.

Bon travail .

D'accord merci beaucoup mtschoon.