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
[+]

 #26 - 18-08-2015 18:47:12

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

Ue somme de 2 carrés

L'énoncé était, rappelons le:

7901 est premier et est égal à 85²+26².
Trouver le plus petit entier x tel que:
7901*x=1+4n², n étant entier naturel. A la main bien entendu.
Pour les plus courageux: prouver que x existe pour tout nombre premier impair somme de 2 carrés.

Solution rapide:
p=a²+b² dont on cherche un multiplicateur
q=c²+d² ce multiplicateur ! car
pq= (ac+bd)²+(ad-cb)² ou (ac-bd)²+(ad+cb)²=1²+(2n)²
Comme on cherche un pq=1+4n², et qu'on sait qu'il existe le couple (c,d) tel que ac-bd=1 mais aussi ac-bd=-1, car a et b sont premiers entre eux, il n'y a plus qu'à trouver (c,d).

Quand on a un couple a,b premiers entre eux, on sait que tous les restes de n*a modulo b, n<a, donneront b-1 restes différents, dont bien entendu 1 et -1 ( ou b-1). L'égalité n'intervient que pour a*b=b*a. (c,d) seront donc plus petits que (a,b), et par conséquent q aussi.

Cherchons (c,d)
85c-26d=1
26(3c-d)+7c=1
26e+7c=1
7(3e+c)+5e=1
7f+5e=1
Une solution est e=3 et f=-2
3e+c=f
c=f-3e=-11 ou 15 modulo 26
e=3c-d
d=3c-e=-36 ou 49 modulo 85

Comme il faut q impair, on prend le couple (-11,-36) car la somme des carrés est impaire.
x=q=11²+36²=1417 et n=1673.

1+4n²=0 modulo 7901 pour n=1417 et aussi pour tout n=7901k + ou-1417.

Etant donné qu'on a cherché le seul couple (c,d) <(a,b) tel que ac-bd=1 et avec c²+d² impair, c'est le plus petit.

Cette méthode généralise de facto l'existence de x( ou q) pour tout p somme de 2 carrés.

Cette question a été inspirée par l'étude des nombres de la forme 1+4n². On sait maintenant que tous les nombres premiers de la forme 4n+1 divisent les nombres 1+4n².  Ce sont d'ailleurs les seuls.

Bravo à Promath et Papiauche qui ont su résoudre en totalité ou en partie cet épineux problème d'arithmétique, avec tous les deux une démarche presque identique et plutôt sophistiquée. Merci aux autres intervenants qui ont vite trouvé la solution particulière et aussi aux autres qui ont cherché.

#0 Pub

 #27 - 18-08-2015 19:25:26

Promath-
Elite de Prise2Tete
Enigmes résolues : 18
Messages : 1416
Lieu: Au fond de l'univers

Une sommme de 2 carrés

J'étais parti sur ce que tu as fait au début sans trouver, je n'aurais jamais pensé à ça!!


Un promath- actif dans un forum actif

 #28 - 18-08-2015 20:22:34

papiauche
Sa Sainteté
Enigmes résolues : 49
Messages : 2131

Une somme de carrés

Très bien, très bien, très bien smile

Pas mécontent d'avoir vu pas mal de choses:
- la question de la parité,
- l'utilisation de l'identité de Bezout, nettement plus performante avec a et b qu'avec a (ou b) et p.
- le choix du multiplicateur avec ma deuxième solution.

Sur la démo prouvant qu'on a bien obtenu le plus petit, je comprends le principe général, mais il faut que je métabolise. big_smile

Une question me vient:

nodgim a écrit:

Cette méthode généralise de facto l'existence de x( ou q) pour tout p somme de 2 carrés.

Si un nombre premier est somme de deux carrés, les nombres sont nécessairement premiers entre eux.

La formulation de la généralisation porte-t-elle sur:

un nombre premier somme de deux carrés,
ou celle (apparemment moins restrictive) d'un nombre somme de deux carrés de nombres premiers entre eux.

De mon point de vue, c'est la seconde:
7801 n'est pas premier = 13*269

7801= =85^2+24^2

Avec la méthode de résolution:

q = 2285
n = 2111

P.S. Je ne voyais pas comment utiliser le fait que p était premier dans ma seconde approche.


"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde

 #29 - 19-08-2015 08:09:29

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

Une somme dee 2 carrés

ça marche pour tout nombre somme de a²+b² premiers entre eux, puisqu'il faut bien trouver une solution à ac-bd=1. Et d'ailleurs, si pq=1+4n², q qui est aussi somme de 2 carrés n'est pas non plus nécéssairement premier.

 

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 : Pif, Paf et ?

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