Feladat:	B.3517	Korcsoport: 16-17	Nehézségi fok: átlagos
Füzet:	2003/január, 32. oldal		PDF  |  MathML
Témakör(ök):	Oszthatóság, Maradékos osztás, kongruenciák, Feladat
Hivatkozás(ok):	Feladatok: 2002/január: B.3517

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.   I. megoldás. Mivel a 71 prímszám, Wilson tétele szerint (lásd pl. Freud R. ‐ Gyarmati E. Számelmélet c. egyetemi tankönyvét) $70!+1$ osztható 71-gyel. Elegendő tehát azt megmutatni, hogy $61!$ ugyanazt a maradékot adja 71-gyel osztva, mint $70!$. Vizsgáljuk meg ennek megfelelően az $A=62\cdot 63\cdot \text{...}\cdot 70$ szorzatot. $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle A}& {\displaystyle \equiv \left(71-9\right)\cdot \left(71-8\right)\cdot \left(71-7\right)\cdot \text{...}\cdot \left(71-1\right)\equiv \left(-9\right)\cdot \left(-8\right)\cdot \left(-7\right)\cdot \text{...}\cdot \left(-1\right)=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =72\cdot \left(-7!\right)\equiv -7!=-70\cdot 72\equiv 1\left(\text{mod}71\right)\mathrm{,}}\hfill \end{array}}}\end{array}$ vagyis $70!=A\cdot 61!\equiv 61!\left(\text{mod}71\right)$, amit bizonyítani akartunk.   Megjegyzés. A beérkezett megoldások két csoportba sorolhatók: a Wilson tételt használókra és azokra, amelyekben a 61! maradékát több lépésben számolták ki. Az utóbbi megoldásnak az az előnye, hogy az összes olyan $n$ számot megadhatja, amelyre 71 osztója $n!+1$-nek. Ezek az $n$ értékek a 7, 9, 19, 51, 61, 63. Ezt Bartha Ágnes, Birkner Tamás, Haszpra Tímea és Visnovitz Ferenc ki is emelték dolgozatukban.   II. megoldás. Számoljuk ki, hogy mely $n$ számokra osztható 71-gyel az $n!+1$ ($n$ pozitív egész). Az $n!$ osztási maradékát, $r_n$-t az $\left(n-1\right)!$ osztási maradékából, $r_{n-1}$-ből a következőképpen kaphatjuk meg: $r_n=r_{n-1}\cdot n-71\left[\frac{r_{n-1}\cdot n}{71}\right]$, ahol $\left[x\right]$ az $x$ szám egész részét jelöli. A 71-gyel osztva 70 maradékot adó számokhoz 1-et adva 71-gyel osztható számokat kapunk. Ezek a megjegyzésben már említett számok, közöttük az utolsó előtti a 61. Ezzel feladatunk állítását is beláttuk.