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 - 15-08-2015 09:50:05

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

yne somme de 2 carrés

Bonjour à tous,
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.

Bonne recherche

  • |
  • Répondre

#0 Pub

 #2 - 15-08-2015 11:37:50

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

une somme de 2 carréq

Tu veux bien dire 7901*x et non pas x à la 4ème ligne? Du coup ça fait 7901²*k, k impair?


Dans ce cas en posant x=7901k puis k=2l+1 j'aboutis à l pair donc l=2m , en simplifiant j'ai m= (n²-1506450)/62425801 ce qui me donne une équation modulaire, qui aboutit à n=29864107 pour m=14286799... Je n'ai pas mieux pour le moment hélas hmm


Un promath- actif dans un forum actif

 #3 - 15-08-2015 12:54:14

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

Unne somme de 2 carrés

Tu as raison Promath, je me suis embrouillé dans l'énoncé. J'ai corrigé.
Mille excuses.

 #4 - 15-08-2015 18:30:15

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

Une osmme de 2 carrés

Posant x=4m+1 on arrive à la résolution de l'équation diophantienne suivante: n²=7901m+1975

posant n=ak+b et m=ck²+dk+f

on a 7901c=a²
7901d=2ab
7901f+1975=b²

il en découle que 7901 divise 4c*1975 donc que c est multiple de 7901 et d de 2. Puis on met en évidence une nouvelle solution, après avoir posé c=7901g, qui donne que g est un carré parfait, pour prouver plus tard que 2g' divise d; ce qui amène, en posant g'= sqrt (g) que le couple n,m=d/2g',f est solution de l'équation. Il vient ensuite rapidement que c=7901, les autres valeurs suivent. Ce qui donne un n=1673 au minimum, amenant un x égal au minimum à 1417 smile


Edit: j'ai remarqué qu'on peut arriver à x congru à 1 modulo 4 rapidement aussi, et considérer un résidu négligeable après mais je ne sais pas comment faire sans machine du coup

Edit2: Je viens de me rendre compte que l'équation était soluble directement! Tant pis ça fonctionne aussi comme ça...


Un promath- actif dans un forum actif

 #5 - 15-08-2015 20:48:22

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

une sommr de 2 carrés

J'ai -presque- la preuve de l'existence de x mais pas encore trouvé la manière d'obtenir le plus petit hmm

1°) p= i^2+j^2
p étant impair, i et j sont nécessairement de parité opposée.
Pour la suite on choisira i pair (dans l'exemple i = 26) .

Par ailleurs, p ne divise pas i, sinon on aurait:
p= k^2*p^2+j^2 ce qui est impossible par simple encadrement.

2°) Comme i et p sont premiers entre eux, on peut appliquer l'identité de Bezout:

Il existe donc a et b entiers relatifs tels que:

a*i+b*p =1
a*i= 1-b*p

Avec b impair.

a^2*(i^2+j^2)=a^2*p=(1-b*p)^2+a^2*j^2

Il vient:

(a*j)^2 +1 = a^2*p+2*b*p-b^2p^2p^2

(a*j)^2 +1=p*(a^2+2*b-b^2*p)

Sans pouvoir établir la parité de a.

On a donc trouvé:

n= a*j/2
x= a^2+2*b-b^2*p


Sous réserve de la parité de a, qui est peut-être évidente.

Numériquement, sur l'exemple a=5166; b= 17
n= 5166*85/2= 219555
x= 24404201

Avec un tableur, pour les plus petites valeurs, je trouve
n= 1417
x= 1673

Je suis donc très loin de l'optimum tongue
Peut-être un jeu sur la parité de i...
Quoiqu'il en soit, si on doit passer par Bezout, à la main, ça n'est pas facile!


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

 #6 - 16-08-2015 08:58:17

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

Une omme de 2 carrés

@ Promath:
Si j'étais éditeur je dirais: la méthode est remarquable, car c'est par une série d'inductions ingénieuses que la solution apparait presque miraculeusement. Un délice pour les spécialistes !
Comme je ne suis pas éditeur, je dirais que c'est un peu capillotracté. Bien sûr il existe une méthode plus aérienne, et surtout, comme tu procèdes, la généralisation n'est pas accessible.

@ Papiauche:
Tu as eu un bon départ, malheureusement tu t'es perdu en cours de route. J'ai l'explication de cette perdition dans ta toute dernière phrase, car il existe bien une méthode facile pour résoudre cette équation.

Sinon, vous avez bien tous les deux trouvé le bon résultat, bravo !

Je donnerai un indice sur la méthode qui me semble être la plus courte si personne ne trouve.

 #7 - 16-08-2015 10:59:32

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

une somme de 2 catrés

Ça ressemble à du Fermat cette affaire smile

Je vais juste donner l'unique contre-exemple : 2=1²+1² est premier et je ne trouve pas de x et de n tels que 2x=1+4n² hmm

Vasimolo

 #8 - 16-08-2015 15:06:39

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3208
Lieu: Luxembourg

Une somme de 2 carrsé

A la main, c'est-à-dire en tapant sur le clavier big_smile, je trouve: x = 1417

On a l'égalité: 1417 x (85² + 26²) = 1 + 4 x 1673². Mais même en remarquant
que: 1417 = 13 x 109 et 1673 = 7 x 239, je ne vois aucune autre méthode sad.

 #9 - 16-08-2015 16:29:38

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

Une somme d e2 carrés

Merci Vasimolo pour ta remarque sur le x=2 qui n'est effectivement pas solution, et pour cause !
Fermat a peut être travaillé aussi sur cette partie là, je ne sais pas. Sinon, il y a un autre thèorème très célèbre en arithmétique qui est à utiliser de préférence.

Franky, c'est OK pour le résultat. Tu as le droit de te servir à la main de ton clavier à condition que ton ordi soit....hors tension.

 #10 - 16-08-2015 17:10:21

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

Un somme de 2 carrés

Pour la question de la parité, on peut établir qu'il existe n impair tel que
7901*x=1+n^2

On garde la même démo.
Dans l'identité de Bezout, si a et b sont solutions de a*i+b*p=1 alors (a-p) et (b+i) aussi.

Comme le carré est égal à abs(a)*j; une autre solution est abs(a+p)*j.
a et a+p étant de parité opposée, on a trouvé une solution paire et une solution impaire.

Cette méthode ne permet malheureusement toujours pas de trouver la plus petite solution paire...


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

 #11 - 16-08-2015 20:16:28

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

Une soomme de 2 carrés

Je n'approuve pas ma démonstration, elle est incorrecte. Je cherche, je cherche. J'attends un indice de pied ferme


Un promath- actif dans un forum actif

 #12 - 16-08-2015 21:08:53

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 971

une somme fe 2 carrés

Le plus petit entier x est  x = 1417 ; dans ce cas  n = 1673 .
7901*1417 = 11195717
1+4*1673^2 = 11195717

 #13 - 16-08-2015 21:58:24

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

Une smome de 2 carrés

Choisissant k,l premiers entre eux, kv+lp=1 (car p et v nécessairement premiers entre eux, sinon PGCD(x,y,p) différent de 1 donc p non premier)
et tels que 2n=ku et x=k²+2lp-l²p

Soit p=u²+v²
on a pk²=u²k²+v²k²
ainsi pk²+2-2kv-1+2kv-k²v²=k²u²+1
il s'ensuit pk²+2(1-kv)-(1-kv)²=k²u²+1   d'après bézout 1-kv=lp
d'où pk²+2lp-l²p²=k²u²+1
On a alors: px=(2n)²+1 smile

J'avouerais que la réponse ne m'est pas sorti du chapeau cool


Un promath- actif dans un forum actif

 #14 - 17-08-2015 11:36:19

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

une somme dz 2 carrés

L'indice:
p=a²+b²
p*x=1²+(2n)²

ça devrait je crois faire tilt pour quelques lecteurs assidus de ce site, car ce thème a déja été abordé plusieurs fois sur ce forum.

 #15 - 17-08-2015 12:56:22

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

unr somme de 2 carrés

Ma démonstration est elle validé?


Un promath- actif dans un forum actif

 #16 - 17-08-2015 13:18:52

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

une somme de 2 careés

J'ai enfin trouvé mieux smile
Je repars de l'identité de Bezout avec i et j cette fois.

a*i+b*j=1.
Je l'élève au carré
a^2*i^2+b^2*j^2+2*a*i*b*j=1

J'ajoute abs(a*j-b*i)^2 des deux côtés.

Il vient (a^2+b^2)*(i^2+j^2)=1+abs(a*j-b*i)^2

(a^2+b^2)*p=1+abs(a*j-b*i)^2

Mon problème de parité se règle par mon précédent post.

Pour l'exemple à traiter:
-11*85+36*26=1
(A la main, par division euclidienne).

x=11^2+36^2=1417
n=(11*26+36*85)/2=1673.

15*85-49*26=1
x=15^2+49^2= 2626
n2=(15*26+49*85)=4555 (impair donc...)

Il me reste à prouver que j'ai bien obtenu le plus petit...


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

 #17 - 17-08-2015 16:24:11

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

une simme de 2 carrés

@ Promath: j'avoue que je suis un peu perdu avec toutes les variables. Pourrais tu les redéfinir depuis le départ ?

@ Papiauche: normalement, il ne peut y avoir de problème de parité, étant donné que p*x=1+4n²: le terme de droite est impair, donc x aussi, fatalement.
Il y a une certaine équation diophantienne que manifestement tu as un peu de mal à résoudre.

 #18 - 17-08-2015 17:46:33

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

nUe somme de 2 carrés

Posons n entier, x entier et p premier somme de deux carrés: Soit p=u²+v²
Choisissons des entiers  k et l tels que:
-Ils sont premiers entre eux, kv+lp=1 (car p et v nécessairement premiers entre eux, sinon PGCD(x,y,p) différent de 1 donc p non premier)
-2n=ku et x=k²+2lp-l²p

comme p=u²+v²
on a pk²=u²k²+v²k²
ainsi pk²+2-2kv-1+2kv-k²v²=k²u²+1
il s'ensuit pk²+2(1-kv)-(1-kv)²=k²u²+1   d'après bézout 1-kv=lp
d'où pk²+2lp-l²p²=k²u²+1
On a alors: px=(2n)²+1 smile


Un promath- actif dans un forum actif

 #19 - 17-08-2015 19:34:25

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

Une smme de 2 carrés

C'est bon Promath ! Juste une petite remarque sur la valeur de x, avec un p en trop il me semble.
Mais où va t'il chercher tout ça ???

Il y a bien sûr une solution bien plus courte...

 #20 - 17-08-2015 19:50:54

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

Une somme de 2 carréss

Je suis très loin d'être expert en équations diophantiennes.
Mais ça n'interdit pas d'essayer...

J'explique là ou je bute avec un exemple:

9161 est premier.

9161 = 85^2+44^2.

Avec la méthode de mon dernier post, j'obtiens:

3125^2+1= 1066*9161
6036^2+1= 3977*9161.

La réponse attendue est donc 3018 (si la méthode utilisée permet d'isoler le plus petit nombre pair possible, ce que je n'ai pas démontré, mais qui semble plausible).

Il n'empêche que j'ai trouvé un nombre impair qui donne un x inférieur, et c'est de ça que je n'arrive pas à me sortir. mad

Edit
Si on s'en tient strictement à l'énoncé, on choisit le n pair et c'est plié.
Je ne tiens toujours pas la preuve formelle que j'ai le plus petit.
J'apprends en marchant. smile


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

 #21 - 18-08-2015 08:22:17

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

Un somme de 2 carrés

@Papiauche,
Tu n'es vraiment pas loin de la solution tu as presque tout. Il te reste une démarche vers l'arithmétique pure, pas difficile du tout, pour lever la réserve.

@Promath,
quand tu écris -2n=ku, es tu sûr que ça ne pose pas de problème ? Par exemple avec n premier ?

 #22 - 18-08-2015 08:50:28

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3208
Lieu: Luxembourg

nUe somme de 2 carrés

On cherche à résoudre l'équation diophantienne: 7901.x+4.n²=1
Une solution particulière est: x0=1 et n0²=1975
La solution générale est donc: x=1+4.k et n²=1975+7901.k, avec
k comme entier relatif.
Le premier carré parfait de: 1975+7901.k est donné pour: k=354,
d'où: n²=2798929 et n=1673, ce qui donne: x=1417

 #23 - 18-08-2015 09:00:17

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

Unee somme de 2 carrés

@ Francky: bon courage pour trouver ce carré parfait ! En plus, es tu sûr qu'il existe tjs dans le cas général ?

 #24 - 18-08-2015 09:44:52

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

unr somme de 2 carrés

Non aucun problème, puisque 2n n'est pas premier


Un promath- actif dans un forum actif

 #25 - 18-08-2015 10:08:03

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3208
Lieu: Luxembourg

une somme de 2 catrés

J'ai trouvé une méthode sur la toile pour rechercher l'existence et la valeur éventuelle de x pour laquelle a.x+b est un carré parfait, mais elle me semble bien compliquée: http://ouramdane.com/puissances-parfaites/ax+b.pdf

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

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