A²+1=2*b²
Olympiades mathématiques, énigmes et défis
-
nodjim
- Membre Complexe
- Messages: 3241
- Enregistré le: 24 Avr 2009, 17:35
-
par nodjim » 09 Oct 2010, 11:46
Bonjour à tous.
Résoudre dans N cette équation.
C'est sûrement connu. J'imagine qu'il existe peut être une manière générale de résoudre, quand c'est possible: ka²+b=jc² avec k,b et j donnés.
-
Ben314
- Le Ben
- Messages: 21535
- Enregistré le: 11 Nov 2009, 22:53
-
par Ben314 » 09 Oct 2010, 13:07
Salut,
Cherche "Equation de Pell-Fermat" (celles de la forme x²-dy²=+-1 avec ici d=2) et tu devrait trouver ton bonheur.
On peut aussi les trouver sans connaitre toute la théorie : on utilise la "méthode de descente" de Fermat, c'est à dire que, partant d'une solution (x,y) on montre que l'on peut en trouver une autre (x',y') "plus petite" (sous certaines conditions...)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
-
beagle
- Habitué(e)
- Messages: 8707
- Enregistré le: 08 Sep 2009, 15:14
-
par beagle » 09 Oct 2010, 13:12
Ben314 a écrit:Salut,
On peut aussi les trouver sans connaitre toute la théorie : on utilise la "méthode de descente" de Fermat, c'est à dire que, partant d'une solution (x,y) on montre que l'on peut en trouver une autre (x',y') "plus petite" (sous certaines conditions...)
oui, c'est avec cette méthode que j'avais trouvé a=1, b=1
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
-
Ben314
- Le Ben
- Messages: 21535
- Enregistré le: 11 Nov 2009, 22:53
-
par Ben314 » 09 Oct 2010, 13:45
Par exemple, "à la main",
Tu peut montrer que, si
et
vérifient
,
alors
et
sont
, vérifient
et
.
A force de "descendre", on fini par tomber sur une solution telle que
et
c'est à dire sur la solution "triviale"
(qui, si on itère une fois de plus le procéssus donne
)
cela permet en "remontant" de trouver toutes les autres solutions.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
-
nodjim
- Membre Complexe
- Messages: 3241
- Enregistré le: 24 Avr 2009, 17:35
-
par nodjim » 09 Oct 2010, 13:51
Je ne connaissais pas. Je trouve ça intéressant. C'est du bezout, mais avec des carrés. On peut aussi avec des cubes ou des puissances supérieures ?
-
Ben314
- Le Ben
- Messages: 21535
- Enregistré le: 11 Nov 2009, 22:53
-
par Ben314 » 09 Oct 2010, 13:56
nodjim a écrit:Je ne connaissais pas. Je trouve ça intéressant. C'est du bezout, mais avec des carrés. On peut aussi avec des cubes ou des puissances supérieures ?
pas à ma conaissance (i.e. je ne connais pas de théorie générale simple, mais il y a forcément des cas particuliers où c'est faisable)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
-
Doraki
- Habitué(e)
- Messages: 5021
- Enregistré le: 20 Aoû 2008, 12:07
-
par Doraki » 09 Oct 2010, 20:12
Sur cette équation particulière,
les solutions vont être essentiellement données par des approximations de racine(2) (a/b vaut presque racine(2)).
Quand tu es face à 2b²-a² = 1,
il y a une solution (a=1, b=1), et sinon, tu peux déduire que les autres solutions sont telles que a>b (parceque si b=a, ça fait a², qui est trop grand)
Du coup tu remplaces a par a+b' et tu recommences.
Le truc bien quand t'es en degré 2, c'est que tu vas forcément finir par retomber sur l'équation de départ (et en fait, les transformations que tu fais peuvent se lire sur le développement en fraction continue de racine(2), qui est lui aussi périodique)
Dès que tu es en degré 3, même si tu appliques ce procédé, tu verras vite que les coefficients devant a^3, a²b, ab², b^3 vont pas être bornés et que tu vas jamais pouvoir retomber sur une équation déjà connue (et ça devrait être pareil pour le développement en fraction continue)
Une façon un peu plus élaborée de décrire ce qui se passe est de dire que l'équation équivaut à trouver les éléments de Z[sqrt(2)] de norme -1. Si on en a un (par exemple 1+-racine(2)), les autres sont obtenus en le multipliant par un élément de norme 1.
Et on peut étudier la structure du groupe des éléments de norme 1 de Z[sqrt(2)] et voir qu'il est isomorphe à (Z/2Z) * Z
(on a -1 qui est d'ordre 2, et 3+-2racine(2) pour la composante infinie)
-
nodjim
- Membre Complexe
- Messages: 3241
- Enregistré le: 24 Avr 2009, 17:35
-
par nodjim » 11 Oct 2010, 23:06
Merci pour vos réponses.
En poussant un peu, puisque la première question semblait assez facile:
trouver toutes les solutions de cette équation:
ax²-(a-1)y²=1
Donner le couple minimal ne dévoilera pas grand chose des autres solutions:
(1,1).
Bonne recherche.
-
Ben314
- Le Ben
- Messages: 21535
- Enregistré le: 11 Nov 2009, 22:53
-
par Ben314 » 12 Oct 2010, 00:55
Salut,
Si (x,y) est une solution, vérifie que
x'=(2a-1)x-(2a-2)y
y'=-2a.x+(2a-1)y
est une solution "plus petite" que (x,y)...
Ou, si tu préfère "monter", partant de x0=1 ; y0=1, construit
x(n+1)=(2a-1)xn+(2a-2)yn
y(n+1)=2a.xn+(2a-1)yn
et tu aura ainsi toutes les solutions.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
-
nodjim
- Membre Complexe
- Messages: 3241
- Enregistré le: 24 Avr 2009, 17:35
-
par nodjim » 12 Oct 2010, 09:36
Oui, c'est ça. Comment as tu trouvé si vite ?
On peut remarquer la précision du rapport y/x pour l'évaluation de racine (a/(a-1)), l'écart relatif est proche de 1/(2Ax²). En 2 ou 3 passes, on dépasse facilement la précision d'une machine ordinaire !
-
nodjim
- Membre Complexe
- Messages: 3241
- Enregistré le: 24 Avr 2009, 17:35
-
par nodjim » 14 Oct 2010, 17:42
Une curiosité:
Montrer qu'il existe toujours un couple d'entiers (a,b) de sorte que :
A^(2^n)=a²-(A+4)b² quels que soient A et n entiers.
-
Ben314
- Le Ben
- Messages: 21535
- Enregistré le: 11 Nov 2009, 22:53
-
par Ben314 » 14 Oct 2010, 18:57
Salut,
Il doit manquer un truc dans l'énoncé :
Pour A=2 et n=0, l'équation est
a²-6b²=2
qui implique que a²=2 modulo 3 ce qui est impossible.
Pour n>=1, l'équation admet comme solution "triviale" a=A^(2^(n-1)) , b=0.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
-
nodjim
- Membre Complexe
- Messages: 3241
- Enregistré le: 24 Avr 2009, 17:35
-
par nodjim » 14 Oct 2010, 19:09
Oui, n a et b ne doivent pas être nuls.
-
Ben314
- Le Ben
- Messages: 21535
- Enregistré le: 11 Nov 2009, 22:53
-
par Ben314 » 14 Oct 2010, 19:19
Bon, n'embèche que, si on a une solution non triviale (a,b) de a²-(A+4)b²=A², il suffit de multiplier a et b par A^(2^(n-1)-1) pour obtenir une solution de a²-(A+4)b²=A^(2^n)...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
-
nodjim
- Membre Complexe
- Messages: 3241
- Enregistré le: 24 Avr 2009, 17:35
-
par nodjim » 15 Oct 2010, 09:06
Oui ,c'est vrai. Ce n'est pas ce que j'attendais, mais ça marche, et c'est trivial.
Reste à savoir si la solution primitive (a,b) existe toujours.
-
Ben314
- Le Ben
- Messages: 21535
- Enregistré le: 11 Nov 2009, 22:53
-
par Ben314 » 15 Oct 2010, 10:12
Il me semble bien que a=A+8 et b=4 donne a²-(A+4)b²=A²
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
-
nodjim
- Membre Complexe
- Messages: 3241
- Enregistré le: 24 Avr 2009, 17:35
-
par nodjim » 16 Oct 2010, 10:20
C'est bien ça. Cette question vient de la comparaison entre les différentes solutions de l'équation de Pell-Fermat a²-nb²=+-1 et de l'algorithme ordinaire du calcul d'une racine carrée:
1) Pell-Fermat: parmi la série de solutions, il y a cette série: a²-nb²=-+1 puis (a²+nb²)²-n(2ab)²=+1
qui consiste à transformer le couple (a,b) en celui ci (a²+nb², 2ab) qui est le carré du précédent.
2) L'algorithme du calcul de la racine carrée: ((n/2)+n/(n/2))/2. Le premier résultat est toujours un carré. Les autres résultats s'obtiennent en transformant un rapport a/b en ((a/b)+n/(a/b))/2 qui revient à passer du couple (a,b) au couple (a²+nb², 2ab). C'est à dire qu'il s'agit du même algorithme que le précédent. Le résultat a²-+nb², qui est la différence entre la racine de n et le rapport a/b est un carré de carré de carré.... alors que l'équation de Pell Fermat donne toujours 1 comme différence.
Tout ça pour dire que si on veut calculer avec beaucoup de précision une racine carrée, c'est mieux de chercher la solution a²-nb²=+-1.
-
Ben314
- Le Ben
- Messages: 21535
- Enregistré le: 11 Nov 2009, 22:53
-
par Ben314 » 16 Oct 2010, 14:08
Juste un petit mot pour signaler qu'au niveau "culture générale", lorsque tu parle pour approximer racine(d) de "passer" de (a,b) à (a²+nb²,2ab), on peut aussi le voir comme une application de la méthode des tangentes de Newton qui dit que, sous certaines hypothèses (vérifiées dans le cas présent), pour approximer une solution d'une équation f(x)=0, il faut considérer la suite U(n+1)=Un-f(Un)/f'(Un).
Si on prend f(x)=x²-d (=> f(x)=0 a pour solutions +-racine(d)) on tombe sur U(n+1)=(Un²+d)/(2Un) qui, si Un=a/b dit que U(n+1)=(a²+nb²)/(2ab).
Je fait cette remarque principalement du fait que, à mon sens, la méthode "équation de Pell-Fermat" consiste plutôt à déterminer les fractions a/b qui apparaissent lorsque l'on évalue la fraction continue de racine(d) et que, dans ce cas, on obtient beaucoup plus de fractions a/b que lorsque l'on utilise la méthode de Newton (par contre, si on prend pour U0 le nombre entier suivant racine(d), les fraction obtenues par la méthode de Newton font toutes parti des fraction obtenues par le développement en fraction continue)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 22 invités