Forum de mathématiques - Bibm@th.net

bastien

Invité

pgcd et compagnie [Résolu]

Bonjour a tous !
Je suis un peu dans une impasse, et ce forum est quasiment ma dernière chance : un DM de spé math quasiment terminé, mais 2 questions sur lesquelles je bloque , je vous remercie d'avance pour les réponses qui j'éspère afflueront :

"On pose, pour n entier relatif ( n différent de 7 ) :  a=n + 7      et       b=3n - 4

1) Calculer 3a - b ; en déduire que le PGCD de a et b est un diviseur de 25

2) On pose d=PGCD(a;b). Montrer que d=PGCD(a;25)

3) En déduire les équivalences :
            a) [tex]d=25\,\Longleftrightarrow n\equiv 18\,\left[25\right][/tex]
            b) [tex]d=5\,\Longleftrightarrow \,n\equiv 3\,\left[5\right]\,et\,n\,ne\,congrue\,pas\,à\,18\,\left[25\right][/tex]

J'ai trouvé facilement pour le 1), mais pour les 2) et 3), j'ai déja cherché plus d'une heure, en vain...

Je m'en remet donc à vos réponses, et je le redit, merci d'avance pour les éventuelles réponses.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : pgcd et compagnie [Résolu]

Salut,

bah, une heure de recherche, ce n'est pas suffisant parfois. Je me souviens d'un sujet de concours à faire en 3 heures, et 95 % des candidats n'ont pas trouver la réponse à la première question (réponse nécessaire pour continuer le sujet) en moins de 3 heures.

Tout le travail que tu feras te sera très utile  pour aller plus vite ensuite, car tu auras déjà rencontré l'obstacle. Donc essaie de te déboutonner un peu plus pour y arriver.

Si tu as fait 1), le 2) vient tout de suite : puisque d=PGCD(a,b) divise 25, cela signifie que d divise a; d divise b et bien d divise aussi 25 => le PGCD(a,25) divise aussi 25.

Manifestement d=5 ou 25 (ou 1 !) !

Comment as tu répondu au 1) ?

Je reviens ..

PS : ah oui, on dit "n n'est pas congru à 18 modulo 25" à savoir que n ne peut pas s'écrire sous la forme 25p+18

Dernière modification par freddy (04-11-2009 09:10:39)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : pgcd et compagnie [Résolu]

Bonjour,

Si d est un diviseur de 25, on n'a pas trop le choix : 1 étant exclu, il ne nous reste que d = 25 ou d = 5.
5 est donc la plus petite valeur possible.
Voyons voir si on peut aller jusqu'à 25...
a est un multiple de 5 donc [tex]\exists k\:\in\mathbb{N}^*\;/\; a = 5k[/tex]
b est un multiple de 5 donc [tex]\exists k'\:\in\mathbb{N}^*\;/\; b = 5k'[/tex]

On écrit donc :
[tex]\begin{cases}
n + 7 &= 5k\\3n - 4 &= 5k'[/tex]
A partir de là tu dois trouver une égalité (très semblable à celle que l'énoncé t'a suggéré d'utiliser pour arriver à 25) mettant en jeu k et k', montrant que leur pgcd est un diviseur de 5...

@+

[EDIT] Grillé par freddy... Hello, Boss !

bastien

Invité

Re : pgcd et compagnie [Résolu]

Eh bien a vrai dire, j'ai réussi le 2), mais le 3) je bloque toujours... J'ai pas trop bien compris comment tu voulais partir Yoshi =S Mais en tout cas, merci beaucoup à vous 2 pour l'aide que vous m'avez déja donné.

=> freddy => Eh bien pour le 1), j'ai bidouillé avec un corollaire du th. de Bézout qui dit que "l'équation ax+by=n admet des solutions (x;y) dans Z si et seulement si n est un multiple de D=PGCD(a;b)"

Pour le 2), j'ai mis que d=PGCD(a,b) <=> d divise a et b donc si d=PGCD(a,25) alors d divise a et 25 ( pour le "a" c'est bon, et pour le "25" c'est prouvé dans le 1) ) => donc d=PGCD(a,25) cqfd . Mais tout compte fait, je pense que cela ne sert qu'a démontrer que d est diviseur de a et 25, mais pas forcement que c'est le PLUS GRAND diviseur de ceux-ci. Le truc c'est que je pense qu'il y a le fait qu'on ai "a" dans les deux équations et que cela peut regler mon problème, mais j'en suis pas sur...

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : pgcd et compagnie [Résolu]

Re,

J'ai voulu dire que, à partir de
[tex]\begin{cases}n+7&=5k\\3n-4&=5k'[/tex]
je tire :
[tex]\begin{cases}n&=5k-7\\n&=\dfrac{5k'+4}{3}[/tex]

D'où :
[tex]5k-7=\dfrac{5k'+4}{3}[/tex]
[tex]3(5k-7)=5k'+4[/tex]
Je te laisse arriver à
[tex]3k-k'=5[/tex]
pgcd(k,k') = 5

Dans le 1) tu conclus seulement, ainsi que demandé par l'énoncé, que pgcd(a,b) est un diviseur de 25, pgcd = 25, c'est l'objet de la 2e question...

@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : pgcd et compagnie [Résolu]

Salute tutti,

pour le 1), je vois la réponse comme suit :

3a-b = 3dk-dk' = d(3k-k')=25 => d divise bien 25, 

avec a= dk et b=dk', sans passer par Bézout.

Du coup, le 3) vient tout seul :

3-1) si d= 25 => a=25k=n+7 => n+7 =0 mod(25) <=> n = -7 = 18 mod(25).
Je te laisse démontrer la réciproque.

3-2 ) si d=5 => a=5k=n+7 => n+7 = 0 mod(5) <=> n = -2 = 3 mod(5) (= signifie congruent à )
Là aussi, je te laisse prouver la réciproque.

Je t'ai donné le raisonnement qu'on attend de toi en Spé Maths au bac et au delà, yoshi t'a donné une autre piste de raisonnement.

Avec deux soutiens pareils, tu ne crains plus rien !

[EDIT] Salut camarade yoshi !

Dernière modification par freddy (05-11-2009 10:57:36)

bastien

Invité

Re : pgcd et compagnie [Résolu]

Re, et merci encore pour toutes ces nouvelles réponses. J'aurai juste une dernière question, est-ce que mon raisonnement pour le 2) est OK ? Ou faut-il y rajouter un petit truc, ou même le changer tout entier ?... Merci d'avance, vous êtes vraiment super (et super rapides^^) tous les 2 !!

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : pgcd et compagnie [Résolu]

Salut,

Je suis d'accord avec ta propre conclusion pour le 2) pour moi, tu n'as effectivement prouvé de manière superfétatoire que d est un diviseur de 25, ce qui était déjà montré dans le 1).
Maintenant, tu disposes de 2 pistes de travail, celle de freddy et la mienne...

Pour le 3. Rien d'autre à proposer que freddy. Pour faire dans le simple, dire que 25 est un diviseur de a, c'est dire que [tex]a\;\equiv\; 0\;\;(25)[/tex] soit encore que [tex]n+7\;\equiv\; 0\;\;(25)[/tex]
Donc, il existe k tel que n+7 = 25k et n = 25k-7 = 25(k+1)+18 ce qui signifie bien que [tex]n\;\equiv\; 18\;\;(25)[/tex]

@+

B'soir freddy...

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : pgcd et compagnie [Résolu]

Re,

mon post #2 ci dessus te donne la réponse : d ne peut être égal qu'à 5 ou 25 et dans les deux cas, c'est bien le PGCD.

Vois tu bien pourquoi ?

bastien

Invité

Re : pgcd et compagnie [Résolu]

La réponse pour le 2) ? Si c'est ca, non je ne vois pas vraiment...

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : pgcd et compagnie [Résolu]

Re,

La question posée dans la question 2. est très exactement : Montrer que d=PGCD(a;25).

Freddy te renvoie à son message #2 où il dit

Manifestement d = 5 ou 25

parce que le pgcd de a et 25 est forcément déjà un diviseur de 25 : d'où le " 5 ou 25"

@+