Un curieux test de primalité…

Cet article sur Blogdemaths me rappelle cette histoire de Dennis P. Walsh dans Mathematics Magazine.

Un étudiant de mathématiques monte à bord d’un taxi. Pour entamer la discussion, la chauffeuse de taxi lui demande ce qui l’occupe et lorsqu’il lui répond elle lui dit : “Ah! Très bien ! Écoutez donc ce qui suit.  La dérivée seconde de\[e^{x}\]évaluée en\[x=0\]est égale à 1, n’est-ce pas ? Cela implique que 2 est un nombre premier.  L’étudiant réprime un petit rire condescendant à l’endroit de cette chauffeuse de taxi qui s’amuse innocemment avec des mathématiques qu’elle ne comprend pas mais se console et se dit que, au moins, sur le fond, 2 est effectivement un nombre premier.  Cette dernière n’appréciant pas la réaction, elle emprunte un long détour (qui finira par coûter très cher !)  Elle renchérit : “La dérivée troisième de\[e^{x}+e^{x^{2}}\]évaluée en \[x = 0\]est bien égale à 1 n’est-ce pas ? Alors 3 est un nombre premier.  Et la dérivée quatrième de\[e^{x}+e^{x^{2}} +e^{x^{3}}\]évaluée en\[x = 0\]n’est pas égale à 1 ! Alors 4 n’est pas un nombre premier…

Vous avez sûrement remarqué la régularité.  Elle affirme que pour la fonction \(g\) suivante définie pour \(n>1\) \[g_{n}(x) = \sum_{k\,=\,1}^{n-1}e^{x^{k}}\]si on a \[g_{n}^{(n)}(0) = 1\]alors \(n\) est premier et si on a \[g_{n}^{(n)}(0) \neq 1\]alors \(n\) est composé.  Avant de s’attaquer à la preuve de cet énoncé, puisqu’on parle de dérivées seconde, troisième, quatrième et plus, un petit rappel s’impose.  La dérivée de la fonction puissance \(f\) \[f(x) = x^{\alpha}\]est \[f'(x) = \alpha x^{\alpha-1}\]cette règle étant bien connue des étudiants dès les premiers cours de calcul différentiel.  En appliquant à nouveau la même règle, on obtient pour la dérivée seconde \[f^{\prime \prime}(x) = \alpha (\alpha-1) x^{\alpha-2 }\]et en appliquant à nouveau la même règle à répétition, on obtient après \(n\) itérations \[f^{(n)}(x) = \alpha(\alpha-1)(\alpha-2)\dots(\alpha-n+1)x^{\alpha-n}\]pour la dérivée \(n\)e de la fonction \(f\).  Il est tout à fait pertinent de noter qu’à chaque itération, la fonction puissance perd un degré.  En outre, si \(\alpha<n\), c’est-à-dire que si on dérive la fonction un nombre plus grand de fois que son degré initial, on aura éventuellement que des termes nuls, et donc \[f^{(n)}(x) = 0\]Par ailleurs, si \(\alpha = n\), on a exactement \[f^{(n)}(x) = \alpha(\alpha-1)\dots (\alpha-n+1)x^{0} = \alpha(\alpha-1)\dots (\alpha-n+1)\]c’est-à-dire un terme constant.  Enfin, si  \(\alpha > n\), on aura un terme non-nul de degré \(\alpha-n\) \[f^{(n)}(x) = \alpha(\alpha-1)(\alpha-2)\dots (\alpha-n+1)x^{\alpha-n}\]L’astuce est d’utiliser le développement en série de la fonction exponentielle \[e^{z} = \sum_{j\,=\, 0}^{\infty}\frac{z^{j}}{j\,!}\]En posant\[z =x^{k}\]on obtient\[e^{x^{k}} = \sum_{j\,=\,0}^{\infty}\frac{\left(x^{k}\right)^{j}}{j\,!} = \sum_{j\,=\,0}^{\infty} \frac{x^{kj}}{j\,!}\]Il est donc possible d’exprimer la fonction \(g\) \[g_{n}(x) = \sum_{k\,=\,1}^{n-1}e^{x^{k}}\]comme \[g_{n}(x) = \sum_{k\,=\,1}^{n-1}\sum_{j\,=\,0}^{\infty}\frac{x^{kj}}{j\,!}\]On considère la \(n\)e dérivée de \(g\).  On sait que pour \(kj<n\), on obtient des termes nuls.  Pour \(kj =n\), on obtient des termes constants et pour \(kj>n\) on obtient des termes de degré \(kj-n\).  La dérivée est donc \[g_{n}^{(n)} (x)= \sum_{k\,=\,1}^{n-1}\sum_{j\,=\,0}^{\infty}\frac{(kj)(kj-1)(kj-2)\dots(kj-n+1)x^{kj-n}}{j\,!}\]pour chaque \(kj\geq n\).  Lorsqu’on évalue la fonction en \(x=0\), tous les termes où \(kj>n\) deviennent nuls.  Les seuls termes restants sont les termes constants, c’est-à-dire ceux où \(kj=n\). On a donc \[g_{n}^{(n)}(0) = \sum_{\underset{k\, \vert\, n}{k\,=\,1}}^{n-1}\frac{n(n-1)(n-2)\dots(n-n+1)}{\left(\frac{n}{k}\right)!}\]cette somme étant étendue aux diviseurs \(k\) de \(n\) (on utilise ici la notation \(k\, \vert\, n\) habituelle pour « \(k\) divise \(n\) »).  En utilisant la définition de factorielle et le fait que \(k=1\) divise toujours \(n\), on peut réécrire l’expression précédente de manière plus élégante comme\[g_{n}^{(n)}(0) = \sum_{\underset{k\, \vert\,  n}{k\, =\, 1}}^{n-1}\frac{n!}{\left(\frac{n}{k}\right)!} = 1 + \sum_{\underset{k\,\vert \, n}{k\,=\,2}}^{n-1}\frac{n!}{\left(\frac{n}{k}\right)!}\]Si \(n\) est premier, le seul et unique diviseur \(k\) de \(n\) plus petit ou égal à \(n-1\) est \(1\).  La somme de droite est donc nulle !  Et on a bien \[g_{n}(0) = 1\]Si, d’autre part, \(n\) est composé, alors il existe au moins deux nombres \(k\) et \(r\) dans \(\left\{2,\ \dots \ , \, n-1\right\}\) qui divisent \(n\).  On peut donc écrire \[g_{n}^{(n)}(0) \geq 1 + \frac{(kr)!}{(r)!}>1\]L’histoire ne dit pas si l’étudiant s’excuse auprès de la dame !

Références :

Dennis P. Walsh, Mathematics Magazine, Volume 80, Number 4, October 2007 , pp. 302-303(2)

David M. Bradley, Mathematics Magazine, Volume 82, Number 3, June 2009 , pp. 215-218(4)

Leave a Reply

Your email address will not be published. Required fields are marked *