Lettre F

FACTORIELLE

Pour chaque entier n\geqslant1, on définit sa factorielle, que l’on note n!, comme le produit des entiers de 1 à n. Par exemple :

    \[6!=1\times2\times3\times4\times5\times6=720\]

et, par convention :

    \[0!=1\]

La factorielle de n peut s’interpréter comme le nombre de permutations de n éléments. Cet article propose une interprétation amusante de la factorielle de 52 (c’est-à-dire du nombre de façons de permuter un jeu de cartes).

Si k,n sont des entiers tels que 0\leqslant k\leqslant n, le coefficient binomial \binom{n}{k} est donné par :

    \[\binom{n}{k}=\frac{n!}{k!\thinspace\left(n-k\right)!}\]

Une condition nécessaire et suffisante pour qu’un entier p\geqslant2 soit premier est donnée par le théorème de Wilson :

    \[p\in\mathbb{P}\Leftrightarrow1+\left(p-1\right)!\equiv0\pmod{p}\]

La formule de Stirling donne, lorsqu’on fait tendre n vers +\infty, l’estimation asymptotique suivante :

    \[n!\sim\left(\frac{n}{e}\right)^{n}\sqrt{2\pi n}\]

Voir cet article pour une preuve détaillée de ce résultat.

La fonction Gamma \left(\Gamma\right) d’Euler, définie pour tout réel x>0 par :

    \[\Gamma\left(x\right)=\int_{0}^{+\infty}t^{x-1}e^{-t}\thinspace dt\]

vérifie \forall n\in\mathbb{N}^{\star},\thinspace\Gamma\left(n+1\right)=n\thinspace\Gamma\left(n\right) et \Gamma\left(1\right)=1, d’où \Gamma\left(n+1\right)=n!.
Ainsi, \left]-1,+\infty\right[\rightarrow\mathbb{R},\thinspace x\mapsto\Gamma\left(x+1\right) est un prolongement (\mathcal{C}^{\infty}) de la factorielle.
On peut montrer que \Gamma est la seule application f:\left]0,+\infty\right[\rightarrow\left]0,+\infty\right[ logarithmiquement convexe (c’est-à-dire telle que \ln\circ\Gamma soit convexe), vérifiant :

    \[f\left(1\right)=1\qquad\textrm{ et }\qquad\forall x>0,\,f\left(x+1\right)=x\,f\left(x\right)\]

FERMAT (petit théorème de)

Le petit théorème de Fermat ne doit pas être confondu avec le grand théorème de Fermat (ou dernier théorème de Fermat), démontré en 1995 par Andrew Wiles.

petit théorème de Fermat

Etant donné un nombre premier p, tout entier naturel n vérifie la congruence :

    \[ n^{p}\equiv n\pmod{p} \]

On peut prouver ce résultat par récurrence sur n, en exploitant la formule du binôme et le fait que :

    \[\forall k\in\left\llbracket 1,p-1\right\rrbracket ,\;p\mid\binom{p}{k}\]

On peut aussi appliquer le théorème de Lagrange au groupe \left(\mathbb{Z}/p\mathbb{Z}\right)^{\star} (groupe de cardinal p-1, constitué des éléments inversibles du corps \left(\mathbb{Z}/p\mathbb{Z},+,\times\right)).

Ces différents points de vue sont développés dans cet article.

Le petit théorème de Fermat fait l’objet de l’exercice n° 8 de cette fiche.

Une question naturelle est la réciproque : est-ce qu’un entier q\geqslant2 vérifiant n^{q}\equiv n\pmod{q} pour tout n\in\mathbb{N} est nécessairement premier ?

La réponse est non : il existe des entiers, appelés nombres de Carmichael, qui sont composés (c’est-à-dire non premiers) mais qui vérifient tout de même cette condition. Le plus petit tel entier est 561.

Il est connu (théorème de Alford, Granville et Pomerance – 1994) qu’il existe une infinité de nombres de Carmichael.

Un nombre composé q\geqslant2 est dit pseudo-premier en base n si n^{q}\equiv n\pmod{q}. Les nombres de Carmichael sont donc ceux qui sont pseudo-premiers en toute base. Le fait que les nombres pseudo-premiers simultanément en plusieurs bases soient “suffisamment rares” est à l’origine d’un test de primalité probabiliste, appelé test de Rabin-Miller. Ce test permet d’affirmer – avec certitude – qu’un nombre q est composé ou bien – avec une très petite probabilité d’erreur – qu’il est premier.

FERMÉ

La notion de partie fermée est présentée ici dans \mathbb{R} par souci de simplicité. Son cadre naturel est celui des espaces topologiques.

On dit d’une partie A de \mathbb{R} que c’est un fermé lorsque son complémentaire est un ouvert; autrement dit lorsque :

    \[\forall a\in\mathbb{R}-A,\thinspace\exists r>0;\thinspace\left]a-r,a+r\right[\cap A=\emptyset\]

Cette condition équivaut à la suivante (caractérisation séquentielle des fermés) : pour toute suite \left(a_{n}\right)_{n\in\mathbb{N}} à termes dans A, si cette suite converge, alors sa limite appartient à A.

L’adjectif “fermé” doit donc être compris comme “fermé pour le passage à la limite” : on ne sort pas de A en prenant la limite d’une suite convergente d’éléments de A.

Attention :
“être un fermé” n’est pas la négation de “être un ouvert” !

Par exemple : \left[0,1\right[ n’est ni un ouvert ni un fermé.

Les parties suivantes de \mathbb{R} sont des fermés :

  • \emptyset
  • \mathbb{R}
  • \left\{ a\right\}
  • \left[a,b\right] pour tout couple \left(a,b\right)\in\mathbb{R}^{2} tel que a<b
  • \mathbb{Z}
  • l’intersection de toute famille de fermés
  • l’union d’un famille finie de fermés
  • l’image réciproque d’un fermé par une application continue \mathbb{R}\rightarrow\mathbb{R}

Les parties suivantes de \mathbb{R} ne sont pas des fermés :

  • \left]a,b\right[,\left[a,b\right[,\left]a,b\right] pour tout couple \left(a,b\right)\in\mathbb{R}^{2} tel que a<b
  • \left\{ \frac{1}{n};\thinspace n\in\mathbb{N}^{\star}\right\}
  • \mathbb{Q} et \mathbb{R}-\mathbb{Q}

FIBONACCI (suite de)

Définition

La suite d’entiers naturels définie par les relations de récurrence suivantes :

    \[F_{0}=0,\quad F_{1}=1\]

et pour tout n\in\mathbb{N}^{\star} :

    \[F_{n+1}=F_{n}+F_{n-1}\]

est appelée suite de Fibonacci.

Quelques généralités à son sujet sont rassemblées dans cet article.

La suite de Fibonacci vérifie donc une relation de récurrence linéaire du second ordre à coefficients constants. Le polynôme caractéristique associé est X^{2}-X-1 et ses racines sont distinctes; il s’agit de :

    \[\alpha=\frac{1+\sqrt{5}}{2}\quad\text{et}\quad\beta=\frac{1-\sqrt{5}}{2}\]

c’est-à-dire du nombre d’or et de l’opposé de son inverse. On en déduit l’expression explicite suivante :

    \[\boxed{\forall n\in\mathbb{N},\thinspace F_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]}\]

Pour les détails, on pourra consulter l’exemple A de la section 6 de cet article.

On notera qu’il n’est pas du tout évident que le second membre de cette égalité soit un entier naturel … mais c’est pourtant bien le cas !

Parmi les nombreuses propriétés remarquables de la suite \left(F_{n}\right)_{n\geqslant0}, retenons les trois suivantes (la première peut servir de base à un algorithme de calcul rapide des F_{n}) :

Proposition 1

Pour tout \left(n,m\right)\in\mathbb{N}^{\star}\times\mathbb{N} :

    \[\boxed{F_{n+m}=F_{n-1}F_{m}+F_{n}F_{m+1}}\]

Proposition 2

Pour tout couple \left(m,n\right) d’entiers naturels :

    \[\boxed{F_{m}\wedge F_{n}=F_{m\wedge n}}\]

On note a\wedge b le PGCD des entiers a,b.

Proposition 3

Pour tout n\in\mathbb{N} :

    \[\boxed{\sum_{k=0}^{n}\binom{n}{k}F_{k}=F_{2n}}\]

Les preuves de ces trois propositions sont laissées en pâture au lecteur 🙂 Mais n’hésitez pas – si nécessaire – à demander une indication en passant par le formulaire de contact.

Signalons encore les challenges n° 26 et n° 33 qui portent, l’un comme l’autre, sur la suite de Fibonacci.

FORME LINÉAIRE

Définition

Etant donné un \mathbb{K}-espace vectoriel E, on appelle forme linéaire sur E toute application linéaire de E dans \mathbb{K}.

Le noyau d’une forme linéaire est :

  • l’espace entier (s’il s’agit de la forme linéaire nulle),
  • un hyperplan de E (dans les autres cas).

Quelques exemples …

Exemple 1

Si E est de dimension finie et si B=\left(e_{1},\cdots,e_{n}\right) est une base de E alors l’application e_{i}^{\star} qui à chaque vecteur de E associe sa i-ème coordonnée dans B est une forme linéaire, appelée i-ème forme coordonnée relative à B.

La famille \left(e_{1}^{\star},\cdots,e_{n}^{\star}\right) est une base de \mathcal{L}\left(E,\mathbb{K}\right) : c’est la base duale de B.

Exemple 2

Si a\in\mathbb{R}, alors l’application E_{a}:\mathbb{R}\left[X\right]\rightarrow\mathbb{R},\thinspace P\mapsto P\left(a\right) est une forme linéaire.

Son noyau est constitué des polynômes de la forme \left(X-a\right)Q avec Q\in\mathbb{R}\left[X\right] arbitraire.

Exemple 3

Soit I un intervalle non trivial de \mathbb{R} et E l’espace des applications continues et intégrables de I dans \mathbb{R} (la précision “intégrables” étant superflue si I est un segment).

L’application E\rightarrow\mathbb{R},\thinspace f\mapsto\int_{I}f\left(t\right)\thinspace dt est une forme linéaire.

Définition

Etant donné un \mathbb{K}-espace vectoriel E, on appelle forme linéaire sur E toute application linéaire de E dans \mathbb{K}.

Le noyau d’une forme linéaire est :

  • l’espace entier (s’il s’agit de la forme linéaire nulle),
  • un hyperplan de E (dans les autres cas).

Quelques exemples …

Exemple 1

Si E est de dimension finie et si B=\left(e_{1},\cdots,e_{n}\right) est une base de E alors l’application e_{i}^{\star} qui à chaque vecteur de E associe sa i-ème coordonnée dans B est une forme linéaire, appelée i-ème forme coordonnée relative à B.

La famille \left(e_{1}^{\star},\cdots,e_{n}^{\star}\right) est une base de \mathcal{L}\left(E,\mathbb{K}\right) : c’est la base duale de B.

Exemple 2

Si a\in\mathbb{R}, alors l’application E_{a}:\mathbb{R}\left[X\right]\rightarrow\mathbb{R},\thinspace P\mapsto P\left(a\right) est une forme linéaire.

Son noyau est constitué des polynômes de la forme \left(X-a\right)Q avec Q\in\mathbb{R}\left[X\right] arbitraire.

Exemple 3

Soit I un intervalle non trivial de \mathbb{R} et E l’espace des applications continues et intégrables de I dans \mathbb{R} (la précision “intégrables” étant superflue si I est un segment).

L’application E\rightarrow\mathbb{R},\thinspace f\mapsto\int_{I}f\left(t\right)\thinspace dt est une forme linéaire.

Exemple 4

Soit E un espace pré-hilbertien réel et soit a\in E.

L’application E\rightarrow\mathbb{R},\thinspace x\mapsto\left(x\mid a\right) est une forme linéaire sur E.

Si de plus E est de dimension finie (espace euclidien), alors toute forme linéaire sur E est de ce type. C’est le théorème d’isomorphisme canonique entre un espace vectoriel euclidien et son dual (cas particulier du théorème de représentation de Riesz).

Partager cet article
  •  
  •  
  •  
  •