Forum de mathématiques
Recherche Messages du jour Marquer les forums comme lus
Rechercher sur Maths-Forum  
  Recherche avancée
  Maths-Forum > Forum Communauté Maths-Forum > Forum Défis
  Pseudo
  Mot de passe  Oublié?  S'inscrire »  
 
Outils de la discussion Rechercher Modes d'affichage
Vieux 05/11/2013, 22h08
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut Le 2011ème point...

Bonjour,
J'aimerais vous faire part d'un problème qui m'a bien plu, puisque à mon niveau, il s'agit du premier vrai problème qui demandait une réflexion autre que celle des théorèmes tout fait du cours :
"Dans un repère, d est la droite d'équation :
5x-27y=1

Le "premier point" à coordonnées entières en positives de la droite d est le point de coordonnées (11; 2)
Quel est le 2011ème point de d à coordonnées positives ?"


J'avoue que j'ai trouvé un résultat plutôt simplement, ce qui m'inquiète un peu
Donc j'espère que nous aurons les mêmes résultats !

La bonne journée !


Waax22951 est déconnecté  
Vieux 06/11/2013, 10h16
nodjim
Membre Complexe
 
Sur Maths-Forum depuis: avril 2009
Messages: 2 439
Par défaut

Ne t'inquiète pas, c'est normal.
J'imagine que tu as vu Bezout ? A partir de là...
Ton 2011 ème point, tu as dû le trouver quelque part vers les (50000, 10000) ?
nodjim est déconnecté  
Vieux 06/11/2013, 13h24
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut

Hum... Non, c'est quoi ? :/
Oui, j'ai trouvé les coordonnées (54281; 10052), c'est ça ? ^^
Waax22951 est déconnecté  
Vieux 06/11/2013, 13h36
chan79
Membre Complexe
 
Avatar de chan79
 
Sur Maths-Forum depuis: mars 2007
Localisation: POITOU
Messages: 6 543
Par défaut

Citation:
Posté par Waax22951
Hum... Non, c'est quoi ? :/
Oui, j'ai trouvé les coordonnées (54281; 10052), c'est ça ? ^^

C'est bien ça
chan79 est actuellement connecté  
Vieux 06/11/2013, 14h44
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut

D'accord merci ;)
Je viens de regarder sur internet l'identité de Bézout, et oui, j'ai utilisé cette méthode (enfin, quelque chose qui s'en rapproche ^^)

La bonne journée !
Waax22951 est déconnecté  
Vieux 06/11/2013, 18h13
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut

En fait, je me suis renseigné un peu plus, mais le seul point commun entre ma méthode et le théorème de Bézout est que j'ai utilisé les PGCD, donc en fait il n'y a pas vraiment de rapports :/
Waax22951 est déconnecté  
Vieux 07/11/2013, 17h13
ffpower
Membre Complexe
 
Sur Maths-Forum depuis: décembre 2007
Localisation: Rio
Messages: 2 530
Par défaut

Le theoreme de Bezout sert juste a justifier qu'une equation de ce genre admet des solutions.
L'algorithme de Bezout permet de trouver explicitement une solution.
Une fois qu'on q une solution, on peut les trouver toutes, pas besoin de Bezout pour ca.
Ici, l'algo de Bezout servirait a obtenir la solution (11,2). Mais vu que l'enonce donne deja cette solution de l'equation, pas besoin de Bezout donc..
ffpower est déconnecté  
Vieux 07/11/2013, 19h49
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut

Ne sachant pas quoi faire je me suis dis que je pourrais généraliser le problème sous la forme "ax+by=c" en cherchant le nombre de solutions dans \mathbb{N}*, et j'ai réussi à trouver une formule permettant de trouver x_n et y_n, qui sont les résultats de la n-ième solution ainsi qu'un moyen de trouver le nombre de solutions, mais toutes ces formules demandent de connaître le premier couple de solution... Y aurait-il un moyen de trouver cette solution par le calcul sans utiliser d'algorithme compliqué ou une formule à rallonge ? (je dirais que oui mais j'avoue que je ne trouve pas encore ... )
Des idées ?
Waax22951 est déconnecté  
Vieux 07/11/2013, 21h02
Ben314
Membre Complexe
 
Avatar de Ben314
 
Sur Maths-Forum depuis: novembre 2009
Localisation: Chas
Messages: 10 216
Par défaut

Perso, je suis comme ffpower : je ne connais que l'algo. d'euclide pour trouver des solutions particulière (et j'ai un peu peur qu'il n'y ait que des méthodes de ce type pour trouver les solutions dans le cas général...)

D'un autre coté, l'algo d'euclide, c'est pas non plus la mer à boire...

Si tu part de ton premier exemple 5x-27y, si on applique l'algo. d'euclide "étendu", ça consiste à écrire :
27 = 5 x 0 + 1 x 27
5 = 5 x 1 + 0 x 27
Je divise 27 par 5. Le quotient est 5 et le reste est 2 : 27=5x5+2 donc
2 = 27 - 5 x 5 = (5 x 0 + 1 x 27) - 5x(5 x 1 + 0 x 27)
= -5 x 5 + 1 x 27
(étape un peu débile si on fait les calculs à la main, mais pratique si on fait faire les calcul par un ordi)
Je divise 5 par 2 : Le quotient est 2 et le reste est 1 : 5=2x2+1 donc
1 = 5 - 2 x 2 = (5 x 1 + 0 x 27) - 2x( -5 x 5 + 1 x 27)
= 11 x 5 - 2 x 27
cqfd

Essaye de le faire toi même sur un exemple avec des nombres un peu plus grands, par exemple 23 et 61.

Dernière modification par Ben314 07/11/2013 à 21h15.
Ben314 est déconnecté  
Vieux 07/11/2013, 22h10
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut

Je suis un peu fatigué donc c'est sûrement bête, mais il s'agit bien du même algorithme d'Euclide pour les pgcd, non ?
Si c'est le cas, il y a aussi la méthode de la soustraction successive qui est plus rapide si on ne veut pas se prendre la tête, non ?
Merci de vos réponses ! =D
Waax22951 est déconnecté  
Vieux 07/11/2013, 23h41
Ben314
Membre Complexe
 
Avatar de Ben314
 
Sur Maths-Forum depuis: novembre 2009
Localisation: Chas
Messages: 10 216
Par défaut

La "méthode par soustraction" et celle "par reste de division", c'est et fait les deux mêmes...
Sauf qu'au lieu (par exemple) d'écrire que, si on divise 31 par 9, il y va 3 fois et il reste 4, ben tu va écrire 31-9=22 puis 22-9=13 puis 13-9=4.
Certes, c'est un peu moins fatiguant pour le cerveau (y'a que des soustractions à faire), mais si par hasard il y a une (ou des) divisions avec un gros quotient, ben c'est vachement plus long avec que des soustractions...
Par exemple, pour trouver le reste de la division de 357 par 11, ben perso, même de tête, je commence pas par faire 357-11 puis -11 puis -11... etc
Je commence directement par 357-330 (330=11*30) et après, effectivement, je risque de fait (éventuellement) des -11

Edit : La division par 11, c'est un mauvais exemple vu que...

Dernière modification par Ben314 07/11/2013 à 23h48.
Ben314 est déconnecté  
Vieux 08/11/2013, 18h14
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut

Hum... Je pensais que c'était à cause de la fatigue, mais en fait je ne comprend pas le raisonnement x)
Parce que, dans l'exemple, on obtient un 5 et un deux, ce qui permet de faire le lien, mais avec 23 et 61 je trouve :
61 = 23*2+15
15 = 61-23*2
15 = -2*23 - (-1)*61

15 = 7*2+1
1 = 15-7*2
1 = (-2*23 - (-1)*61)-7*2

Mais je reste bloqué, car je ne peux pas changer le 7 ou le deux... Où est ma faute ?
Waax22951 est déconnecté  
Vieux 08/11/2013, 18h50
Ben314
Membre Complexe
 
Avatar de Ben314
 
Sur Maths-Forum depuis: novembre 2009
Localisation: Chas
Messages: 10 216
Par défaut

Au départ, tu as 61 puis 23, puis le reste de la div. de 61 par 23, c'est à dire 15.
Arrivé à ce point, tu doit diviser 23 par 15 : il y va une fois et il reste 8
(à la limite, si tu comprend parfaitement ce que tu fait, tu peut écrire qu'il y va 2 fois et qu'il reste -1 : ça gagne du temps...)

Avec 61 et 23 :

1)
61 = a
2)
23 = b
3) Je divise 61 par 23. Le quotient est 2 et le reste est 15 : 61=2x23+15 donc
15 = 61 - 2x23 = a - 2b
4) Je divise 23 par 15. Le quotient est 1 et le reste est 8 : 23=1x15+8 donc
8 = 23 - 15 = b - (a - 2b) = 3b - a
5) Je divise 15 par 8. Le quotient est 1 et le reste est 7 : 15=1x8+7 donc
7 = 15 - 8 = (a - 2b) - (3b - a) = 2a - 5b
6) Je divise 8 par 7. Le quotient est 1 et le reste est 1 : 8=1x7+1 donc
1 = 8 - 7 = (3b - a) - (2a - 5b) = 8b - 3a

conclusion : (-3)x61 + 8x23 = 1

Et, à la limite, à l'étape 5, tu pouvais écrire :
5) Je divise 15 par 8. Le quotient est 2 et le reste est -1 : 15=2x8-1 donc
1 = 2x8 - 15 = 2 x (3b - a) - (a - 2b) = 8b - 3b

De même, à partir de l'étape 3), on aurait pu écrire :
3) Je divise 61 par 23. Le quotient est 3 et le reste est -8 : 61=3x23-8 donc
8 = 3x23 - 61 = 3b - a
4) Je divise 23 par 8. Le quotient est 3 et le reste est -1 : 23=3x8-1 donc
1 = 3x8 - 23 = 3 x (3b-a) - b = 8b - 3a

(en fait, c'est peut-être plus simple à comprendre en écrivant au départ "61=a" et "23=b" pour mieux comprendre qui on ajoute avec qui)

Dernière modification par Ben314 08/11/2013 à 21h49.
Ben314 est déconnecté  
Vieux 08/11/2013, 19h15
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut

Oui c'est beaucoup plus simple comme ça !
Je pense comprendre le principe, je vais m'entrainer dès que j'aurais fini un truc ^^
Vous pensez qu'on peut transformer cet algorithme sous la forme d'une formule ou quelque chose d'autre ?
En tout cas merci beaucoup ;)
Waax22951 est déconnecté  
Vieux 08/11/2013, 19h17
Ben314
Membre Complexe
 
Avatar de Ben314
 
Sur Maths-Forum depuis: novembre 2009
Localisation: Chas
Messages: 10 216
Par défaut

Transformer l’algorithme en une unique formule "simple", non, je pense pas qu'on puisse, mais par contre faire un programme (par exemple sous algobox), c'est très facile...

P.S. J'ai beau être vieux (et c..), je préfèrerais que tu me tutoie...
Ben314 est déconnecté  
Vieux 08/11/2013, 21h15
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut

Oups désolé :X
D'accord merci ;)
Et comment fait on quand c est différent de 1 ? (on le considère toujours appartenant à \mathbb{N}* )
J'avoue que j'ai pas trop cherché, parce que je fais quelque chose à côté, mais je ne vois pas de méthode "logique"...
Merci ^^
Waax22951 est déconnecté  
Vieux 08/11/2013, 21h49
Ben314
Membre Complexe
 
Avatar de Ben314
 
Sur Maths-Forum depuis: novembre 2009
Localisation: Chas
Messages: 10 216
Par défaut

Si par exemple, tu cherche une solution de 61X+23Y=17 (*),
Tu fait l'algo d'euclide pour trouver que 61x(-3) + 23x8 = 1
puis.. tu multiplie tout par 17 : 61x(-3x17)+23x(8x17) = 17
ça te donne UNE solution (qui n'est en général pas parmi les "plus petites") puis tu en déduit toutes les autres (et à la limite, tu peut chercher lesquelles ne sont "pas trop grandes")
Ben314 est déconnecté  
Vieux 08/11/2013, 22h03
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut

Citation:
Posté par Ben314
Si par exemple, tu cherche une solution de 61X+23Y=17 (*),
Tu fait l'algo d'euclide pour trouver que 61x(-3) + 23x8 = 1
puis.. tu multiplie tout par 17 : 61x(-3x17)+23x(8x17) = 17
ça te donne UNE solution (qui n'est en général pas parmi les "plus petites") puis tu en déduit toutes les autres (et à la limite, tu peut chercher lesquelles ne sont "pas trop grandes")

Donc il va falloir que je trouve une méthode en fonction d'une solution... x)
Tu crois qu'il serait possible de trouver sa "place" dans l'ordre des solutions, par exemple, si on sait qu'il y a au plus 7.5 solutions (donc il y a 7 solutions entières), si on considère que les solutions sont "uniformément" réparties, on pourrait trouver le premier point ou, au moins l'emplacement de la solution par rapport aux autres. Tu penses que c'est possible ? ^^
Waax22951 est déconnecté  
Vieux 08/11/2013, 22h38
Ben314
Membre Complexe
 
Avatar de Ben314
 
Sur Maths-Forum depuis: novembre 2009
Localisation: Chas
Messages: 10 216
Par défaut

Je ne comprend pas trop de quoi tu parle là.
Le "bon" cadre (c'est à dire le cadre dans lequel tout marche parfaitement bien) pour résoudre les équation aX+bY=c est celui des entiers relatifs (i.e. positif, nuls ou négatifs) : a,b,c sont des entiers relatif et on cherche les solutions (X,Y) parmi les couples d'entiers relatifs.
Dans ce cas, il y a soit aucune solution (par exemple 4X-6Y=7 n'a pas de solutions entières) soit une infinité de solutions.
Lorsque l'on cherche (par exemple) les solutions pour lesquelles X et Y sont des entiers naturels (i.e. positifs), je pense que le plus simple consiste souvent à commencer par chercher TOUTES les solutions dans les entiers relatifs PUIS à regarder lesquelles sont positives.

Exemple : On cherche tout les couples d'entiers positifs ou nuls (X,Y) tels que 5X+7Y=111.
On fait l'algo d'euclide.
On en déduit que a=5 et b=7 sont premiers entre eux et que 1=3a-2b.
Donc 111=333a-222b et l'équation de départ peut s'écrire aX+bY=333a-222b
soit encore b(Y+222)=a(333-X) (#)
Comme b est premier avec a et qu'il divise a(333-X), c'est qu'il divise 333-X (théorème de Gauss)
Donc 333-X=kb avec k entier relatif c'est à dire X=333-7k.
En réinjectant ce résultat dans l'équation (#) on trouve que Y+222=ka donc que Y=5k-222.
Et on termine en disant que, pour que X et Y soient positifs ou nuls, il faut que \frac{333}{7}\geq k \geq \frac{222}{5} c'est à dire que k\in\{45,46,47}.
Il y a donc 3 solutions au problème de départ.

Dernière modification par Ben314 08/11/2013 à 22h56.
Ben314 est déconnecté  
Vieux 09/11/2013, 11h07
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut

Dans mon problème de départ, je cherchais le nombre de solutions entières positives pour ax-by=c, ainsi qu'un moyen (dans un second temps) pour obtenir la "n-ième" solution entière relative de ax+by+c, en se basant sur une certaine solution, ce qui m'a paru idiot ensuite... Donc je me suis concentré sur le premier problème ^^
Donc dans mon problème de départ, il s'agissait de savoir s'il y avait des solutions réelles, le nombre de solutions s'il y en a(leur nombre est forcément fini dans les entiers positifs, puisqu'on a ax-by=c), puis de les définir en fonction du premier couple de solutions
Avec l'algorithme d'Euclide, on peut avoir UNE de ces solutions, donc mon problème est que je n'aurai pas ce premier couple, et que donc je devrai définir les autres points en fonction d'un autre, quelconque, mais ça me paraît peut probable à faire...
Ou alors il me faudrait savoir la "place" de cette solution par rapport aux autres (si elle est le première, la seconde, la troisième, etc...)
Tu penses que ce serait possible ?
Je crois que j'ai déjà vu ce genre d'exemples, mais je ne me rappelle plus où ^^
Waax22951 est déconnecté  
Vieux 09/11/2013, 11h23
nodjim
Membre Complexe
 
Sur Maths-Forum depuis: avril 2009
Messages: 2 439
Par défaut

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
nodjim est déconnecté  
Vieux 09/11/2013, 14h16
Ben314
Membre Complexe
 
Avatar de Ben314
 
Sur Maths-Forum depuis: novembre 2009
Localisation: Chas
Messages: 10 216
Par défaut

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 48X-69Y=213
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 et Y<0).
Cherchons les autres (pas forcément positives) :
16X-23Y=71 équivaut à 16X-23Y=16x(-710)-23x(-497) et donc à 16(X+710)=23(Y+497).
16 est premier avec 23 et divise 23(Y+497) donc il divise Y+497 : Y+497=16k.
et en réinjectant dans l'équation on trouve que X+710=23k.
Les solutions entières (pas forcément positives) sont donc X=23k-710 et Y=16k-497 avec k entier relatif.
Et maintenant, pour finir, on résout 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

Dernière modification par Ben314 09/11/2013 à 14h25.
Ben314 est déconnecté  
Vieux 12/11/2013, 21h10
Waax22951
Membre Réel
 
Avatar de Waax22951
 
Sur Maths-Forum depuis: mai 2013
Localisation: Poitou-Charentes
Messages: 267
Par défaut

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
Waax22951 est déconnecté  

Outils de la discussion Rechercher
Rechercher:

Recherche avancée
Modes d'affichage




Règles des messages du forum de mathématiques
Vous pouvez ouvrir de nouvelles discussions : nonoui
Vous pouvez envoyer des réponses : nonoui
Vous pouvez insérer des pièces jointes : nonoui
Vous pouvez modifier vos messages : nonoui

Les balises BB sont activées : oui
Les smileys sont activés : oui
La balise [IMG] est activée : oui
Le code HTML peut être employé : non


Forum de maths © 2003-2014 Maths-Forum. Tous droits réservés.
FAQ   Contact