Divisibilità fattoriale

[n@t]

Salve,
propongo il seguente problemino:
Sia \(\displaystyle n = 100! + 1 \). Per quale dei seguenti numeri è divisibile \(\displaystyle n \)?
A) 225
B) 1000
C) 144
D) nessuna delle risposte è corretta

Fornire una spiegazione adeguata

Grazie a chiunque voglia dedicarci del tempo.

Saluti

[Gi81]

Sia $225$ sia $1000$ sia $144$ dividono $100 !$: infatti $225= 15*5*3$, $1000=100*10$, $144=12*6*2$.
Quindi nessuno dei tre può dividere $n$.

[n@t]

Grazie credevo esistesse qualche criterio di divisibilità per \(\displaystyle n! \).

[dan952]

Scommetterei il mio libro di Algebra che quel $n$ è divisibile per 101.

[Pachisi]

@dan95: con il teorema di Wilson per $p=101$ dovrebbe venire.

[dan952]

Bravo Pachisi, ma se uno non conoscesse Wilson?!

[dan952]

Suggerimento:
Dimostrare che per ogni $x \in {1, 2, 3 ,\cdots, p-1}$ con $p$ primo, esiste ed è unico $y \in {1, 2, 3 ,\cdots, p-1}$ tale che $xy -= 1\ mod\ p$
Usare il precedente risultato per mostrare che $100!-=-1\ mod\101$.

[Pachisi]

Forse:

SI fa per assurdo. Prendiamo un $x \in {1,2,...,p-1}$. Supponiamo non esiste alcun $y \in {1,2,..,p-1}$ tale che $xy \equiv1 mod p$. Allora esisteranno $a,b \in {1,2,...,p-1}$ diversi, tali che $ax \equiv bx mod p$. Essendo $(x,p)=1$, abbiamo $a \equiv b mod p$. Assurdo.
Se non fosse unico ci sarebbe lo stesso problema.
Ritornando al problema, consideriamo l'insieme ${1,2,...,100}$. Allora, per la prima parte, per ogni $x \in {1,2,...,100}$ esiste un unico $y \in {1,2,...,100}$ tale che $xy \equiv 1 mod 101$. Notiamo che $100$ va con $100$. Allora, prendiamo tutte le altre coppie, e le moltiplichiamo. Segue che $99! \equiv 1 mod 101$. Moltiplicando per $100$ segue le tesi.

[dan952]

Bravo se generalizzi la seconda parte dimostri una delle due implicazioni di Wilson, ovvero se $p$ è primo allora $p|(p-1)!+1$.

[ot]Sei studente? Se sì di quale facoltà o liceo?[/ot]

[Pachisi]

Per il caso generale, mi sembra abbastanza simile la dimostrazione. Consideriamo l'insieme ${1,2,...,p-1}$, con $p$ primo. Con il tuo hint, $p-1$ deve andare con $p-1$. Allora, moltiplicando tutti gli altri, abbiamo $(p-2)! \equiv 1 mod p$. Quindi, $(p-1)! \equiv -1 mod p$. Quindi segue la tesi.

[ot]Una high school.[/ot]

[dan952]

Ok!