
Dans cette fonction, \og \texttt{2**(n-1)\%n} \fg{} représente le reste de la division euclidienne de $2^{n-1}$ par $n$. Autrement dit, cela représente la congruence de $2^{n-1}$ modulo $n$.

\medskip

D'après le petit théorème de Fermat, si $n$ est premier (donc ne divise par 2) alors $2^{n-1}\equiv1\mod p$.

Ainsi, si le reste calculé est différent de 1, alors $n$ n'est pas premier. Par conséquent, si \texttt{test(n)} renvoie \og False \fg, $n$ n'est assurément pas premier.

Mais attention, si la fonction renvoie \og True \fg, cela ne signifie pas nécessairement que $n$ est premier.

En effet, \texttt{test(341)} renvoie \og True \fg{} et pourtant, $341=11\times31$.

\medskip

Ce test n'est donc pas fait pour prouver qu'un nombre est premier mais au contraire pour prouver qu'un nombre n'est pas premier.

On peut alors modifier cette fonction afin qu'elle soit moins ambigüe:
\begin{python}
def test(n):
    if 2**(n-1)%n != 1:
        return f"{n} n'est assurément pas un nombre premier."
    else:
        return f"{n} est potentiellement premier, mais il faut effectuer d'autres tests pour s'en assurer."
\end{python}
