Home

MPSI/PCSI

Maths

Algèbre

Divisibilité et division euclidienne

Dans cet exercice, on cherche à démontrer l'existence et l'unicité d'une base B telle que tout entier naturel n puisse être décomposé de manière unique sous la forme d'une somme de coefficients multipliés par des puissances de B.

Pour démontrer l'existence, on utilise une récurrence forte. On suppose que la propriété P(n) est vraie pour tout entier k plus petit que n, et on montre que P(n+1) est aussi vraie. On distingue deux cas : si n+1 est strictement plus petit que B, alors n+1 peut être écrit sous la forme d'une somme avec un seul coefficient, qui est n+1 lui-même. Si n+1 est supérieur ou égal à B, on utilise la division euclidienne pour écrire n+1 sous la forme de BQ + R, où Q est plus petit que n et R est entre 0 et B-1. On utilise ensuite l'hypothèse de ré

Salut ! Dans cet exercice, on va montrer l'existence d'une base B. En fait, l'unicité et l'existence d'une base B, ça veut dire qu'en gros, n'importe quel entier naturel n, on peut le décomposer de manière unique sous cette forme-là. Donc la somme de k égale 0 à P de certains coefficients ak fois B puissance k. Donc c'est ce qu'on appelle une base B, tout simplement. Alors, on va commencer avec l'existence. Donc, on nous dit, il faut démontrer l'existence en procédant par une récurrence forte. Donc une récurrence forte, c'est au lieu de dire, on suppose que c'est vrai pour n, et on regarde si c'est vrai pour n plus 1, donc à l'hérédité. On va dire, on suppose que c'est vrai, pour tout le k plus petit que n, et on va montrer que c'est vrai pour n plus 1. Donc c'est parti. Montrons du coup. Alors la propriété P de n qu'on va créer, c'est de dire qu'il existe un P positif, et il existe P plus un nombre, donc a0, a1, etc. jusqu'à ap. Qui sont tous, respectivement, dans l'ensemble 0, 1, 2, 3, jusqu'à B-1. Tel que n peut s'écrire comme la somme de k égale 0 à P de ak B puissance k. Donc ça, c'est ce qu'on va montrer. Donc on va le montrer par récurrence, comme on disait. Alors si n est égal à 1, ben 1, c'est 1 fois B puissance 0, donc c'est vrai, d'accord ? Ici, on n'a pas à se casser la tête. C'est tout simplement l'écriture assez simple à avoir. 1 fois B puissance 0, tout simplement. Alors maintenant, on suppose, comme je disais, que P de 1, P de 2, P de 3, etc. jusqu'à P de n sont toutes vraies, d'accord ? Toutes ces propriétés sont vraies. Et on va montrer que la propriété au rang n plus 1, elle est vraie aussi. Donc là, on va séparer la situation en deux cas de figure. Si n plus 1 est strictement plus petit que B, alors ce qu'on fait, c'est qu'on écrit n plus 1, c'est n plus 1 fois B puissance 0, un peu comme on l'a fait avec 1. Et là, c'est fini, d'accord ? Là, c'est fini, parce que n plus 1 joue le rôle de A0, et donc, on peut l'écrire de la forme, la somme, du coup, le cas, c'est juste 0, de A0 fois B puissance 0. Donc voilà, P égale 0, et A0, c'est n plus 1. Maintenant, le cas qui est un peu intéressant, si n plus 1 est supérieur ou égal à B. Donc là, on nous a donné l'indication, c'est d'utiliser la division euclidienne. Donc ce qu'on fait, c'est la division euclidienne de n plus 1 par B, donc c'est BQ plus R, du coup. La seule condition qu'on connaît, c'est que R, il est entre 0, il peut être égal à 0, entre 0 et B, mais strictement plus petit que B. Étant donné que B est supérieur ou égal à 2, Q va être plus petit que n, parce que sinon, là, B fois Q, on dépasserait n, tout simplement. Alors, d'après l'hypothèse de récurrence, on va prendre P plus 1, coefficient a, 0, enfin a, i, tout simplement, et on va faire l'écriture avec Q, parce que Q est plus petit que n. Donc on utilise la propriété, du coup, on va dire la propriété P de Q est vraie, donc on écrit Q comme étant la somme de k égale 0 à P de ak, B puissance k. Donc maintenant, BQ plus R s'écrit comme ça, d'accord ? On a juste multiplié cette somme par B, parce que le B, on peut le mettre là, mais sinon on le rajoute, on le distribue dans la somme, et on a juste à rajouter un petit plus 1 ici, qu'on a fait ici, donc le plus R, on le remet. Et donc finalement, le R, on va l'intégrer à la somme, mais en faisant des petits décalages d'indices, parce que le R, on ne peut pas l'intégrer juste comme ça, il faut que la somme, on voit bien les bons indices à chaque fois. Donc ce qu'on va faire, c'est on va faire P', donc le nouveau nombre, là où on s'arrête, le nouveau nombre de coefficients qu'on va avoir, c'est P plus 1, et on va voir pourquoi on fait ça, P' c'est P plus 1, et les ak, du coup, ce sera, donc on va prendre les ak', qui vont être égaux respectivement à ak moins 1, pour k qui va de 1 à P'. Parce qu'en fait, en faisant cette construction-là, on n'a pas de coefficients constants, ça veut dire que la puissance de B n'est jamais 0, donc il y a toujours du B. C'est normal, parce qu'on a multiplié tout ça par B. Donc, finalement, le R va être un peu notre A0, et donc on va décaler tout le reste en faisant cette transformation-là, et A'0, du coup, comme je disais, c'est R. Et en faisant ça, du coup, Pn plus 1, elle est vraie. Parce que là, il ne faut pas oublier que ce qu'on était en train d'écrire, c'est n plus 1, et on a montré qu'on peut écrire n plus 1 comme la somme de k égale 0 à P', du coup, de A'k fois B puissance k. Donc, voilà pour la récurrence. Ensuite, dans la deuxième question, on nous disait, on va montrer l'unicité, alors là, c'est un peu plus compliqué de montrer l'unicité, on va voir ce qu'on nous demande de faire. Donc, on nous dit, il existe deux décompositions distinctes, voilà, c'est les mêmes, mais juste on rajoute des primes ici, et là. Ensuite, on nous dit, quitte à compléter la suite par d'autres nombres, on va supposer qu'il y en a autant, d'accord ? On va supposer que P' et P, c'est les mêmes, et que du coup, il y a autant de coefficients, quitte à ce qu'ils soient nuls, c'est pas grave, on veut qu'il y en ait autant pour pouvoir les comparer respectivement avec leurs indices. Et on va noter L, c'est le plus petit indice, on va dire, pardon, le plus grand indice, tel que les AL sont pas différents. Donc ça veut dire en gros que s'il y a un nombre K qui est plus grand que L, mais du coup plus petit que P, AK est égal à AK'. C'est ça qu'on nous dit avec la construction de L. Ok ? Très bien, maintenant on a compris un peu ce qu'il en est. On veut montrer maintenant cette égalité-là. Mais là, en fait, il y a juste à écrire et on voit tout de suite ce qui se passe. Donc, on va utiliser ce qu'on sait sur L. L'hypothèse nous dit déjà qu'on a les deux mêmes écritures, et d'après la définition de L, on a que A'L'1 c'est égal à A'L'1, etc., la même chose jusqu'à P, donc que AP est égal à A'P'. Mais bon, P est égal à P', donc voilà, on a pris tous les coefficients parce qu'il y en a autant. Et donc, on va réécrire les deux sommes en utilisant le L. On fait une séparation au moment du L. On fait tout ce qui est jusqu'à L et tout ce qui est après L. Donc tout ce qui est jusqu'à L, c'est là, et de l'autre côté c'est ici, et tout ce qui est après L, ce sont ces parties-là. Mais vu que c'est les mêmes coefficients et qu'il y en a autant, on a écrit la même chose. Donc on va simplifier par ces coefficients. Donc finalement, on a que la somme de K'0 à L des AK B'K, c'est la somme de K'0 à L des A'K B'K. Et là, ce qu'on fait, si on va prendre juste les derniers termes de la somme, donc on va écrire la somme qui s'arrête à L-1 et le dernier terme on le sépare, on fait pareil pour l'autre, et on va passer toutes les sommes à droite, tous les derniers termes qu'on a extraits, on les passe à gauche, et on factorise du coup à gauche par B, par B puissance L, donc ça nous fait AL moins AL' fois B puissance L, et à droite, donc on a cette somme-là moins cette somme-là, qu'on a passée de l'autre côté, et on met tout sous une même somme, et on factorise par B puissance K dans ce qui est la somme, et on a bien la somme de K égale 0 à L-1 de A' K moins AK fois B puissance K. Il faut bien faire gaffe que l'ordre, ce n'est pas le même ici et là. Là, c'est celui-là qu'on a passé de l'autre côté, donc on aura moins AK, et ici, on a passé celui-là de l'autre côté, donc on aura moins A' L. Donc, voilà pour cette question. Ensuite, on nous dit, démontrer que pour toute suite finie, C0, C1, C2, etc., jusqu'à CL-1, avec tous les CK qui sont entre 0 et B-1, on a que, du coup, leur écriture de cette façon-là, donc la somme des CK fois B puissance K, donc qui va de 0 à L-1, ça c'est plus petit que B puissance L. Bon, là, encore une fois, il suffit juste d'écrire pour voir ce qui se passe. Donc, la somme de ces CK, on va majorer chacun des CK par B-1, parce qu'étant donné que chacun des CK est entre 0 et B-1, on majore chacun des CK par B-1, et donc on se retrouve avec cette somme-là. Et donc cette somme-là, en fait, on va sortir B-1 de l'autre côté, parce qu'il ne dépend pas de le cas, tout simplement, c'est juste une constante multiplicative, on la met devant la somme, et on se retrouve avec ça. Alors là, je fais un rappel juste après, mais il faut reconnaître, il faut reconnaître que cette somme-là, ce n'est pas rien, ça va être B puissance L-1, parce que, voilà, le petit rappel il est là, X puissance N plus 1 moins 1, c'est X-1 fois X puissance N plus 1, plus etc., plus X plus 1. Donc, ça c'est quelque chose qu'il faut savoir, il faut savoir le reconnaître dans les deux sens, il faut savoir que ça, ça nous fait X puissance N plus 1 moins 1, et il faut savoir décomposer X puissance N plus 1 moins 1 en produits comme ça, de deux polynômes, dont X moins 1 qui est ici, souvent ça aide, voilà, mais on ne va pas s'attarder là-dessus. Donc ici, on reconnaît cette forme-là, alors c'est sous forme de somme, ce n'est pas détaillé comme ça, mais c'est sous forme d'une somme, mais on le reconnaît quand même, c'est une somme de puissance qui commence, les puissances commencent à zéro et s'arrêtent à L-1, donc finalement quand on multiplie par B-1, on est à une puissance de plus que L-1, donc ça veut dire qu'on est à B puissance L-1, ici qu'on retrouve là. Et B puissance L-1, c'est plus petit que B puissance L, donc finalement, parce qu'on n'oublie pas qu'on était dans cette inégalité-là, on a trouvé que ça, c'était plus petit que B puissance L, donc finalement on a bien que la somme des CK B puissance K pour K qui va de 0 à L-1, c'est strictement plus petit que B puissance L. Et dans la dernière question, finalement, on nous demande de conclure, alors de conclure sur quoi ? De conclure sur l'unicité, on nous a fait montrer des égalités et une inégalité, et bien en fait, il faut conclure sur l'unicité. Donc on va voir qu'il y a une contradiction quelque part. En fait, là, ce qu'il faut se dire, on va dire, pour savoir vers où partir, là on nous dit qu'on a une égalité, là, c'est pas anodin, on a une inégalité stricte. Donc on va essayer de mettre ces deux-là un peu sous cette forme-là, en passant par les CK, pour avoir une inégalité stricte, mais qui finalement devrait être une égalité, d'après cette question-là. Donc c'est ça qu'on va faire. Donc là, on va poser, où est-ce que j'en suis ? On va poser ici, on va poser les CK comme étant valeur absolue de AK-AK'. Donc pour K qui va de 0 à L-1. Donc là, on a nos CK. Donc les AL et AL', il y en a un des deux qui va être plus grand que l'autre. On peut supposer que c'est celui-là qui va être plus grand, sans perdre de généralité, sinon on inverse, on dit que c'est l'autre, et du coup on inverse dans les résultats. Et donc là, on a notre inégalité, alors je l'explique. Ça, c'est l'inégalité qu'on a dans la question 2. Ça veut dire que c'est la somme des CK B puissance K, pour K qui va jusqu'à L-1, qui est plus petit, strictement, que B puissance L. Voilà, ça c'est la question 2. Cette partie-là, c'est tout simplement l'inégalité triangulaire. En gros, la valeur absolue de la somme, c'est plus petit que la somme des valeurs absolues d'une certaine quantité. Donc ça, c'est l'inégalité triangulaire. Et ça, c'est tout simplement, étant donné que AL' est plus grand que AL, cette quantité-là va être plus grande que 1, donc ce truc-là est plus grand que B puissance L. Alors, maintenant, où est la contradiction ? En fait, la contradiction, elle vient du fait que ça, ce qui est dans la valeur absolue, c'est égal à ça d'après la question 1. Ce sont les deux égalités, enfin, pardon, ce sont les deux quantités dont on a montré qu'elles sont égales dans la question 1. Et, étant donné que ici, il y a une inégalité stricte, en fait, c'est ce que je disais tout à l'heure, on a montré que deux choses qui doivent être égales, on a montré que c'est égal, sont dans une inégalité stricte, donc finalement, elles ne sont pas égales. Donc ça, c'est une contradiction, ça contredit la question 2.1, donc finalement, on a bien l'unicité. C'est-à-dire que les quantités sont toutes les deux égales, parce qu'en fait, ce qui contredit c'est l'existence du L. Ce qui contredit, c'est l'existence de ce L-là, parce que étant donné que on a l'unicité, parce que ce L-là, en fait, n'existe pas, tous les AK vont être égaux.

Ecriture en base

RELATED

Recommended videos

Carré parfait

Divisibilité

Division euclidienne