Cours de Arithmétique dans Z en Ligne par les Meilleurs Professeurs - Arithmétique dans Z

Carré parfait

Dans cet exercice, nous souhaitons démontrer que le produit de 4 entiers consécutifs augmentés de 1 est un carré parfait. Pour ce faire, nous allons réécrire cette consigne de manière algébrique. Nous posons le but de montrer l'existence d'un cas appartenant à n, un entier naturel, tel que le produit des 4 entiers consécutifs (n x (n+1) x (n+2) x (n+3)), augmenté de 1, est égal à k², où k est un autre nombre au carré. En développant cette expression, nous obtenons n⁴ + 6n³ + 11n² + 6n + 1, qui contient 5 termes. Sachant qu'une forme de carré parfait a au plus 3 termes après simplification, nous pouvons conclure que ce n'est pas le cas ici. Cependant, nous explorons la possibilité que certains de ces 5 termes soient en réalité 2 termes regroupés. Par exemple, 6n³ pourrait être équivalent à 2n³ + 4n³, de même pour 5n² et 6n². Nous remarquons que ces 5 termes peuvent être écrits comme une triple somme au carré. En identifiant les termes, nous trouvons que le plus grand degré est n⁴, que nous associons à a² (a étant égal à n²). Le plus petit degré, équivalent à c², est 1, ce qui signifie que c est égal à 1. Maintenant, nous cherchons à identifier les termes avec b. Nous constatons que 6n³ peut être exprimé comme 2ab. Si nous avions choisi 2bc, nous aurions trouvé b = 3n³, ce qui n'est pas possible car n² est le plus grand degré. Finalement, nous trouvons que b est égal à 3n. En réécrivant l'expression initiale en utilisant ces identifications, nous obtenons que le produit des 4 entiers consécutifs augmentés de 1 est égal à (n² + 3n + 1)², ce qui est bien un carré parfait.

Divisibilité

Dans cet exercice, on démontre deux résultats arithmétiques. Tout d'abord, pour tout entier n, on montre que 6 divise 5^n + n. En utilisant les congruences, on montre que ce nombre est divisible par 2 et par 3, donc par 6. Ensuite, on démontre que pour tout entier n, 4^(2^n) + 2^(2^n) + 1 est divisible par 7. En examinant les premières valeurs de n, on constate un motif (4, 2, 4, 2...) qui nous permet de généraliser la propriété par récurrence. Finalement, on conclut en affirmant que pour tout entier n, ces deux propriétés sont vérifiées.

Division euclidienne

Dans cet exercice, on nous demande de déterminer le reste de la division du nombre 96 842 par chacun des nombres 256 et 375. Pour cela, nous utilisons le calcul initial qui nous donne le résultat 96 842 = 256 x 375 + 842. Notons que le reste dans une division euclidienne doit être strictement plus petit que le quotient. Cependant, dans ce cas, 842 n'est pas plus petit que 256 ou 375, ce qui pose problème. Pour résoudre ce problème, nous allons réduire uniquement le chiffre 842. La méthode consiste à faire la division euclidienne de 842 par 256 pour obtenir le quotient 3 et le reste 74. Ensuite, nous faisons la division euclidienne de 842 par 375 pour obtenir le quotient 2 et le reste 92. Cette fois-ci, les conditions de la division euclidienne sont respectées, c'est-à-dire que le reste est plus petit que le quotient dans les deux cas. Nous utilisons ensuite ces résultats pour réécrire l'équation initiale. Ainsi, 96 842 devient 256 x 375 + 375 x 2 + 92. Nous factorisons ces termes par 375 pour obtenir 375 x 258 + 92. Cette nouvelle écriture respecte bien la division euclidienne, car le reste 92 est plus petit que 375. En utilisant la même méthode, en réécrivant l'équation en utilisant cette fois-ci l'écriture pour 842, nous trouvons que 96 842 est égal à 256 x 378 + 74. Le nombre 378 est obtenu en ajoutant 3 fois 256 à 375. Ainsi, le reste de la division euclidienne de 96 842 par 375 est 92, et le reste de la division euclidienne de 96 842 par 256 est 74.

Ecriture en base

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é

Cubes consécutifs

Dans cet exercice, on démontre que la somme de 3 cubes consécutifs est toujours divisible par 9. Pour cela, on utilise les congruences pour simplifier les résultats. On veut montrer que la somme de 3 cubes consécutifs, soit n^3 + (n+1)^3 + (n+2)^3, est congru à 0 modulo 9. En développant cette expression, on obtient 3n^3 + 9n^2 + 15n + 9. On regroupe les termes pour faciliter les calculs et remarquons que le premier terme est déjà divisible par 9. En factorisant le deuxième terme par 3n et le troisième terme par 3, on obtient 9(n^2 + 1)(3n + 5). Il est facile de voir que le terme 9(n^2 +1) est congru à 0 modulo 9 car il est divisible par 9. De plus, le terme 3n + 5 est congru à 0 modulo 3 car il est divisible par 3. Ainsi, nous avons démontré que pour tout n, la somme de 3 cubes consécutifs est divisible par 9.

Congruences avec les puissances

Dans cet exercice, l'objectif est de trouver le reste de la division par 13 du nombre 100 puissance 1000. Pour cela, il est recommandé d'utiliser les congruences plutôt qu'une calculatrice en raison de la taille du nombre. Tout d'abord, on détermine le reste de la division de 100 par 13, qui est 9. Ensuite, au lieu de travailler avec 100, on travaillera avec 9 car ils sont congruents modulo 13. Par exemple, si 100 puissance 4 est congru à 1 modulo 13, alors 9 puissance 4 sera aussi congru à 1 modulo 13. On calcule donc les puissances de 9. On constate que 9 puissance 2 est congru à 3 modulo 13, mais ce n'est pas ce que l'on souhaite. On cherche à trouver une puissance de 9 qui est congru à 1 modulo 13, et on trouve que 9 puissance 3 est congru à 1 modulo 13. Donc la puissance recherchée est 3. On réécrit alors 100 puissance 3 comme congru à 9 puissance 3, qui est congru à 1 modulo 13. Etant donné que 100 puissance 3 est congru à 1 modulo 13, le nouveau diviseur sera 3 cette fois-ci. On effectue donc une division euclidienne de 1000 par 3, ce qui donne 333 avec un reste de 1. On réécrit alors 100 puissance 1000 comme 100 puissance 3 fois 333 plus 1, en utilisant les règles de calcul sur les puissances. Cela devient donc (100 puissance 3) puissance 333 multiplié par 100. Il est important de ne pas se tromper en interprétant cela comme (100 puissance 333) puissance 3, car cela engendrerait une interprétation différente. Ici, on écrit cette expression de cette façon spécifique car on sait que 100 puissance 3 est congru à 1 modulo 13, et que 100 est congru à 9. Ainsi, on peut remplacer 100 par 9 dans l'expression. En considérant que 1 puissance 333 est égal à 1 modulo 13, le calcul final donne que 1 puissance 333 fois 9 est congru à 9 modulo 13. Par conséquent, selon la définition des congruences, le reste de la division euclidienne de 100 puissance 1000 par 13 est égal à 9.

Division de puissances

Dans cet exercice, nous allons montrer que 13 divise 3^126 + 5^126 en utilisant les congruences. Au lieu de montrer que chaque terme est congru à 0 modulo 13, nous allons examiner à quoi chaque terme est congru modulo 13. Pour cela, nous cherchons d'abord une puissance de 3 qui est congrue à 1 modulo 13. Nous trouvons que 3^3 ≡ 1 modulo 13. Ensuite, nous divisons 126 par 3 pour obtenir 42 sans reste. Ainsi, 3^126 = (3^3)^42 ≡ 1^42 ≡ 1 modulo 13. De la même manière, nous cherchons une puissance de 5 qui convient. Nous trouvons que 5^3 ≡ 8 modulo 13. Ensuite, nous divisons 126 par 4 pour obtenir 31 avec un reste de 2. Ainsi, 5^126 = (5^4)^31 * 5^2 ≡ 1^31 * 12 ≡ 12 modulo 13. Finalement, nous avons montré que 3^126 ≡ 1 modulo 13 et 5^126 ≡ 12 modulo 13. Donc, 3^126 + 5^126 ≡ 1 + 12 ≡ 0 modulo 13. Ainsi, nous concluons que 13 divise bien 3^126 + 5^126.

Equation type Fermat

Dans cet exercice, on doit résoudre une équation avec des coefficients entiers. On nous demande de montrer que si n, a et b sont des entiers tels que n est un multiple de 4 et que l'équation n = a² + b² est vérifiée, alors a et b doivent être pairs. Pour prouver cela, on va utiliser une preuve par l'absurde. On suppose d'abord que a et b sont impairs. On peut alors écrire a comme 2k + 1 et b comme 2k' + 1, où k et k' sont des entiers. On développe ensuite l'équation a² + b² et on factorise par 4. On remarque que cela nous donne 4 fois un nombre entier plus 2. Cependant, cela implique que a² + b² est congru à 2 modulo 4, ce qui contredit le fait que n est un multiple de 4. Donc, l'hypothèse selon laquelle a et b sont impairs est fausse. Ensuite, on suppose qu'un des deux nombres a ou b est impair. Nous pouvons supposer sans perte de généralité que c'est a qui est impair et que b est pair. En utilisant le même raisonnement, on arrive à la conclusion que a et b doivent tous les deux être pairs pour que n soit un multiple de 4. En utilisant cette conclusion, on peut également montrer que l'équation 2^(2n) = a² + b² n'a pas de solution. En supposant qu'il existe une solution et en notant n0 le plus petit entier tel que 2^(2n0) = a² + b², on montre de manière contradictoire que cette équation n'a pas de solution en utilisant la minimalité de n0. Enfin, on nous demande de démontrer que l'équation 2^(2n) + 1 = a² + b² a une unique solution. On montre d'abord qu'une solution est donnée par a = b = 2^n en décomposant 2^(2n) + 1 en 2 (2^n)^2. Ensuite, on utilise une preuve par récurrence pour montrer que c'est la seule solution. On suppose que cela est vrai pour un certain rang n et on montre que cela est aussi vrai pour n+1, en utilisant le fait que 2^(2n+3) est un multiple de 4 et en appliquant notre hypothèse de récurrence. Ainsi, on peut conclure que l'équation 2^(2n) + 1 = a² + b² admet une unique solution donnée par a = b = 2^n.

Divisbilté par 7

Dans cet exercice, il s'agit de démontrer que pour tout nombre naturel n, l'expression 3 puissance 2n plus 1 plus 2 puissance 4n plus 2 est divisible par 7. Pour cela, on utilise une méthode de récurrence. On commence par le cas initial, n=0. En substituant n par 0 dans l'expression, on obtient 3 puissance 1 plus 2 puissance 2, qui est égal à 7. Donc, dans ce cas, 7 divise bien l'expression. Ensuite, on passe au cas de n à n+1. On veut montrer que l'expression 3 puissance 2n plus 3 plus 2 puissance 4n plus 6 est congruente à 0 modulo 7. Pour cela, on utilise les congruences. On factorise l'expression en extrayant 3 puissance 2 et 2 puissance 4 (car un 2 et un 4 sont sortis lors du passage de n à n+1). En utilisant les propriétés des congruences modulo 7, on peut simplifier l'expression et la réécrire comme 2 * (3 puissance 2n plus 1 plus 2 puissance 4n plus 2). Or, on reconnaît que cette expression est congruente à 0 modulo 7, grâce à l'hypothèse de récurrence. En effet, on sait que pour tout n antinaturel, l'expression 3 puissance 2n plus 1 plus 2 puissance 4n plus 2 est divisible par 7. Donc, si cette expression est congruente à 0 modulo 7, l'expression 3 puissance 2n plus 3 plus 2 puissance 4n plus 6 l'est également. Finalement, on a bien démontré que pour tout n, l'expression 3 puissance 2n plus 1 plus 2 puissance 4n plus 2 est divisible par 7.

Congurences simultanées

Dans cet exercice, nous devons résoudre des équations linéaires congruentes modulo m. Dans la première partie, on nous demande de prouver qu'une équation de la forme nx congrue à a modulo m a une unique solution modulo m lorsque n et m sont premiers entre eux. On utilise le théorème de Bézout qui nous dit que si m et n sont premiers entre eux, alors il existe une combinaison linéaire d'entiers u et v telle que mu plus nv est égal à 1. On multiplie l'équation nx congrue à a modulo m par v de chaque côté pour se débarrasser de nv et obtenir x congrue à av modulo m. Dans la deuxième partie, on considère deux équations modulo n et m respectivement, avec m et n premiers entre eux. On veut montrer qu'il existe une unique solution modulo nm. On utilise à nouveau le théorème de Bézout pour trouver une combinaison linéaire d'entiers u et v telle que um plus nv est égal à 1. En multipliant la deuxième équation par nv, on obtient une expression pour k, qui est égal à v fois b moins a modulo m. On remplace k dans la première équation pour obtenir une expression pour x. La solution est donc de la forme x congrue à av modulo mn. Ensuite, dans la troisième partie, on résout un problème pratique où deux signaux s'allument à des intervalles de temps différents. On modélise ce problème par trois congruences modulo 15, 28 et 2 respectivement. On utilise le théorème de Bézout pour trouver une unique solution, qui est x congrue à 92 plus 420L modulo 420, où L est un entier arbitraire. Finalement, dans la dernière partie, on résout un problème où on doit répartir un butin entre plusieurs personnes. On modélise ce problème par trois congruences modulo 17, 11 et 6 respectivement. On utilise le théorème de Bézout pour trouver une solution particulière, qui est x congrue à 37 modulo 187. En résolvant cette équation modulo 6, on trouve que l'ensemble des solutions est x congrue à 785 plus 1122L modulo 1122, où L est un entier arbitraire.

PGCD Fibonacci

Dans cet exercice, nous étudions la suite de Fibonacci. Nous rappelons que la suite de Fibonacci est définie par U0=0, U1=1 et Un+2 = Un+1 + Un. La première question consiste à montrer que pour tout n positif, (Un+1 * Un-1 - Un^2) = (-1)^n. Pour cela, nous considérons une suite Vn définie par Vn = (Un+1 * Un-1 - Un^2). Nous souhaitons montrer que Vn est une suite géométrique de raison -1. Nous commençons par exprimer Vn+1 en fonction de Vn. En utilisant la relation de récurrence de la suite de Fibonacci, nous obtenons Vn+1 = (Un+2 * Un - Un+1^2). Nous procédons ensuite à un développement et simplifions l'expression pour obtenir Vn+1 = -Vn. Cela prouve que Vn est une suite géométrique de raison -1. En calculant V1, nous trouvons que Vn = (-1)^n. Ainsi, nous avons montré que pour tout n positif, (Un+1 * Un-1 - Un^2) = (-1)^n. La deuxième partie consiste à montrer que deux termes consécutifs de la suite de Fibonacci sont premiers entre eux. Nous utilisons l'égalité précédente pour cela. Nous remarquons que cette égalité ressemble à une égalité de Bézout. En multipliant les deux côtés de l'égalité par (-1)^n, nous obtenons U(n+1) * U(n-1) - U(n)^2 = 1. En écrivant cette égalité sous la forme U(n-1) * U(n+1) + U(n) * Un = 1, nous avons trouvé les coefficients de Bézout montrant que U(n-1) et U(n+1) sont premiers entre eux. Ensuite, nous montrons que pour tout n, U(m+n) = Um * Un+1 + Um-1 * Un. Nous utilisons une double récurrence pour démontrer cette propriété. En vérifiant les deux premiers termes de la récurrence, nous constatons que la propriété est vérifiée. Ensuite, nous supposons que la propriété est vraie pour PM et PM+1, et nous montrons qu'elle est également vraie pour PM+2. Finalement, en utilisant cette propriété, nous montrons que le PGCD de Um et Un est égal à U(PGCD(m,n)). En conclusion, nous avons étudié la suite de Fibonacci et montré plusieurs propriétés intéressantes, telles que la relation géométrique entre les termes de la suite, la coprimalité des termes consécutifs et la relation entre le PGCD de deux termes et le PGCD de leurs indices.