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 *

Time limit exceeded. Please complete the captcha once again.