Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 31-03-2018 08:26:34

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3427

gPcd

Bonjour à tous.

Sauriez vous trouver à la main le plus grand PGCD possible de :

(60 000 013 n + 60 000 049) et (60 000 023 n + 60 000 047)
(n entier naturel) ? 

Sans même la moindre calculette....


Bon courage.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 31-03-2018 16:02:05

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 677

gcd

Salut nodgim,

  PGCD(60 000 013 n + 60 000 049 ; 60 000 023 n + 60 000 047)
= PGCD(60 000 013 n + 60 000 049 ; 10 n - 2)
= PGCD(3 n + 72 000 051 ; 10 n - 2)
= PGCD(360 000 253 n + 1 ; 10 n - 2)
= PGCD(360 000 253 n + 1 ; 720 000 516 n)

Un facteur premier de n ne peut être contenu dans (360 000 253 n + 1), donc le PGCD maximal potentiel est 720 000 516.

Un petit coup d'algorithme d'Euclide étendu pour résoudre 720 000 516 k + 360 000 253 n = 1, et on trouve qu'en prenant n = 216 000 155, le PGCD est précisément de 720 000 516, c'est donc bien la valeur maximale. Tous ces calculs peuvent se faire à la main.

Au passage merci de continuer à nourrir ce site smile

 #3 - 31-03-2018 16:46:21

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3427

pfcd

Ben oui, faut bien le faire vivre un peu ce site.....
Tout le problème est de proposer des énigmes pas trop faciles, pas trop difficiles, pas trop mathématiques,....

Pour en revenir à l'énigme, oui c'est bien cela, Ebichu. Je voulais qu'on propose un truc plus court, tu n'en as pas eu besoin, malgré les grands nombres en jeu.

Et si je demandais, en généralité, le PGCD de (a*n + b) et (c*n+d), que répondrais tu ?

 #4 - 31-03-2018 16:50:58

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3427

Pggcd

En fait ( @ tous ) l'idée de la question est de s'affranchir carrément de l'algorithme d"Euclide, pas toujours facile à manipuler.

Et ici on peut très bien s'en passer...

 #5 - 03-04-2018 17:53:56

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3427

Pgc

Et bien voila, le temps est écoulé.

J'avais promis une réponse plus simple pour la recherche du PGCD dans ce genre de figure. La voici donc :

Si P = pgcd

a * n + b = k* P
c * n + d = j * P

n = ( ( k * P ) - b ) / a = ( ( j * P ) - d ) / c

c * k * P - b * c = a * j * P - a * d
P ( c * k - a * j ) = b * c  - a * d

P existe et est max quand c * k - a * j = +- 1 , ce qui est toujours possible si a et c sont premiers entre eux. Dans ce cas P = I  b * c - a * d  I 

C'est donc tout de même plus court que l'algorithme d'Euclide.

Remarque : Si a et c ont un facteur commun, P = 1 sauf si ce facteur commun est aussi dans b et d.


Peu de participants à cette petite énigme pourtant pas bien méchante. Trop scolaire ?

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete