équations dans N^3

Et pour $3x+2y+5z=133$?

[size=x-small]Bon allez j'essaie celle de meu:

3x+2y+5z=133

mod 2 -->x+z=1 so x+z=2t+1

2x+2y+4z+2t+1=133 /+/ x+z=2t+1

2(x+z)+2y+2z+2t+1=133 /+/...

6t+2y+2z=130 /+/...

(3t+y+z)=65 /+/...

ca chauffe la... un multiple de 13


try modulo 3:

y+z=2 so y+z=3a+2

3t+3a+2=65 /+/......./+/.......

hé hé 3(t+a)=63<---> t+a=21


lol après je sais plus quoi faire, ai l'impression que on remonte à une solution à partir de 2 nombres tels que t+a=21 et les "....":="y+z=3a+2 et x+z=2t+1" via

pick a, x comme on veut; puis pick t:=21-a; puis pick z:=2t+1-x; puis pick y:=3a+2-z etc etc[/size]

La méthode de Nicolas Patrois marcherait moins bien avec $3x+2y-5z=133$.

On peut essayer une autre méthode, qui donne le résultat à tous les coups (pas seulement pour une équation, mais même pour un système d'équations), et pour laquelle on n'a absolument pas besoin d'astuce. Cette méthode est si bête qu'on peut l'apprendre à un ordinateur.

On a donc à résoudre $3x+2y+5z=133$ en entiers (on se restreindra après aux entiers naturels). C'est une équation linéaire qu'on peut écrire matriciellement $A\,X=133$, avec $A=(3\ 2\ 5)$ et $X$ le vecteur colonne des inconnues.

Comment résout-on un système linéaire ? En échelonnant la matrice du système. Mais ici on va échelonner la matrice $A$ suivant les colonnes. On procède par opérations élémentaires sur les colonnes, en retenant bien la leçon de papa Euclide : toujours retirer le plus petit du plus grand, jusqu'à ce qu'il ne reste plus que le pgcd. Allons-y
\begin{center}
\begin{tabular}{c|c}
\rule[-8mm]{0mm}{19mm}$\left(\begin{array}{rrr} 3&2&5\end{array}\right)$&$\left(\begin{array}{rrr} 1&0&0\\ 0&1&0\\ 0&0&1\end{array}\right)$\\ \hline
\rule[-8mm]{0mm}{19mm}$\left(\begin{array}{rrr} 1&2&1\end{array}\right)$&$\left(\begin{array}{rrr} 1&0&0\\ -1&1&-2\\ 0&0&1\end{array}\right)$\\ \hline
\rule[-8mm]{0mm}{19mm}$\left(\begin{array}{rrr} 1&0&0\end{array}\right)$&$\left(\begin{array}{rrr} 1&-2&-1\\ -1&3&-1\\ 0&0&1\end{array}\right) = R$
\end{tabular}
\end{center}
La matrice $A$ a été échelonnée suivant les colonnes en deux étapes :
1e étape : retirer $C_2$ de $C_1$ et $2C_2$ de $C_3$
2e étape : retirer $2C_1$ de $C_2$ et $C_1$ de $C_3$.
\`A droite, on a gardé la trace des opérations élémentaires sur les colonnes dans une matrice $3\times 3$. La matrice $R$ est une matrice inversible sur les entiers telle que $A\,R= (1\ 0\ 0)$.

Faisons le changement de variables $X=R\,X'$ (pas de problème, on peut passer dans l'autre sens, $R$ est inversible sur les entiers). L'équation devient $A\,R\,X'=133$, soit $ (1\ 0\ 0) X'=133$, c.-à-d. $x' + 0\,y'+ 0\,z'= 133$. Cette équation est vachement simple à résoudre en entiers : $x'=133,\ y'=\lambda,\ z'=\mu$ où $\lambda$ et $\mu$ sont des entiers quelconques.

On revient en $X$ en multipliant par la matrice $R$, pour obtenir que les solutions entières de $3x+2y+5z=133$ sont
$$(x=133-2\lambda-\mu,\ y=-133 +3\lambda -\mu, z = \mu)\;,$$
où $\lambda$ et $\mu$ sont des entiers quelconques. Pour les solutions en entiers naturels, on prend bien sûr
$$\mu\geq 0, \ (133+\mu)/3 \leq\lambda \leq (133-\mu)/2\;.$$

X:-( C'est sûr que c'est plus classe déjà comme ça... Si on avait à résoudre un Bézout $a_1x_1+...+a_nx_n=1$ avec ça, on obtiendrait un matrice R avec ARX'=1 et AR serait "simple" (mais jusqu'en quel point le serait-elle?) et à priori on "verrait" si les $a_i$ sont premiers entre eux, ah bah voui.... effectivement

Qu'est-ce qu'on peut obtenir de mieux comme AR? (voyons voir en divisant $a_1$ par $a_8$ par exemple, on obtient $a_1=qa_8+r$ et en retranchant $q$ fois la colonne 8 à la première, on obtient $a'_1=r$ et quelque chose descend ou devient nul). On peut donc supposer que l'un des coef divise tous les autres et recommencer avec les autres. (Ca marche aussi avec des matrices ayant plusieurs lignes, à priori, suffit de faire descendre AU MOINS un truc à chaque fois). S'il n'y a qu'une ligne, c'est seulement quand il ne reste qu'un seul coef non nul au plus qu'on ne peut plus simplifer... Ah ouais, c'est assez superbe comme efficacité (lol et c'est encore de l'exploitation de Euclide (voir fil sur le Samuel), sacrée bonhomme quand-même celui-là, pour son époque, il devait sacrément planant comme gars quand ses postes lui rendaient visite). A la fin, on obtient forcément un truc du genre $AR=(0;0;...;b;...;0)$

En plus ce qui est bien dans ton truc, meu, c'est qu'il n'y a pas à "inverser" la matrice R (lol pour qui n'aiment pas les calculs c'est agréable), elle est juste un "passeport" déontologique (pour pouvoir dire qu'on a trouvé toutes les solutions; ie que toute solution AX=demande est de la forme X=RX', avec X'=R'X, où R' est l'inverse de R et bien sûr, X' sol du truc simplifié..)

lol, en fait on tombe sur le fait que les systèmes ne contenant que des équations de la forme:

$AX+c=(BX)^2$ où il n'y a qu'une seule inconue $X$ uplet de nombres entiers (les A,B) étant des matrices lignes,

sont indécidables et on n'a rien gagné (sans s'y connaitre en formes quadratiques...)

.

.

Maple trouve bien 317 comme coefficient de $X^{133}$ dans $\dfrac{1}{(1-X^2)(1-X^3)(1-X^5)}$.

Voilà le livre dont je parle

http://www.amazon.fr/Léquation-diophantienne-du-second-degré/dp/2705614303

Oui, $\dfrac{1}{1-a}=1+a+a^2+a^3+\cdots$ et développer.

Merci à vous 2, il se trouve que j'ai installé une vieille version de mapple il y a longtemps, et jamais eu la patience d'apprendre à m'en servir, ce sera une occasion d'essayer...

.

Bonjour Borde,

il y a une ambiguité qui s'est glissée dans votre échange: on ne sait si tu parles du degré1 ou du degré quelconque, parce que tu as dit "il n'existe pas de méthode générale" ou un truc dans le genre. L'ambiguité est que tu sembles dire que "même" au degré1 le problème est difficile (avec une seule équation), mais tu pensais peut-être plus généralement en fait.

Par ailleurs, il y a une ambiguité sur la classe de problème: est-ce "répondre oui ou non à chaque question, étant donné $(a_1;...;a_n,b)$, existe-t-il des entiers $x_i$ tels que la somme des $a_ix_i$ vaut $b$?" (1) ou est-ce fair plus?(2) (Les trouver toutes, les compter, etc)

Bien que je sois ignare dans le domaine, la réponse à (1) (dans $\Z$) me semble être "oui quand le pgcd des $a_i$ divise $b$, et sinon, non. Peut-être que ça change tout quand on est dans $\N$?

Ou peut-être discutez-vous de (2)?

Cette méthode (ce n'est pas la mienne!) fonctionne bien pour tout système linéaire sur les entiers. Comme tu l'as vu, l'échelonnement n'est rien d'autre que la réduction de Hermite (en fait, pas poussée au bout). On peut trouver une analyse de complexité de la réduction de Hermite ici.

Pour une seule équation linéaire, la méthode est simplement l'algorithme d'Euclide. On fait difficilement plus praticable.

Sincèrement, j'aimerais que tu ne te défiles pas et que tu expliques ce que tu veux dire par
"'il n'y a pas de méthode universelle pour la résolution de ce type d'équations diophantiennes dès que le nombre d'inconnues dépasse 3"
CC en a fait une exégèse où il sort du cadre linéaire pour parler du 10e problème de Hiilbert, mais je ne pense pas que c'était ce que tu avais en tête. Alors, quoi? Est-ce en lien avec le problème résolution en entiers/ résolution en entiers naturels? D'ailleurs, qu'attend-on exactement quand on parle de "résolution en entiers naturels"? En entiers, c'est facile à expliquer : c'est donner une solution particulière et une base du module des solutions du système homogène associé.

Par ailleurs,puis-je me permettre une critique? Je n'apprécie pas trop ta pratique de modifier a posteriori tes messages en effaçant les points sur lesquels je fais des objections. Ca ne facilite pas la compréhension du fil.

.

Que tu aimes polémiquer, c'est ton droit. Personnellement, ça ne m'intéresse pas (tout au moins sur ce forum).

En revanche, je ne suis pas d'accord pour laisser des inexactitudes dans des textes, et qu'ils soient ou non dans des livres ou articles importe peu, c'est le fait que cela soit écrit qui est important.

D'autre part, je trouve que tu t'acharnes beaucoup pour une simple pécadille...

Quant à me traiter de malhonnête, pourquoi pas mais, dans ce cas-là, allons jusqu'au bout : on peut considérer que toutes mes interventions dans ce sujet le sont (malhonnêtes), sauf le premier message qui répond à Jona. Il faut donc les effacer.


Borde.

De Meu
Il y a un lieu pour avoir des textes aussi lisses et parfaits que possible : c'est les livres et les articles

Comme tu y vas... Moui, mais enfin t'es dugenre à quasiment toujours poster des trucs parfaits, donc ça peut mettre la pression, en particulier à un intervenant comme Borde, d'autant, que pour une simple erreur de calcul comme il en arrive des milliards par seconde (de la part de Borde, qui d'ailleurs t'avait demandé si tu étais sûr d'un moins ou d'un plus, je ne sais pas alors que l'étourderie venait de lui semble-t-il), c'est un peu parti en pseudo match, mais je trouve que tu y vas fort sur le coup des corrections post post (olala je suis fier de mon jeu de mot là je n'ai pas vu double), parce qu'à priori, ce n'était pas important (quand une grave erreur de raisonnement ou un grave oubli d'hypothèse est présent, là ouais, tout le monde est de ton avis, mais comme Borde t'a répondu, sur une histoire de 305 au lieu de 317, - ou +, comme à priori le fil a surtout comme utilité pérenne de pouvoir renseigner des gens qui accèderont par google à telle ou telle formule, dans le présent cas, ça ne me choque pas de corriger, tout le monde le fait

(et parce que j'aime bien polémiquer, ça met un peu de piment, non)

effectivement... Par contre, venant ici depuis longtempts, je ne crois pas que ce soit un plaisir pour Borde de polémiquer. Je l'ai rarement vu participer longuement à des discussions ludiques et des échanges de nature "prouveur-sceptique" ou dialectique et je le crois plus volontiers motivé par une volonté de donner une info quand il peut, particulièrement dans le domaine artihmétique dont il se manifeste spécialiste aux autres intervenants et tout particulièrement les addictionnés à l'arithmétique, contrairement à toi qui semble souhaiter exceller (et qui excelle) et le manifeste dans toutes les questions d'agreg, (là c'en était une, car au fond, c'était bien une application des modules sur les anneaux principaux à IZ) où tu postes de complets et articulés "cours latex" parfaitement rédigés et calibrés

je trouve à la limite de la malhonnêteté vis à vis des autres intervenants d'effacer purement et simplement les passages qui ont justement prêté à discussion

oui, mais après il y a le degré... déjà évoqué ci-dessus...

Sincèrement, j'aimerais que tu ne te défiles pas(***) et que tu expliques ce que tu veux dire par
"'il n'y a pas de méthode universelle pour la résolution de ce type d'équations diophantiennes dès que le nombre d'inconnues dépasse 3" (****)
Alors, quoi?

*** est quand-même limite une phrase du genre "viens dans l'arêne te battre". Certes, c'est subtil, mais étais-tu vraiment en quête d'une réponse mathématique, très sincèrement, puisque tu avais donné toi-même un algorithme en temps quasi linéaire pour régler toutes les instances, pour un nombre quelconque de variables, de cette classe de problème, ou souhaitais-tu juste voir la réaction ou la pensée de Borde face à ce que tu considérais manifestement comme une erreur
(je suis sûr qu'au fond de toi, tu pensais qu'il avait fait une erreur).

C'est pour ça que comme tu dis j'ai fait "l'exégèse" (il est joli ce mot), parce que je me suis dit que Borde, en allant vite, et habitué à l'indécidabilité de 10e problème de Hilbert, l'ayant vaguement en tête le resignalait à sa manière (volonté de dire: attention avec les entiers!! Rien n'est simple) peut-être un peu vite, sans vraiment avoir réfléchi très exactement au sujet précisprécisprécis du fil, alors que toi tu suivais parfaitement tout depuis le départ et avais bien conscience que ton algo était parfait. Donc es-tu vraiment de bonne foi sur cette histoire d'insistance (je veux dire étais-tu vraiment sincère dans ton attente d'une impropable obstruction potentielle que pourrait présenter Borde à l'algo Hermite, ou avais-tu juste envie de te le payer pour le plaisir?


Je n'apprécie pas trop ta pratique de modifier a posteriori tes messages en effaçant les points sur lesquels je fais des objections



comme tu y vas... lol bon bin j'ai tout dit. En résumé, je ne suis pas certain que Borde goute avec plaisir à ce jeu des duels d'arguments (chacun son truc, je trouve très bien aussi que toi tu les goutes, ce n'est pas une critique), mais un truc auquel tu ne penses peut-être pas c'est que tu peux raréfier les infos que donnent les spécialistes d'un sujet s'ils doivent craindre ta perfection polémique. On a aussi à gagner sur un forum que les gens s'y promènent tranquillement, survolent quelques fils, postent quelques infos rapidement, et n'aient pas à se soucier d'être repris par un formateur agreg qui ne postent que des textes parfaits et montre sa compétence dans ce programme.

Qu'il n'y ait pas de malentendu, je ne prends pas parti ici, simplement ta phrase Il y a un lieu pour avoir des textes aussi lisses et parfaits que possible : c'est les livres et les articles m'a un peu fait bondir quand on voit tous tes posts qui sont systématiquement parfaits,et même le plus souvent EN PLUS très pédagogiques, et que tu l'utilises comme argument retourné. D'autant que je "sentais" (quand tu as demandé à Borde de préciser (****) que tu tenais là une occasion de t'amuser et que tu ne lacherais pas l'affaire lol

lol, si Borde était comme moi, jmenfoutiste, peut-être qu'il s'en foutrait, mais bon il est surement plus pudique que moi, et je ne me choque pas du tout qu'il ait modifié son erreur de calcul. C'est comme quand même moi je remodifie tous mes messages 15 fois pour chasser les "et" qui devraient être des "est" car curieusement, de ce genre de fautes, j'ai un peu honte, c'est tout

Bonjour Borde,

J'envisage d'acheter ton bouquin, dont les mathematonautes disent beaucoup de bien, mais je ne trouve pas la table des matières sur le net, et j'aimerais ne pas acheter chat en poche. Peux tu nous la donner ? (je pense que ça peux en intéresser d'autres, c'est pour ça que je n'ai pas fait un MP)

Amicalement,

Vous habitez dans la même ville ou toutes les BU du monde ferment à 16H????

Merci d'avoir laissée la superformule que j'ai comprise (je suis tout fier, j'ai compris de A à Z) un calcul, ça me fait plaisir..

Je l'immortalise (lol c'est un hold up, mais chez moi je n'ai pas de compilateur tex)

De Borde:

Bonjour CC,

Les séries génératrices de suites sont certainement l'un des outils les plus utilisés en analyse combinatoire, car ces séries contiennent les informations de ces suites.

Comme l'a dit Meu, la série génératrice du dénumérant $D(n,k)$ de l'équation diophantienne $a_1 x_1 + \dotsb + a_k x_k = n$ (i.e. le nombre de solutions dans $\N^k$) est donnée formellement par $\displaystyle {F(t) = \prod_{j=1}^{k} \left (1-t^{a_j} \right )^{-1}}$. L'analyse complexe permet alors d'extraire les informations souhaitées. Par exemple, si les $a_i$ sont premiers entre eux dans leur ensemble (ce qui n'est pas trop dur à avoir dans ce type d'équation), alors lorsque $t \rightarrow 1^-$, on a

$$F(t) \sim \frac{1}{\prod_{j=1}^{k} a_j} \times \frac{1}{(1-t)^k}$$

et un théorème de transfert permet alors d'en déduire que $D(n,k)$, qui est le coefficient de $t^n$ dans $F(t)$, vérifie lorsque $n \rightarrow \infty$

$$D(n,k) \sim \frac{n^{k-1}}{(k-1)! \prod_{j=1}^{k} a_j}.$$


Borde.

Bin oui, mais j'ai eu vraiment un doute sur ta sincérité quand j'ai vu la suite de l'échange, cependant, pour te dire à quel point quand-même je te faisais confiance, quant tu as réinsisté, j'ai pris la parti de la sincérité, ça m'avait aussi mis un doute cette histoire de $\Z vs \N$ et j'ai même moi-même reposer un peu la question, mais sans mettre de "défi" dans mon style, mais avec l'algorithme qui donne EXACTEMENT le nombre de solutions, difficile de continuer de douter de la décidabilité (même de la facilité) du problème

Par ailleurs, Borde a parfaitement expliqué que justement, cette histoire $\Z vs \N$, d'après son expérience reste problématique en pratique, d'où son invitation aux congruences, etc..

Mais bon, le fil est parti dans une direction moins maitrisable... Enfin, on a quand-même toutes les réponses, les plus générales aux questions qu'on pouvait se poser grace à vous 2 (2 algorithmes, une formule pour calculer, très simple (vu que je la comprends) et par ailleurs on sait que dès qu'on multiplie 2 inconnues ça devient inextricable très vite (Matiasevic)...

Je reviens aussi au "nombre de solution" et à leur importance.

Il existe (Matiasevic) des équations diophantiennes universelles (auxquelles se réduisent toutes les autres).

Pour ce genre de problème, je précise pour les gens qui voient ça "de loin" comment "l'indécidabilité" est marrante: admettons que pour tout entier $k$ on connaisse "décidablement" le nombre f(k) d'équations de pas plus que k symboles qui ont des solutions (donc avec une universelle, le mot "équation peut être remplacé par "paramètre").

Voici comment on peut rendre décidable toutes les équations: soit e une équation avec k symboles et p:=le nombre f(k): on fait défiler tous les entiers, et à chaque fois qu'on trouve une solution à une équation de pas plus que k symboles on augment un compteur de 1. Tant qu'on n'a pas atteint p, on sait qu'il en reste qui ont des solutions. Dès qu'on atteint p, c'est fini, on est tranquille. On regarde alors si e a été solutionné pendant la recherche.

de bs:

notre incontournable viagra m'a conseillé d'aller voir un psy

non, le pseudo "freud" ne fait pas partie de la liste de pseudos utilisés par vi@gra

@bs

La force brute :