Trouver tous les entiers n divisant (n-1)!

Sachaben

Bonjour. Encore un exo d’arithmétique. Je dois trouver tous les entiers n non nuls tels que n divise (n-1)!
si n est premier, j’utilise Wilson et donc il n’y a pas de solution.
si n n’est pas premier, j’écris n=axb. a>1 et b<n. Donc dans (n-1)! on trouvera le produit axb donc tout entier non premier convient. 

Est-ce que le raisonnement est correct ?

Pour n=4, cela ne marche pas 4 ne divise pas 6. Je ne vois pas ce qui cloche dans mon raisonnement. 

Merci pour toute aide 

Math Coss

Ben, dans $2\times3$ tu as $2$ et tu as $2$ mais c'est deux fois le même.

Sachaben

Je n’ai pas compris la remarque Math Coss

JLapin

Le facteur $2$ n'apparait pas 2 fois dans le produit $2*3$.

SI on prend un nombre plus grand, par exemple $12=2*6$, on observe que $2$ et $6$ apparaissent séparément dans le produit qui définit $11!$

Chaurien

Si $p$ est premier, à l'évidence $p$ est premier avec $(p-1)!$ et ne divise donc pas $(p-1)!$.

Si $n$ est composé : https://math.stackexchange.com/questions/164852/if-n-ne-4-is-composite-then-n-divides-n-1

Poirot

Ce qui ne marche pas pour $n=4$ c'est que $a$ et $b$ sont supposés distincts dans ton raisonnement. Pour $4 = 2 \times 2$ ce n'est pas le cas.

Sachaben

Ah, ok. Le raisonnement ne marche que si a et b sont différents . Mais pourquoi 4 et pas un autre carré? 9 , ça marche dans 8!, 

NicoLeProf

Parce que dans le lien ci-dessus indiqué par Chaurien, il est écrit lorsque $n=a^2$ (i.e : lorsque $a=b$) :

$(n−1)!≡1×2×⋯×a×⋯×(n−a)×⋯×(n−1)≡1×2×⋯×a×⋯×−a×⋯×−1≡0 \pmod n$.

Je rajoute : ok, sauf si on a : $a=n-a$ auquel on aura $1$ seule occurrence de $a$ et ainsi, on n'aura pas $n \mid (n-1)!$.

Or, $a=n-a$ et $n=a^2$ est équivalent à dire $a=0$ (pas possible) ou $a=2$.

Le seul cas qui ne marche pas dans ton raisonnement est finalement le cas $a=2$ et $n=a^2=4$.

Sachaben

Merci, je comprends mieux. 

J’ai aussi regardé le lien envoyé par Chaurien, et on peut raisonner directement pour n>4 en décomposant les
cas p= racine (n) ou p< racine (n) avec p le plus petit facteur de n. Je n’avais pas été assez rigoureux dans ma décomposition. Merci à tous 

GaBuZoMeu

Bonjour,

On peut raisonner différemment.

Soit $n>1$. L'entier $n$ divise $(n-1)!$ si et seulement si pour tout premier $p$ 

$$v_p(n)\leq \sum_{1\leq k<n} v_p(k)\quad(*).$$($v_p(k)$ est bien entendu la valuation $p$-adique de $k$, autrement dit le plus grand entier naturel $\alpha$ tel que $p^\alpha$ divise $k$.)

Pour $p$ premier, posons $n=p^\alpha u$ où $p$ ne divise pas $u$. Si $u>1$ alors $\sum_{1\leq k<n} v_p(k)\geq (u-1)\alpha\geq \alpha$. Donc si $n$ n'est pas une puissance de premier, alors $n$ divise $(n-1)!$.

Si $n$ est premier, il ne divise pas $(n-1)!$.

Reste à examiner le cas où $n=p^\alpha$ avec $p$ premier et $\alpha >1$. Comme $\sum_{1\leq k<p^\alpha} v_p(k)\geq (p-1)(\alpha -1)$, $(*)$ est vérifié si $p>2$. Enfin si $p=2$, $\sum_{1\leq k<2^\alpha} v_2(k)\geq \alpha-1+2(\alpha-2)$ qui est supérieur ou égal à $\alpha$ dès que $\alpha>2$. Reste $2^2=4$ qui ne divise pas $3!=6$.

Foys

Soit $n$ un entier naturel qui est produit de deux entiers naturels $a,b>1$ distincts (*). Alors $\{a,b\}$ est contenu dans $\{2,...,n-1\}$ et donc $n=ab$ divise $(n-1)!$

Soit $n$ un entier ne divisant pas $(n-1)!$. (*) entraîne que $n$ est de la forme $p^k$ avec $p$ premier et $k\leq 2$. Si $k=2$ et $p\geq 3$ alors $2p<p^2 = n$ donc $2\leq p \leq 2p \leq n-1$ et $p^2\mid(n-1)!$ (contradiction). Donc finalement $n\in \{1,2,4\} \cup P$ (où $P\subseteq \N$ est l'ensemble des nombres premiers). L'inclusion réciroque est claire.

Sachaben

Merci à tous pour vos retours 

gai requin

Qui veut chercher les entiers $n\geq 2$ tels que $n^2$ divise $(n-1)!$ ?

GaBuZoMeu

" Soit $n$ un entier ne divisant pas $(n−1)!$ ... Donc finalement $n\in\{1,2,4\}\cup P$ (où $P\subset \N$ est l'ensemble des nombres premiers). L'inclusion réciroque est claire. "

Ah bon, $1$ ne divise pas $0!$ ?

JLapin

Qui veut chercher les entiers n≥2 tels que n2 divise (n−1)! ?

Et les nombres premiers $p$ tels que $p^2$ divise $(p-1)!+1$ ?

Foys

@GaBuZoMeu
C'est encore la faute de L'ensemble vide/du zéro!
Bref les entiers $n$ ne divisant pas $(n-1)!$ sont $4$ et les nombres premiers.

gai requin

@JLapin : J'ai une solution pour mon problème.
En as-tu une pour le tien ?

JLapin

Evidemment que non !

Simplement, je trouvais que les deux problèmes se ressemblent un peu

jandri

Pour le problème de gai requin : 
$n^2$ divise $(n-1)!$ sauf si $n=p$, $n=2p$ (avec $p$ premier), $n=8$ et $n=9$.

Pour le problème de JLapin : 
$p^2$ divise $(p-1)!+1$ pour $p=5$, $p=13$, $p=563$ et peut-être d'autres valeurs très grandes (suite A007540).