Questions du sujet
1. I.1. Pour calculer le pgcd de 3705 et 513, on peut passer en revue tous les entiers $1,2,3,\ldots,512,513$ puis renvoyer parmi ces entiers le dernier qui divise à la fois 3705 et 513. Il sera alors bien le plus grand des diviseurs communs à 3705 et 513. Écrire une fonction \texttt{gcd} qui renvoie le pgcd de deux entiers naturels non nuls, selon la méthode décrite ci-dessus. On pourra éventuellement utiliser librement l’instruction \texttt{min(a,b)} qui calcule le minimum de $a$ et $b$. Par exemple \texttt{gcd(3705, 513)} renverra 57.} 2. I.2. L’algorithme d’Euclide permet aussi de calculer le pgcd. Voici une fonction Python nommée \texttt{euclide} qui implémente l’algorithme d’Euclide. \begin{verbatim} def euclide(a,b): “””Données: a et b deux entiers naturels Résultat: le pgcd de a et b, calculé par l’algorithme d’Euclide””” u=a v=b while v != 0: r=u%v u=v v=r return u \end{verbatim} Écrire une fonction «récursive» \texttt{euclide\_rec} qui calcule le pgcd de deux entiers naturels selon l’algorithme d’Euclide. } 3. I.3.a. Écrire les divisions euclidiennes successivement effectuées lorsque l’on calcule le pgcd de $F_6 = 8$ et $F_5 = 5$ avec la fonction \texttt{euclide}.} 4. I.3.b. Soit $n \geq 2$ un entier. Quel est le reste de la division euclidienne de $F_{n+2}$ par $F_{n+1}$ ? On pourra utiliser librement que la suite $(F_n)_{n\in\mathbb{N}}$ est strictement croissante à partir de $n = 2$. En déduire, sans démonstration, le nombre $u_n$ de divisions euclidiennes effectuées lorsque l’on calcule le pgcd de $F_{n+2}$ et $F_{n+1}$ avec la fonction \texttt{euclide}. } 5. I.3.c. Comparer pour $n$ au voisinage de $+\infty$, ce nombre $u_n$, avec le nombre $v_n$ de divisions euclidiennes effectuées pour le calcul du pgcd de $F_{n+2}$ et $F_{n+1}$ par la fonction \texttt{gcd}. On pourra utiliser librement que $F_n$ est équivalent, au voisinage de $+\infty$, à $\frac{\varphi^n}{\sqrt{5}}$ où $\varphi = \frac{1+\sqrt{5}}{2}$ est le nombre d’or.} 6. I.4. Écrire une fonction \texttt{fibo} qui prend en argument un entier naturel $n$ et renvoie le nombre de Fibonacci $F_n$. Par exemple, \texttt{fibo(6)} renverra 8.} 7. I.5. En utilisant la fonction \texttt{euclide}, écrire une fonction \texttt{gcd\_trois} qui renvoie le pgcd de trois entiers naturels. Par exemple, \texttt{gcd\_trois(18, 30, 12)} renverra 6.} 8. II.1. Démontrer que les valeurs propres complexes de $A$ prennent au maximum trois valeurs distinctes que l’on précisera. } 9. II.2. Justifier que $A$ est diagonalisable dans $M_n(\mathbb{C})$.} 10. II.3. Démontrer que si $A$ est inversible alors $\det(A) = 1$.} 11. III.1.a. Démontrer que si $P$ et $Q$ n’ont aucune racine complexe commune, alors $P$ et $Q$ sont premiers entre eux (on pourra raisonner par l’absurde). } 12. III.1.b. On suppose que $P$ et $Q$ sont premiers entre eux. En utilisant le théorème de Gauss, démontrer que si $P$ et $Q$ divisent un troisième polynôme $R$ à coefficients complexes, alors il en est de même du polynôme $PQ$.} 13. III.2. Soit $(P_i)_{1\leq i\leq n}$ une famille de polynômes non nuls de $\mathbb{R}[X]$. On considère le polynôme $P \in \mathbb{R}[X]$ et la fraction rationnelle $Q \in \mathbb{R}(X)$ définis par $P = \prod_{i=1}^n P_i$ et $Q = \dfrac{P’}{P}$. Démontrer par récurrence que $Q = \sum_{i=1}^n \dfrac{P’_i}{P_i}$. } 14. III.3.a. Soit $P \in \mathbb{R}[X]$ et $a \in \mathbb{R}$. En utilisant la formule de Taylor, démontrer que : si $P(a) = P'(a) = 0$ alors $(X-a)^2$ divise $P$.} 15. III.3.b. En utilisant la question préliminaire III.1, démontrer que l’application $\varphi$ de $\mathbb{R}_{2p-1}[X]$ vers $\mathbb{R}^{2p}$ définie par \[ \varphi(P) = (P(x_1),P(x_2),… ,P(x_p),P'(x_1),P'(x_2),…,P'(x_p)) \] est une application linéaire bijective de $\mathbb{R}_{2p-1}[X]$ sur $\mathbb{R}^{2p}$.} 16. III.3.c. Démontrer qu’il existe un unique polynôme $P_H \in \mathbb{R}_{2p-1}[X]$ tel que, pour tout entier $i$ vérifiant $1 \leq i \leq p$, on a $P_H(x_i) = a_i$ et $P’_H(x_i) = b_i$. Le polynôme $P_H$ est appelé polynôme d’interpolation de Hermite. } 17. III.4. Déterminer le polynôme d’interpolation de Hermite (défini à la question III.3) lorsque $p = 2$, $x_1 = -1$, $x_2 = 1$, $a_1 = 1$, $a_2 = 0$, $b_1 = -1$ et $b_2 = 2$ (si, au cours de ses calculs, le candidat a besoin d’inverser une matrice, il pourra le faire sans justification à l’aide de sa calculatrice). } 18. III.5.a. Pour tout entier $i$ tel que $1 \leq i \leq p$, on considère le polynôme $Q_i = \prod_{j=1,\,j \neq i}^p \left(\frac{X-x_j}{x_i – x_j}\right)^2$. Soit $i$ un entier vérifiant $1 \leq i \leq p$. Calculer $Q_i(x_k)$ pour tout entier $k$ tel que $1 \leq k \leq p$ et démontrer qu’on a $Q’_i(x_k) = 0$ si $k \neq i$ et $Q’_i(x_i) = \sum_{j=1,\,j \neq i}^p \frac{2}{x_i-x_j}$. On pourra utiliser la question préliminaire III.2. } 19. III.5.b. Démontrer que le polynôme $P$ défini par la formule \[ P = \sum_{i=1}^p \left( \left[1-Q’_i(x_i)(X-x_i)\right]a_i + (X-x_i)b_i \right) Q_i \] est le polynôme d’interpolation de Hermite défini à la question III.3. } 20. III.5.c. Retrouver le polynôme de la question III.4 en utilisant cette formule. } 21. III.6. Démontrer que, pour tout $n \in \mathbb{N}$, $H_n$ est un polynôme unitaire de degré $n$. } 22. III.7. Démontrer que, pour tout $n \in \mathbb{N}$, $H’_{n+1} = (n+1)H_n$. } 23. III.8.a. Justifier, pour tous polynômes $P$ et $Q$ dans $\mathbb{R}[X]$, l’existence de l’intégrale qui définit $\langle P | Q \rangle = \int_{-\infty}^{+\infty} P(x)Q(x)f(x)\, dx$, la fonction $f$ étant définie sur $\mathbb{R}$ par $f(x) = \frac{1}{\sqrt{2\pi}}\exp\left(-\frac{x^2}{2}\right)$. } 24. III.8.b. Démontrer que l’on définit ainsi un produit scalaire sur $\mathbb{R}[X]$. } 25. III.9.a. Démontrer que, pour tout $P \in \mathbb{R}[X]$ et pour tout $n \in \mathbb{N}$, \[ \langle P | H_n \rangle = \langle P^{(n)} | H_0 \rangle. \] } 26. III.9.b. En déduire que, pour tout $n \in \mathbb{N}$, la famille $(H_0,H_1,…,H_n)$ est une base orthogonale de $\mathbb{R}_n[X]$. } 27. III.9.c. Calculer $\|H_n\|$ pour tout $n \in \mathbb{N}$. } 28. III.9.d. Soit $P = X^3 + X^2 + X + 1$. Préciser les polynômes $H_1$, $H_2$ et $H_3$ puis déterminer quatre réels $a_i$ $(0 \leq i \leq 3)$ tels que $P = \sum_{i=0}^3 a_i H_i$. En déduire la distance $d$ du polynôme $P$ au sous-espace $\mathbb{R}_0[X]$ des polynômes constants, c’est-à-dire la borne inférieure de $\|P-Q\|$ quand $Q$ décrit $\mathbb{R}_0[X]$. } 29. III.10.a. Soit $n\in \mathbb{N}$. On note $p$ le nombre de racines réelles (distinctes) d’ordre impair du polynôme $H_n$, $a_1, a_2, …, a_p$ ses racines et $S$ le polynôme défini par $S = 1$ si $p = 0$ et $S = \prod_{i=1}^p(X – a_i)$ sinon. Démontrer que, si $p < n$, alors $\langle S | H_n\rangle = 0$. } 30. III.10.b. Démontrer que, pour tout $x \in \mathbb{R}$, $S(x)H_n(x) \geq 0$. } 31. III.10.c. En déduire que $H_n$ a $n$ racines réelles distinctes.}FAQ
Pour calculer le plus grand commun diviseur (PGCD) de deux entiers, tu as plusieurs méthodes classiques en première et deuxième année de prépa scientifique : la méthode naïve, qui teste tous les diviseurs possibles, et surtout l’algorithme d’Euclide, bien plus rapide et fondamental en arithmétique. Maîtriser la récursivité dans ces algos te permettra aussi d’améliorer tes performances lors de tes révisions ou au concours. Cette notion, fréquemment posée en CCINP, est indispensable pour t’attaquer sereinement à de nombreuses questions d’algèbre ou de calculs d’inversibilité de matrices. Pour t’entraîner sur des exercices corrigés pas à pas et accéder à toutes les astuces de la méthode, pense à débloquer les corrigés sur Prépa Booster !
La suite de Fibonacci et ses propriétés, notamment la croissance, la récurrence, et le calcul du PGCD de suites adjacentes, sont des classiques aussi bien en algèbre qu’en algorithmique. En concours, ces suites permettent d’illustrer aussi des méthodes d’approximation et d’optimisation d’algorithmes (comme l’algorithme d’Euclide) et ouvrent la voie à l’analyse asymptotique grâce au nombre d’or. Comprendre à fond Fibonacci, ce n’est pas seulement résoudre une question, c’est aussi être armé pour attaquer de nombreux problèmes types qui tombent au CCINP ou dans d’autres banques d’épreuves.
Une matrice est diagonalisable s’il existe une base dans laquelle son application linéaire s’exprime sous forme diagonale, c’est-à-dire uniquement avec ses valeurs propres sur la diagonale et des zéros ailleurs. Ce concept te permet de résoudre rapidement des problèmes de puissances de matrices, d’itérations, ou encore de systèmes différentiels linéaires. En filière MP au CCINP, la diagonalisabilité intervient aussi bien en algèbre (valeurs propres, polynômes caractéristiques) qu’en applications concrètes à la physique ou à l’ingénierie. Maîtriser ce point te fera gagner du temps et de la sérénité le jour J.
Les polynômes d’interpolation de Hermite, contrairement à ceux de Lagrange qui n’interpolent que les valeurs, permettent d’interpoler à la fois les valeurs et les dérivées. C’est un outil très puissant pour modéliser des phénomènes physiques ou résoudre des systèmes d’équations dans les sujets de concours, notamment quand il y a des conditions sur plusieurs dérivées en des points précis. Tu es quasiment assuré de croiser ce genre de questions à un moment de tes années de prépa, alors comprends bien la construction et la propriété d’unicité de ce polynôme ! Pour aller plus loin avec des exercices pas à pas et des corrigés détaillés, pense à débloquer l’accès aux corrigés sur Prépa Booster.
Le produit scalaire sur une espace de polynômes, surtout avec un poids gaussien, te permet de définir et d’exploiter l’orthogonalité entre familles de polynômes, comme celle des polynômes de Hermite. Cette structure te sert dans l’analyse, les probabilités et dans la résolution de systèmes linéaires complexes (genre, résolution par projection ou moindres carrés). La gaussienne est choisie car c’est une densité remarquable, liée à la convergence des méthodes et à la théorie des espaces de Hilbert. Ce sont des notions vraiment transversales qui peuvent tomber aussi bien en MP qu’en PSI ou PC, donc prends le temps de bien dompter cette technique !
En débloquant les corrigés sur Prépa Booster, tu accèdes à des corrigés détaillés rédigés comme en colles et à un dashboard qui cible tes points faibles sur l’intégralité du programme de maths. C’est le meilleur moyen de travailler efficacement, en t’entraînant sur des sujets complets et des exercices corrigés de concours, histoire de gagner en rapidité et en assurance avant l’épreuve. Le petit plus : tu peux suivre ta progression, cibler tes lacunes, et retrouver rapidement toutes les notions abordées, que ce soit en algèbre, analyse, ou probabilités.