(p-k)!=k mod(p)

Bonsoir

Si je comprends bien, tu recherches les $p$ premiers et les $k < p$ tels que $(p-k)! = k \pmod p$
Partant du théorème de Wilson : $(p-1)!=-1 \pmod p$, on peut écrire :
\begin{align*}
-1 &= (p-k)! (p-k+1)\ldots (p-2)(p-1) \pmod p \\
&=(p-k)! \big(-(k-1))\ldots (-2)(-1) \pmod p \\
&= (p-k)! (-1)^{k-1} (k-1)! \pmod p
\end{align*}
Finalement on obtient la jolie formule $$ (p-k)! (k-1)! = (-1)^k \pmod p$$
Revenons à ton problème, tu veux $(p-k)! = k \pmod p$, ce qui donne en remplaçant :
$$k! = (-1)^k \pmod p$$ Il n'y a plus qu'à énumérer :
\begin {itemize}
\item $k=2 : 2=1\pmod p$ impossible
\item $k=3 : 3!=6=-1\pmod p$, soit $7 =0\pmod p$ d'où $p=7$ et $(7-3)!=4!=24=3\pmod 7$
\item $k=4 : 4!=24=1\pmod p$, soit $23 =0\pmod p$ d'où $p=23$ et $(23-4)!=19!=4\pmod {23}$
\item $k=5 : 5!=120=-1\pmod p$, soit $121=11^2 =0\pmod p$ d'où $p=11$ et $(11-5)!=6!=5\pmod {11}$
\item $k=6 : 6!=720=1\pmod p$, soit $719 =0\pmod p$ d'où $p=719$ et $(719-6)!=713!=6\pmod {719}$ (vérifié par RAJ )
\item $k=7 : 7!=5040=-1\pmod p$, soit $5041=71^2 =0\pmod p$ d'où $p=71$ et $(71-7)!=64!=7\pmod {71}$
\item $k=8 : 8!=1\pmod p$, soit $40319=23\times 1753 =0\pmod p$ d'où
\begin{enumerate}
\item $p=23$ et $(23-8)!=15!=8\pmod {23}$
\item $p=1753$ et $(1753-8)! = 1745! = 8\pmod{1753}$ (je n'ai pas vérifié non plus)
\end{enumerate}
\item $k=9 : 9!=-1\pmod p$, soit $362881=19\times 71\times 269 =0\pmod p$ d'où \begin{enumerate}
\item $p=19$ et $(19-9)!=10!=9\pmod {19}$
\item $p=71$ et $(71-9)!=62!=9\pmod {71}$
\item $p=269$ et $(269-9)! = 260! = 9\pmod{269}$ (je n'ai pas vérifié ici non plus)
\end{enumerate}
\item $k=10 : 10!=1\pmod p$, soit $3628799=29\times 125131 =0\pmod p$ d'où
\begin{enumerate}
\item $p=29$ et $(29-10)!=19!=10\pmod {29}$
\item $p=125131$ etc ...
\end{enumerate}
\end{itemize}
Bref, il y a une infinité de solutions, autant que de diviseurs premiers de $k!+(-1)^{k+1}$.
Remarquons que ces diviseurs premiers sont toujours plus grands que $k$

Alain

Bonjour,
Si dans la jolie formule d'AD:
$ (p-k)! (k-1)! = (-1)^k \pmod p$
on remplace $p$ par $2p-1$ et $k$ par $p$
et que l'on suppose $p>2$
on doit trouver $(p-1)!^2 + 1=0$ $mod (2p-1)$
Amicalement

(1) $p>2$ et$2p-1$ sont premiers
est équivalent aux congrusences

(2) $(p-1)! + 1=0$ $mod (p)$
(3) $(p-1)!^2 + 1=0$ $mod (2p-1)$

Reste à combiner (2) et (3) en une seule congruence

Amicalement

Fin de partie écrivait:


> k était quelconque, donc la formule $(p-1)!^2 + 1=0$ $ mod (2p-1)$ est vraie pour $2p-1$ premier et
> $k=p$ $p$ entier quelconque?


$p$ doit être impair

Amicalement

AD a démontré que:

Pour tout n>1:

(n-1)!=(n-k)!(k-1)!(-1)^{k-1} mod n pour 1<k<n

Sur les traces de Cidrolin si on cherche k tel que n-k=k-1 on obtient 2k=n+1
Si on suppose n impair on obtient k=(n+1)/2 et ainsi n-k=k-1=(n-1)/2

Ainsi sauf erreur, si n est impair:
{[(n-1)/2]!}²=(-1)^{(n+1)/2} mod n si et seulement si n est premier (comme conséquence du th. de Wilson)

En espérant ne pas avoir écrit trop d'âneries.

Joujoutoc: si tu cherches un algo de factorisation qui utilise une suite d'entiers et le calcul modulaire tu peux lire ceci:
http://fr.wikipedia.org/wiki/Algorithme_rho_de_Pollard