Les calculatrices ne sont pas autorisées.

Le sujet porte sur la résolution de systèmes d'équations linéaires dans les entiers. La première partie traite de la résolution d'une équation dans . La seconde partie étudie la résolution d'un système d'équations dans . La troisième partie porte sur le nombre de Frobenius. La quatrième et dernière partie est consacrée à l'étude d'une borne inférieure sur le nombre de Frobenius. Les quatre parties sont largement indépendantes. En particulier, la deuxième partie est indépendante des autres.

L'usage des calculatrices est interdit.

représente l'ensemble des entiers relatifs, l'ensemble des entiers positifs, l'ensemble des entiers strictement positifs et l'ensemble des réels. Soient des entiers relatifs, non nul. On dit que divise a s'il existe tel que . Le plus grand diviseur commun de et , noté est l'entier tel que divise et divise et tel que pour tout diviseur de et divise . Plus généralement, étant donnés , le plus grand diviseur commun des , noté est l'entier tel que divise chacun des , et tel que pour tout diviseur de chacun des divise .

Si est une matrice de taille , le coefficient ( ), où est l'indice de ligne et l'indice de colonne, , de la matrice est noté . Si est un vecteur de taille , la ème coordonnée de , est notée . La matrice identité de taille est notée . Une matrice de taille pourra être appelée vecteur même si ses coefficients ne sont pas dans un corps.

Si et sont deux ensembles, on note l'ensemble formé de privé des éléments de .
Algorithmes : certaines questions demandent de donner un algorithme. Pour ces questions, on ne demande pas de fournir du pseudo-code mais de décrire l'algorithme en français. La question 2.5 illustre une présentation possible.

Étant donnés deux entiers strictement positifs, on appelle reste de la division euclidienne de a par , noté l'entier tel que et pour un certain entier . On rappelle que l'algorithme d'Euclide, permettant de calculer , est défini à l'aide des suites et de la manière suivante :
et

Question 1.1. Soit l'indice tel que .
(a). Montrer que .
(b). Montrer qu'il existe tels que .

Soient des entiers relatifs. On dit que l'équation

a une solution dans s'il existe tels que .
Question 1.2. Soient et . Soit . Montrer que l'équation a une solution dans si et seulement si l'équation a une solution dans . En déduire que a une solution dans si et seulement si divise .

En particulier, l'équation a toujours une solution dans (théorème de Bézout).

Question 1.3. Proposer un algorithme qui prend en entrée une équation et renvoie :

On supposera donnée une fonction qui prend en entrée deux entiers et qui renvoie tels que et .

Question 1.4. Trouver une solution dans de l'équation .

Soit une matrice de taille à coefficients dans . L'ensemble des solutions dans de l'équation , noté , est l'ensemble des vecteurs tels que . Une base de est un ensemble de vecteurs de tel que tout vecteur de s'écrive comme une combinaison linéaire à coefficients entiers positifs d'éléments de la base.

Étant donnés deux vecteurs , on écrit si et seulement si pour tout .
Question 2.1. Montrer que la relation est un ordre sur les vecteurs de .
On considère l'ensemble des solutions non nulles dans de l'équation , minimales pour l'ordre , c'est-à-dire

Question 2.2. Montrer que est fini.

Question 2.3. Montrer que est une base de .
Question 2.4. Montrer que toute base de contient .
On s'intéresse à la détermination de . Une contrainte est un triplet formé d'une matrice carrée de taille à coefficients dans , d'une matrice de taille à coefficients dans et d'un ensemble .

La contrainte associée à ( ) est notée . L'ensemble des solutions, noté , d'une contrainte est défini par

Ainsi est l'ensemble des solutions de la contrainte . Par convention, on appellera matrice vide la matrice de taille , notée . L'ensemble des solutions, noté , associé à est défini par

On dit qu'une contrainte est en forme résolue si est la matrice vide. Étant donné un ensemble de contraintes, l'ensemble des solutions de est .

On définit la matrice carrée telle que le coefficient ( ) de vaut 1 si ou si et vaut 0 sinon.

Nous allons étudier un algorithme Transf décrit ci-dessous, qui transforme un ensemble de contraintes en un ensemble de contraintes en forme résolue.

si pour tout est en forme résolue.
Sinon, choisir qui n'est pas en forme résolue. Si les ne sont pas tous de même signe, choisir tels que calculer Transf . Sinon, soit la première ligne de . On peut écrire sous la forme . Soit . Calculer Transf .

Question 2.5. Soit un ensemble fini de contraintes. Montrer que Transf renvoie toujours un résultat en un nombre fini d'étapes.

Question 2.6. Montrer que si est un ensemble de contraintes et alors .

Question 2.7. En déduire un algorithme pour déterminer .
Question 2.8. Soit . Déterminer .

Dans cette partie, on suppose que sont des entiers positifs tels que , . On dit qu'un entier est représentable comme une combinaison linéaire positive de s'il existe des entiers , tels que .

Question 3.1. Soit un entier. Les deux propositions suivantes sont-elles équivalentes? Justifier la réponse.
i) est représentable comme une combinaison linéaire positive de .
ii) divise .

Question 3.2. On suppose . Montrer qu'il existe un entier tel que pour tout entier est représentable comme une combinaison linéaire positive de .

On suppose désormais que . On note le plus grand entier non représentable comme combinaison linéaire positive de . Le nombre est appelé nombre de Frobenius.

Question 3.3. Soient . Soit l'ensemble des entiers représentables comme une combinaison linéaire positive de et .
(a). Montrer que .
(b). Montrer que pour tout entier , il existe et tel que et .
(c). Montrer que pour tout entier .
(d). En déduire que le nombre de Frobenius associé à et est .

Soient . On dit que est congru à modulo , noté , s'il existe tel que .

Question 3.4. Soient des entiers positifs. Pour tout , on définit le plus petit entier positif congru à modulo et représentable comme une combinaison linéaire positive de . Montrer que

Si et sont deux parties de , l'ensemble est l'ensemble des avec et . Si est un réel, est l'ensemble des . S'il existe un réel positif tel que , on définit le rayon couvrant de par rapport à par

On considère et et et .
Question 3.5. Montrer que .
Question 3.6. Montrer que existe et que .
Question 3.7. Montrer que est le plus petit réel positif tel que contienne .

Question 3.8. Montrer que .

On considère et des entiers strictement positifs. Le dénumérant est le nombre de solutions dans de l'équation , c'est-à-dire le cardinal de l'ensemble

On considère la fonction définie par

Question 4.1. Montrer que est développable en série entière et que son développement est .

Question 4.2. Donner une formule explicite pour .
On suppose désormais fixés des entiers strictement positifs.
Étant donnés , on considère le rectangle -dimensionnel formé de l'ensemble des points tels que . Étant donné , on considère la pyramide formée de l'ensemble des vecteurs tels que .
Question 4.3. Montrer que .
On définit , le nombre de solutions dans de l'inégalité .

On pose et .
Question 4.4. Montrer que .
On pose .
Question 4.5. On considère la fonction définie par . Montrer que .

Question 4.6. Montrer que .

Fin de l'épreuve.