Feladat:	B.4616	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Vágó Ákos
Füzet:	2015/március, 145. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Számsorozatok, Maradékos osztás
Hivatkozás(ok):	Feladatok: 2014/március: B.4616

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Megoldás. Ha $n=1$, 2 vagy $3$, akkor könnyen ellenőrizhető, hogy különböző maradékot adnak $n$-nel osztva. Ha $n=4$, akkor $2!=2$ és $3!=6$ azonos maradékot adnak 4-gyel osztva, azaz $n=4$ nem felel meg a feltételnek. Belátjuk, hogy ha $4<n$ összetett szám, akkor $\left(n-1\right)!$ osztható $n$-nel. Ha az $n$ szám felírható $n=ab$ alakban, ahol $0<a<b<n$ egészek, akkor $a$ és $b$ is szerepel az $1\cdot 2\cdot \text{...}\cdot \left(n-1\right)$ szorzatban, és így $n\mid \left(n-1\right)!$ valóban teljesül. Csak akkor nem írható fel ilyen alakban $n$, ha egy $p$ prímszám négyzete, de ekkor $2p<n=p^2$, hiszen $n>4$, és ezért $2n=p\left(2p\right)\mid \left(n-1\right)!$, azaz $n\mid \left(n-1\right)!$ ekkor is fennáll. Tehát $\left(n-1\right)!$ és $n!$ egyaránt 0 maradékot adnak $n$-nel osztva, vagyis a $4$-nél nagyobb összetett számok sem felelnek meg a feltételnek. Végül, ha $n>3$ prímszám, akkor a Wilson-tétel miatt $\left(n-1\right)!\equiv -1\left(n\right)$, és ezért $\left(n-2\right)!\equiv 1\left(n\right)$, hiszen $\left(n-1\right)!=\left(n-1\right)\left(n-2\right)!\equiv -\left(n-2\right)!\left(n\right)$. Tehát $\left(n-2\right)!$ és $1!$ azonos maradékot adnak $n$-nel osztva, így $1\ne n-2$ miatt a 3-nál nagyobb $n$ prímszámok sem megfelelők. Tehát $n$ értéke 1, 2 vagy 3 lehet.