par nodgim » 18 Juil 2018, 08:54
Soit a > b > c et k , j, l entiers naturels. a,b,c premiers > 2.
Problème : quel est le + grand nombre qu'on ne peut pas écrire sous la forme ka + jb + lc ?
Idée : Chercher les c plus petites valeurs réelles de ka+jb telles qu'il n'y a pas 2 valeurs identiques modulo c. La plus grande d'entre elles est le nombre recherché.
On construit un tableau de c*c cases, en 1ère ligne : 0, a, 2a, ....(c-1)a et en 1ère colonne 0, b, 2b,...(c-1)b, Les autres cases étant remplies par l'addition case de 1ère ligne + case de 1ère colonne.
On appelle R(x,y) la valeur réelle dans la case (x,y) et C(x,y) sa valeur modulo c.
Vu qu'il existe c² résultats pour c valeurs modulo c, il y a des doublons.
Soit C(x,y) = C(x+x1, y+y1) avec R(x,y) < R(x+x1,y+y1)
Si C(x,y) = C(x+x1, y+y1) [c] alors pour toute autre case (x',y') : C( x' , y' ) = C(x'+x1, y'+y1) et R(x',y') < R(x'+x1,y'+y1).
Vu la propriété, on peut dire que (x1,y1) est un vecteur recopie. Il existe dans le cas général 3 types de vecteurs recopie, selon le signe de (x1,y1) : VR(+ +), VR(+ -), VR(- +)
Il existe donc R(x'',y'') min telle que R(x>=x''+x1, y>=y"+y1) n'est pas une valeur min car C(x>=x''+x1, y>=y"+y1) est doublon.
Si VR(+,+) : C(x",y") = 0, R(x",y") = 0 et (x",y") = (1,1). De plus C(1, 1+y1) = C(1+x1, 1), autrement dit l'un des multiples de a est le complémentaire [c] de l'un des multiples de b.
Si VR(+,-) : x" = 1 et y"+ y1 = 1, autrement dit l'un des multiples de a est l'égal [c] de l'un des multiples de b.
Si VR(-,+) : y" = 1 et x"+ x1 = 1, autrement dit l'un des multiples de a est l'égal [c] de l'un des multiples de b.
Vu ces règles :
L'espace dans le tableau des c cases contenant les c valeurs recherchées est connexe et convexe (convexe : si (x,y) est l'une de ces cases alors les cases ( <= x, <= y) le sont aussi).
On peut même dire qu'il n'a que 2 formes possibles :
-Un rectangle dans un cas particulier;
-Un rectangle dont l'angle à l'intérieur du tableau est découpé par un rectangle (donc au final une forme en L ou en couloir coudé).
Prouvons tout cela.
Soit minVR(+ -) = VR(+ -) pour x min et minVR(- + ) = VR(- +) pour y min.
minVR(+ -) existe toujours étant donné que a > b. Si c'est VR(1,-), Les c plus petites valeurs sont exclusivement dans la 1ère colonne (puisque la seconde est une recopie de la 1ère). C'est le cas particulier évoqué. Dans ce cas là, le nombre "a" est inutile, et le nombre recherché est classiquement bc-b-c. Et donc minVR(- +) = minVR(++) = VR(0 a)
Si min VR(+,-) = VR(>1, -)
Soit (1,y1) origine de minVR(+ -) et (x1,1) sa fin.
Soit (1,y2) origine de minVR(- +) et (x2,1) sa fin.
Alors on a forcément x2 < x1 et y2 > y1. En effet, si tel n'était pas le cas, VR(x2-x1, y2-y1) ou VR(x1-x2, y2-y1) existe et est < minVR.
Du coup, VR (+ +) existe forcément : VR ( -(x2-x1) (y2-y1) )
Il ne peut pas y avoir 2 VR (++) dans le rectangle délimité par minVR(- + ) et min VR( + -). Si tel était le cas, comme les valeurs [c] dans ces 2 cases supposées sont 0, on créerait immédiatement un VR(+ - ) ou VR (- + ) < min VR.
La recherche des minVR(+ -) minVR(- +) et VR(+ + ) se fait en partant par exemple du 1er multiple de b et du multiple correspondant (même valeur [c] ) de a. La valeur réelle du 1er multiple de b est normalement inférieure au multiple correspondant de a. On cherche alors, en partant du 1er, le plus petit multiple de b qui va être supérieur au multiple de a correspondant. C'est à la transition qu'on trouve le triplet de valeurs recherchées. La valeur max est forcément dans l'une des 2 cases d'angle rentrant de la figure,dont les coordonnées sont données par le triplet trouvé.