Online Arithmétique dans Z course by Top Instructors - Arithmétique dans Z

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.

algorithme d’Euclide

Dans cet exercice, on cherche d'abord les diviseurs communs de 390 et 525 en utilisant l'algorithme d'Euclide. On trouve que le PGCD de ces deux nombres est de 15, ce qui signifie que les diviseurs communs sont 1, 3 et 5. Ensuite, on cherche le PGCD de (3^123 - 5) et 25. Nous démontrons que le PGCD est de 1, car si le PGCD était de 5 ou de 25, cela signifierait que 5 divise (3^123 - 5), ce qui est impossible car 3 est un nombre premier. Enfin, on démontre que le produit de trois nombres entiers consécutifs est divisible par 6. En utilisant la propriété selon laquelle au moins l'un des trois nombres est pair et au moins l'un est divisible par 3 (car ils sont consécutifs), nous montrons que 2 et 3 divisent le produit. Puisque le PGCD de 2 et 3 est de 1, cela signifie que 6 divise le produit des trois nombres. En résumé, on démontre que 15 est le PGCD de 390 et 525, que 1 est le PGCD de (3^123 - 5) et 25, et que 6 divise le produit de trois nombres consécutifs.

Equations de Bezou

Dans cet exercice, nous avons résolu quatre équations diophantiennes. Pour résoudre une équation diophantienne, nous commençons par trouver une solution particulière. Si cela n'est pas évident, nous utilisons une méthode spécifique pour garantir une solution. La solution générale se calcule en ajoutant ou soustrayant un coefficient devant l'autre inconnu. Dans la première équation, le PGCD de 2 et 5 est 1. Nous trouvons facilement une solution particulière en prenant x = -1 et y = 1. La solution générale est alors écrite comme x = -1 - 5k et y = 1 + k. Dans la deuxième équation, le PGCD est 17. Après simplification, nous obtenons 19x - 23y = 6. En appliquant l'algorithme de Clide, nous trouvons une solution particulière qui est x = -216 et y = -180. La solution générale est alors x = -216 + 23k et y = -180 + 19k. Dans la troisième équation, le PGCD est 9. Après simplification, nous obtenons 18x + 23y = 3. En appliquant à nouveau l'algorithme de Clide, nous trouvons une solution particulière qui est x = 27 et y = -21. La solution générale est alors x = 27 + 23k et y = -21 + 18k. Enfin, dans la dernière équation, le PGCD est 13 mais il ne divise pas 15, ce qui signifie qu'il n'y a pas de solution.

PGCD nombres pythagoriciens

Aucun résumé n'est disponible pour cette vidéo

Equation modulaire

Dans cet exercice, on cherche à trouver les solutions de l'équation AX congruent à B modulo N, avec des conditions sur A, B et N. On veut démontrer que cette équation a une solution si et seulement si le PGCD de A et N divise B. Dans la première partie, on montre que si X est une solution de l'équation, alors le PGCD divise B. On utilise le fait que si AX est congruent à B modulo N, cela signifie que le PGCD de A et N divise B. Dans la deuxième partie, on montre que si le PGCD divise B, alors l'équation a une solution. On utilise le théorème de Bézout pour montrer qu'il existe un nombre UV tel que AU + NV est égal à D. En multipliant cette équation par B, on obtient BAU + BNV = BD. En factorisant B par le PGCD, on obtient l'équation B'AU + B'NV = B. On en déduit que B'U est une solution de l'équation. Dans la deuxième question, on suppose que le PGCD divise B et on pose N égale à DN'. On veut montrer que l'ensemble des solutions de l'équation est donné par X0 + QN', où Q est un entier. On utilise le fait que si X est une solution, alors A(X-X0) est congruent à 0 modulo N. En factorisant A par le PGCD, on obtient l'équation A'(X-X0) = KN'. Comme A' et N' sont premiers entre eux, on en déduit que N' divise X-X0. On peut alors montrer que tous les nombres de la forme X0 + QN' sont des solutions de l'équation. Dans la troisième question, on cherche à montrer que deux solutions de l'équation sont congrues entre elles modulo N si et seulement si le PGCD divise la différence de leurs coefficients multiplicateurs. On en déduit que les solutions de l'équation sont de la forme X0 + QN', où Q est un entier et X0 est une solution particulière. On conclut que l'équation admet exactement ces solutions.