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 : 3802

ogcd

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.

  • |
  • Répondre

#0 Pub

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

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

pgcf

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 : 3802

Pcgd

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 : 3802

pgcs

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 : 3802

pfcd

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 (numériquement) à la petite énigme suivante : 

Si il y a 63 pommes et que vous en prenez 23, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
P2T
01-11-2011 Enigmes Mathématiques
28-12-2018 Enigmes Mathématiques
P2T
Enigme de probas par bilbo128
11-10-2015 Enigmes Mathématiques
26-08-2015 Enigmes Mathématiques
P2T
Vingt billes par nodgim
31-05-2015 Enigmes Mathématiques
P2T
Gâteau 47 par Vasimolo
03-12-2011 Enigmes Mathématiques
P2T
Gâteau 149 par Vasimolo
15-01-2018 Enigmes Mathématiques
P2T
19-04-2012 Enigmes Mathématiques
P2T
08-08-2011 Enigmes Mathématiques

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