38 делителей

[Гость]

Настя утверждает, что нашла наименьшее натуральное число, которое начинается с 38, оканчивается на 38 и имеет ровно 38 делителей!

По словам Насти, это число равно 38535398281407278950346574602134474041938.

Докажите, что Настя права.

[Kreativshik]

[tex]N = 38535398281407278950346574602134474041938[/tex]. Докажем, что это наименьшее натуральное число, которое начинается с 38, оканчивается на 38 и имеет ровно 38 делителей.

[tex]1.[/tex] Если [tex]n[/tex] имеет ровно [tex]38 = 2\cdot 19[/tex] делителей, то [tex]n = p^{37}[/tex] или [tex]n = p^{18}\cdot q[/tex] для простых [tex]p,q[/tex] ([tex]p\neq q[/tex]).

[tex]2.[/tex] Так как [tex]n[/tex] оканчивается на 38, оно чётно. [tex]p^{37}[/tex] чётно только при [tex]p=2[/tex], но [tex]2^{37}\equiv72\pmod{100}\neq38[/tex]. Значит, [tex]n=2\cdot p^{18}[/tex] с нечётным простым [tex]p[/tex].

[tex]3.[/tex] Из [tex]2p^{18}\equiv38\pmod{100}[/tex] получаем [tex]p^{18}\equiv19\pmod{50}[/tex]. Так как [tex]\varphi(50)=20[/tex], то [tex]p^{20}\equiv1\pmod{50}[/tex], откуда [tex]p^{18}\equiv p^{-2}\equiv19\pmod{50}[/tex], т.е. [tex]p^{2}\equiv29\pmod{50}[/tex]. Это даёт [tex]p\equiv23[/tex] или [tex]27\pmod{50}[/tex].

[tex]4.[/tex] Условие начала с 38: [tex]38\cdot10^{39}\le 2p^{18}<39\cdot10^{39}[/tex]. Логарифмируя: [tex]\log_{10}38+39\le\log_{10}2+18\log_{10}p<\log_{10}39+39[/tex]. Подставляя [tex]\log_{10}38\approx1.5798,\ \log_{10}39\approx1.5911,\ \log_{10}2\approx0.3010[/tex], получаем [tex]40.5798\le0.3010+18\log_{10}p<40.5911[/tex], откуда [tex]2.23771\le\log_{10}p<2.23834[/tex], т.е. [tex]p\approx173[/tex].

[tex]5.[/tex] Проверяем [tex]p=173[/tex] ( [tex]173=50\cdot3+23[/tex] ). Вычисление даёт [tex]2\cdot173^{18}=N[/tex]. Для меньших простых вида [tex]50k+23[/tex] или [tex]50k+27[/tex] ( [tex]23,73,127[/tex] ) число [tex]2p^{18}[/tex] либо начинается не с 38, либо меньше [tex]N[/tex]. Следовательно, [tex]N[/tex] — наименьшее.

[tex]6.[/tex] Число делителей [tex]N[/tex] равно [tex](1+1)(18+1)=38[/tex], и оно оканчивается на 38, так как [tex]173^{18}\equiv19\pmod{50}[/tex].

Таким образом, Настя права.

[Гость]

Большое спасибо!