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

pfcd

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

Pgcdd

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

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

gcd

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

ogcd

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 88 pommes et que vous en prenez 44, combien vous en avez ?

Sujets similaires

Sujet Date Forum
P2T
01-11-2011 Enigmes Mathématiques
24-04-2011 Enigmes Mathématiques
14-03-2010 Enigmes Mathématiques
P2T
Rapport de Sommes par Vasimolo
21-08-2015 Enigmes Mathématiques
P2T
Pavage savant par Clydevil
25-07-2011 Enigmes Mathématiques
P2T
Ranger des Livres par minifat
29-08-2007 Enigmes Mathématiques
P2T
Dés 7 par Vasimolo
13-07-2012 Enigmes Mathématiques
P2T
Qcm aux reponses inconnues par labossedesmaths
03-06-2011 Enigmes Mathématiques
P2T
Gâteau 85 par Vasimolo
13-12-2014 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