លំហាត់នព្វន្ត៖ សិស្សពូកែអាមេរិច AIME ១៩៩៥

តាង $n=2^{31}3^{19}$ ។ តើមានចំនួនគត់វិជ្ជមានចំនួនប៉ុន្មានដែលជាតួចែករបស់ $n^2$ ហើយមានតំលៃតូចជាង $n$ និងចែក $n$ មិនដាច់?

ចំលើយ

តាង $n=p^r q^s$ ដែល $p$ និង $q$ ជាចំនួនបឋមពីរផ្សេងគ្នា។ យើងមាន $n^2=p^{2r} q^{2s}$ ។ ដូច្នេះ $n^2$ មានតួចែកចំនួន $(2r+1)(2s+1)$ ដែលតួចែកទាំងនោះមាន៖

$p^0 q^0,p^1 q^0,\dotsi,p^{2r} q^0,p^0 q^1,p^1 q^1,\dotsi$

យើងដឹងថា បើ $d$ ជាតួចែកចែករបស់ $n^2$ នោះ $d'=\frac{n^2}{d}$ ក៏ជាតួចែករបស់ $n^2$ ដែរ។ បើ $d<n$ នោះ $d'>n$ ។ យើងទាញបានថា ចំនួនតួចែកតូចជាង $n$ ស្មើនឹងចំនួនតួចែកធំជាង $n$ ដូច្នេះតួចែកតូចជាង $n$ មានចំនួន

$\displaystyle \frac{(2r+1)(2s+1)-1}{2}=2rs+r+s$

ដោយ $n=p^r q^s$ នោះ $n$ មានតួចែកវិជ្ជមានចំនួន $(r+1)(s+1)$ ដោយរាប់បញ្ចូលទាំង $n$ ខ្លួនវា។ ដោយមិនគិតខ្លួនវាចូល ចំនួនតួចែករបស់ $n$ មានចំនួន $(r+1)(s+1)-1$ ។ យើងដឹងថា គ្រប់តួចែករបស់ $n$ សុទ្ធតែជាតួចែករបស់ $n^2$ ។ ដូច្នេះតួចែករបស់ $n^2$ ដែលតូចជាង $n$ ហើយមិនមែនជាតួចែករបស់ $n$ មានចំនួន