Zadanie
Slavo rád počíta deliteľov. Preto si zobral nepárne prvočíslo $p$. Potom pre každé celé číslo $k$ spĺňajúce $1 \le k \le p - 1$ spočítal počet deliteľov čísla $kp+ 1$, ktoré sú väčšie ako $k$ a menšie ako $p$, a výsledný počet si zapísal na papier. Určte súčet všetkých čísel, čo Slavo napísal na papier.
V prvom rade je dôležité uvedomiť si, čo chceme spočítať. Máme prvočíslo \(p\), zoberieme si všetky čísla \(k\) menšie ako \(p\), spočítame počty deliteľov (označíme si ich ako vyhovujúce alebo \(d\)) čísel \(kp+1\), ktoré sú medzi \(k\) a \(p\) (teda \(k<d<p\)). - Pre výraz \(1p+1\) chceme zistiť, koľkými z deliteľov \({2,3,4,\dots,p-1}\) je deliteľný. - Pre výraz \(2p+1\) chceme zistiť, koľkými z deliteľov \({3,4,5,\dots,p-1}\) je deliteľný. - Pre výraz \(3p+1\) chceme zistiť, koľkými z deliteľov \({4,5,6,\dots,p-1}\) je deliteľný. \(\dots\) - Pre výraz \((p-2)p+1\) chceme zistiť, koľkými z deliteľov \({p-1}\) je deliteľný,
Zapíšme si to do tabuľky (delitele a výrazy, ktoré nás zaujímajú):
| k\(\backslash\)deliteľ | 2 | 3 | 4 | 5 | 6 | … |
|---|---|---|---|---|---|---|
| 1 | p+1 | p+1 | p+1 | p+1 | p+1 | |
| 2 | 2p+1 | 2p+1 | 2p+1 | 2p+1 | ||
| 3 | 3p+1 | 3p+1 | 3p+1 | |||
| 4 | 4p+1 | 4p+1 | ||||
| 5 | 5p+1 | |||||
| … |
Ak sa na to pozrieme z iného uhla (po stĺpcoch), stačí spočítať, či výraz \(p+1\) je deliteľný \(2\)-mi, koľko z výrazov \(\{p+1, 2p+1\}\) je deliteľných \(3\)-mi, koľko z výrazov \(\{p+1, 2p+1,3p+1\}\) je deliteľných \(4\)-mi, … , koľko z \(\{p+1,2p+1,\dots,(p-2)p+1\}\) delí \(p-1\).
Chceme teda zistiť, koľkokrát \(x\) delí výrazy \(\{p+1,2p+1,\dots,(x-1)p+1\}\) (pre \(x=2,\,3,\,4,\,\dots,\,p-1\)). Ak si to vyskúšame pre nejaké konkrétne \(x\) a \(p\), zistíme, že \(x\) delí práve jeden z daných výrazov. Ako to dokázať? Skúsme sa pozrieť na zvyšky výrazov po delení \(x\). Zaujíma nás zvyšok \(0\). Môžeme si všimnúť, že zvyšky výrazov \(p+1,\, 2p+1,\, \dots ,\,(x-1)p+1\) sú všetky rôzne. Ak sa nám to podarí dokázať, tak budeme mať \(x-1\) rôznych zvyškov z \(x\) možných. Potom stačiť ukázať, že ten jeden zvyšok, čo tam chýba nie je \(0\). To ale platí, lebo chýba zvyšok \(0p+1=1\) (čo zrejme nie je deliteľné žiadnym deliteľom).
Nech majú výrazy \(ap+1\) a \(bp+1\) \((0<a,\,b<x)\) rovnaký zvyšok po delení \(x\). Potom \(x\) delí \((ap+1)-(bp+1)=p(a-b).\) Keďže \(p\) je prvočíslo väčšie ako \(x\), tak \(x\) musí deliť \(a-b\), teda \(a\) aj \(b\) majú rovnaký zvyšok po delení \(x\). Preto čísla \(a\) aj \(b\) musia byť rovnaké.
Ľubovoľný deliteľ \(x\) \((1<x<p)\) delí práve jeden výraz \(kp+1\), preto bude zarátaný práve raz. Súčet čísel na papieri bude preto \(p-2\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.