Le 2011ème point...

[nodjim]

Voici comment je procède habituellement (c'est assez perso, mais..)
5a-27b=1
5(a-5b)-2b=1
5c-2b=1
Ici, c'est court, solution évidente c=1 et b=2
comme c=a-5b, alors a=c+5b=11
Donc:
5(11+27k)-27(2+5k)=1

[Ben314]

Concernant la façon de rédiger, il y a affectivement plusieurs méthodes et celle de nodgim vaut largement la mienne...
Dans les deux cas, au fond on fait exactement les mêmes calculs (il commence par faire "27 divisé par 5 : le quotient est 5 et le reste est 2") mais pas dans le même ordre (en fait il commence par faire uniquement les divisions puis il "remonte" les calculs de bas en haut pour calculer les coef.)

Si celle que j'utilise est considérée habituellement comme plus "classique", c'est sans doute par ce qu'elle est un peu plus simple à mettre en œuvre sur un ordi (pas la peine de mémoriser la liste des divisions qu'on a fait pour les "remonter" à la fin), mais "à la main", ça va rien changer.

Sinon, reprenons ton problème de "points à coordonnées entières positives sur une droite" pour voir que c'est encore la même chose et raisonnons de nouveau sur un exemple :

Quel est le 1000 em point à coordonnées entières positives sur la droite [B]48X-69Y=213[/B]
Euclide (sans utilise l'astuce des restes négatifs) :
a=69, b=48
21=69-1x48=a-b
6=48-2x21=b-2(a-b)=3b-2a
3=21-3x6=(a-b)-3(3b-2a)=7a-10b
A l'étape suivante, on divise 6 par 3. Il y va 2 fois et il reste 0 et si on écrivait quelque chose, ça serait :
0=6-2x3=(3b-2a)-2(7a-10b)=23b-16a.
En fait, si on trouve 0 (et pas 1), ça veut dire que les deux nombres ne sont premiers entre eux et leur pgcd est le dernier nombre trouvé avant le 0, c'est à dire ici, c'est 3.
Comme 48 et 69 sont tout les deux multiple de 3, si le 213 de l'équation de départ ne l'était pas, il n'y aurait pas de solutions à l'équation, mais là il est divisible par 3 et on peut simplifier toute l'équation par 3 ce qui donne : 16X-23Y=71.
(Remarque : les nombres 23=48/3 et 16=69/3 sont ceux qu'on a obtenu à la dernière ligne inutile de l'algo d'euclide : 0=23b-16a.)
Donc on refait l'algo d'euclide avec a'=23=a/3 et b'=16=b/3 ?
Non, c'est pas la peine : en partant de la dernière ligne utile obtenue : 3=7a-10b en divisant par 3 on obtient 1=7a'-10b'=7x23-10x16.
En multipliant par 71 ça nous donne 71=16x(-10x71)x16+23x(7x71)=16x(-710)-23x(-497) donc le point (X=-710,Y=-497) est UN DES POINTS à coordonnées entières sur la droite, (mais ce n'est pas vraiment une solution valable vu que X=0 qui donne k>=710/23 donc k>=31
ainsi que Y>=0 qui donne k>=497/16 donc k>=32.
Pour avoir X>=0 ET Y>=0 il faut dont prendre k>=32.
Pour k=32 on trouve X=23k-710=26 et Y=16k-497=15, qui est le premier point de la droite à coordonnées entières positives (mais en fait ce n'est pas vraiment utile de le calculer).
Le 2em point sur la droite va correspondre à k=33, le 3em à k=34, le 4em à k=35 ... le 1000em point va correspondre à k=1031 : X=23k-710=23 003 et Y=16k-497=15 999.

Une fois qu'on a vu que le premier point correspond à k=32 on aurait aussi pu poser k=31+n pour trouver :
X=23(31+n)-710=23n+3 ; Y=16(31+n)-497=16n-1
ce qui donne directement les coordonnées du n-ième point

[Waax22951]

J'avoue que cette méthode est superbe, je vais m'y entraîner, ça peut toujours être intéressant ^^'
Merci beaucoup pour toutes vos réponses et bonne continuation :lol3: