Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
288 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

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

Envoyé par joujoutoc 
(p-k)!=k mod(p)
il y a douze années
Bonsoir,

Je me suis amusé un peu avec le théorème de Wilson en appliquant l'idée d'un k entier positif (k<p), et p premier et j'ai trouvé des comportements bizarres : le 17 et le 23 en particulier. Ils ont plusieurs solutions

Honnêtement, je n'ai pas été plus loin. C'est frais! Je vous livre mon constat.
Re: (p-k)!=k mod(p)
il y a douze années
avatar
(p-k)!=k mod(p) pour au moins une valeur de k ou pour plusieurs?
Re: (p-k)!=k mod(p)
il y a douze années
Pour plusieurs valeurs de k.
Certains nombres premiers admettent plusieurs solutions. D'autres non.
Re: (p-k)!=k mod(p)
il y a douze années
Exemple :

6! mod(11)=5

11-5=6
AD
Re: (p-k)!=k mod(p)
il y a douze années
avatar
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
Re: (p-k)!=k mod(p)
il y a douze années
Petit rectificatif, pour k=6

6!=720=1 (mod p), soit 719=0 (mod p), d'où p=719 et (719-6)!=713!=6 (mod 719) (j'ai vérifié).


[Aie.. Merci de signaler cette erreur grossière sad smiley. Je corrige ci-dessus. AD]



Edité 1 fois. La derni&egrave;re correction date de il y a douze ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: (p-k)!=k mod(p)
il y a douze années
avatar
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
Re: (p-k)!=k mod(p)
il y a douze années
2p-1 est il premier?

Signalons:

(59-15)!=15 (mod 59)
(59-18)!=18 (mod 59)
(59-43)!=43 (mod 59).
Re: (p-k)!=k mod(p)
il y a douze années
avatar
(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
Re: (p-k)!=k mod(p)
il y a douze années
avatar
Cidrolin:
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?
Re: (p-k)!=k mod(p)
il y a douze années
avatar
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
Re: (p-k)!=k mod(p)
il y a douze années
Bonjour,

Merci AD pour la démonstration dont j'ai saisi le sens.
Elle donne lieu à une application pratique évidente, à la condition de pouvoir décomposer k! + (-1)k+1.
J'ai cependant une autre petite question qui m'intrigue :

Soit N=p*q (N semi-premier)
Soit r la valeur entière de la racine carrée de N
Soit t le produit de (r-(r+k)) avec k variant de 1 à r-2)
Exemple r = 36
On prend les suites ti :
t1=36*35
t2=36*35*34
t3=36*35*34*33
etc....
jusqu'à 36!

ti mod (p) converge vite vers une valeur a = p-1 ou a=1

Je donne un exemple :
N=1633=23*71

40..... 40...... 17
39..... 1560.... 19
38 .... 59280 ....9
37..... 2193360....11
36..... 78960960....5
35 .... 2763633600......14
34 .... 93963542400....... 16
33 .... 3100796899200......22

Est-ce un hasard?
Je l'ai vérifié pour d'autres semi-premiers.
Si la convergence est rapide pour de très grands nombres, il y a matière à exploiter pour factoriser. Difficile à tester pour de très grands nombres (pour moi en tout cas).
Y a-t-il un lien entre le problème évoqué dans ce post et cette relation bizarre?
Peut-on les lier et en faire un outil de factorisation?

Merci beaucoup!
Re: (p-k)!=k mod(p)
il y a douze années
avatar
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.
Re: (p-k)!=k mod(p)
il y a douze années
Bonsoir joujoutoc
Je ne comprends pas bien votre histoire de convergence: toutes vos suites t(k) sont nulles (mod p) à partir d'un certain rang.
Re: (p-k)!=k mod(p)
il y a douze années
avatar
Joujoutoc: si tu cherches un algo de factorisation qui utilise une suite d'entiers et le calcul modulaire tu peux lire ceci:
[fr.wikipedia.org]
Re: (p-k)!=k mod(p)
il y a douze années
Bonsoir,

Je me suis mal exprimé en parlant de convergence.
Le constat est qu'à partir d'un rang i très proche (ça dépend de la taille de n), t(i) mod(p) est égal à 1 ou à p-1.
C'est vérifié pour beaucoup de petits semi-premiers.
Pour les grands, je ne sais pas.
Je ne comprends pas justement le mécanisme.
Prenez un semi-premier N=p*q quelconque dont vous connaissez le plus petit des 2 facteurs (p).
Calculez les t(i) mod (p) successivement de 1 jusqu'au i qui vous donne la valeur 1 ou p-1.
Si ce i recherché est petit (c'est relatif) pour un très grand nombre, il serait facile de le factoriser (en ajoutant +1 ou -1 à ce t(i) et en calculant gcd(t(i)+-1,N) ).
Pourquoi ça marche ainsi, je ne le sais pas.
Je précise que c'est pour un très grand nombre de semi-premiers que ça marche, pas tous.
Re: (p-k)!=k mod(p)
il y a douze années
Je connais tous ces algorithmes de factorisation.
Ce dont je parle c'est pourquoi le t(i) mod (p) tombe si bas que 1 (assez souvent) ou monte à p-1.
Il est évident que lorsque l'on atteint le p faisant partie du produit, ça converge vers zéro.
Il faut essayer ça avec quelques grands nombres au pif pour comprendre ce dont je parle.
Et je ne suis pas sûr mais il doit y avoir un lien avec (p-k)!= k mod(p).
J'essaie juste de comprendre.
Re: (p-k)!=k mod(p)
il y a douze années
avatar
joujoutoc:
n'est ce pas mod n au lieu de mod p?
Re: (p-k)!=k mod(p)
il y a douze années
C'est bien mod(p) et non mod(n).
Il suffit de voir le petit exemple de 1633=23*71
La valeur entière de la racine carrée de 1633 est 40.

On commence par 40*39 et on calcule 40*39 mod (23)=19
on passe ensuite à 40*39*38 mod(23)=9
et ainsi de suite ...
On le fait pour un échantillon de grands semi-premiers juste pour voir comment cela se comporte. On trouve d'abord des petites valeurs ou des valeurs proches de p après quelques itérations.
Si pour des grands N semi-premiers (200 chiffres et plus) on a rapidement (100.000 itérations par exemple, des valeurs < 10 par exemple, on peut factoriser ce type de nombres semi-premiers en 10*100.000 = 1000.000 opérations.
Quelle est la densité de ces nombres je ne sais pas?
Ont-ils des propriéétés particulières auquel cas on peut savoir d'avance si ces nombres facilement factorisables (1000.000 opérations pour un nombre de 200 ou 300 chiffres c'est rien).
Je ne cherche pas à démontrer mais à montrer une piste.
Après les tests, on peut formuler ça et le formaliser en cherchant le pourquoi.
Re: (p-k)!=k mod(p)
il y a douze années
avatar
En fait tu t'intéresses à la suite:

u_k=r!/(r-k)! mod p pour k=0,1,.. ?

avec r la partie entière de la racine carrée de n.
Re: (p-k)!=k mod(p)
il y a douze années
Exact!
Avec k>0 bien sûr.
Re: (p-k)!=k mod(p)
il y a douze années
avatar
n=5*7
r=5
u_0=0 mod 5
Re: (p-k)!=k mod(p)
il y a douze années
Bonjour,

Je vais essayer d'être plus explicite.
Dans le théorème de Wilson :

(p-1)! = (p-1) mod (p) si p est premier

Mon idée est de remplacer (p-1)! par un produit dépendant du paramètre k tel que :

Je reprends ta suite :

u_k=r!/(r-k)! mod p pour k=0,1,..

Il faut que u_k= p-1 ou u_k=1

J'ai choisi r de manière arbitraire (valeur entière de la racine carrée de N=p*q
et k>0) pour essayer de comprendre pourquoi cette suite (à partir d'un petit nombre d'itérations en faisant varier k) devient égale à p-1 ou à 1.
On peut démarrer à k=0 mais cela ne répond pas à mon besoin.
Bien sûr r mod(p) peut être égal à p-1 si r est égal à a*p - 1.



Edité 1 fois. La derni&egrave;re correction date de il y a douze ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par joujoutoc.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 147 733, Messages: 1 484 835, Utilisateurs: 28 072.
Notre dernier utilisateur inscrit Tournencarré.


Ce forum
Discussions: 5 555, Messages: 67 398.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page