рдЧреБрдгрдирдЦрдВрдб рдХреИрд▓рдХреБрд▓реЗрдЯрд░

рдЧреБрдгрдирдЦрдВрдб рдХреИрд▓рдХреБрд▓реЗрдЯрд░

рдЕрдЧреНрд░рдгреА AI Skill PRO

рдЧрдгрдирд╛ рджрд░реНрдЬ рдХрд░реЗрдВ

рд╕реВрддреНрд░ (рдлреЙрд░реНрдореВрд▓рд╛)

F(N)={dтИИтДд+:Nmodd=0}тЗТ(d,Nd),dтЙдNрдЬрд╣рд╛рдБ{N=|рд╕рдВрдЦреНрдпрд╛|N=p1a1┬╖p2a2тЛпpkakрд╕рдВрдЦреНрдпрд╛ (рдЧрдгрдирд╛)=(a1+1)(a2+1)тЛп(ak+1)\begin{gathered} F(N) = \{\, d \in \mathbb{Z}^{+} : N \bmod d = 0 \,\} \quad\Rightarrow\quad \left( d,\ \frac{N}{d} \right),\ \ d \le \sqrt{N} \\[1.5em] \text{рдЬрд╣рд╛рдБ}\quad \left\{ \begin{aligned} N &= \left| \text{рд╕рдВрдЦреНрдпрд╛} \right| \\ N &= p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdots p_{k}^{a_{k}} \\ \text{рд╕рдВрдЦреНрдпрд╛ (рдЧрдгрдирд╛)} &= \left( a_{1}+1 \right)\left( a_{2}+1 \right) \cdots \left( a_{k}+1 \right) \end{aligned} \right. \end{gathered}
рдЙрдкрдпреЛрдЧ рдЖрдБрдХрдбрд╝реЗ

рд╡рд┐рдЬреНрдЮрд╛рдкрди

рдкрд░рд┐рдгрд╛рдо

21 рдХрд╛ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди
21 = 3 ├Ч 7
this number is рднрд╛рдЬреНрдп
рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ 4
рд╕рднреА рдЧреБрдгрдирдЦрдВрдб 1, 3, 7, 21
рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо (1, 21), (3, 7)

рдЗрд╕ рдкреЗрдЬ рдкрд░ рддреНрд░реБрдЯрд┐ рдХреА рд░рд┐рдкреЛрд░реНрдЯ рдХрд░реЗрдВ

рдЧреБрдгрдирдЦрдВрдб рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХреНрдпрд╛ рд╣реИ?

рдпрд╣ рдЯреВрд▓ рдХрд┐рд╕реА рднреА рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рдХреЛ рд▓реЗрдХрд░ рдЙрд╕рдХреА рд╡рд┐рднрд╛рдЬреНрдпрддрд╛ рдХреЗ рдмрд╛рд░реЗ рдореЗрдВ рд╣рд░ рдЬрд╝рд░реВрд░реА рдЬрд╛рдирдХрд╛рд░реА рдирд┐рдХрд╛рд▓ рджреЗрддрд╛ рд╣реИ: рд╕рднреА рдзрдирд╛рддреНрдордХ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рдкреВрд░реА рд╕реВрдЪреА, рдЙрд╕рдХреЗ рд╕рд╛рд░реЗ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо, рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рдФрд░ рдпрд╣ рдХрд┐ рд╡рд╣ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рд╣реИ рдпрд╛ рднрд╛рдЬреНрдпред рдЧреБрдгрдирдЦрдВрдб рдирд┐рдХрд╛рд▓рдирд╛ рдЕрдВрдХрдЧрдгрд┐рдд, рдмреАрдЬрдЧрдгрд┐рдд рдФрд░ рд╕рдВрдЦреНрдпрд╛ рд╕рд┐рджреНрдзрд╛рдВрдд рдХрд╛ рдПрдХ рдмреБрдирд┐рдпрд╛рджреА рдХреМрд╢рд▓ рд╣реИ, рдФрд░ рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдкрд▓ рднрд░ рдореЗрдВ рдЖрдкрдХреЗ рд▓рд┐рдП рд╕рд╛рд░рд╛ рд╡рд┐рднрд╛рдЬрди рдХрд░рдХреЗ рджрд┐рдЦрд╛ рджреЗрддрд╛ рд╣реИред

рдЗрд╕рдХрд╛ рдЗрд╕реНрддреЗрдорд╛рд▓ рдХреИрд╕реЗ рдХрд░реЗрдВ

"рдЗрд╕ рд╕рдВрдЦреНрдпрд╛ рдХреЗ рдЧреБрдгрдирдЦрдВрдб рдЬреНрдЮрд╛рдд рдХрд░реЗрдВ:" рд╡рд╛рд▓реЗ рдмреЙрдХреНрд╕ рдореЗрдВ рдХреЛрдИ рдкреВрд░реНрдгрд╛рдВрдХ рдЯрд╛рдЗрдк рдХрд░реЗрдВ рдФрд░ рд╕рдмрдорд┐рдЯ рдХрд░реЗрдВред рдЛрдгрд╛рддреНрдордХ рд╕рдВрдЦреНрдпрд╛рдПрдВ рднреА рд╕реНрд╡реАрдХрд╛рд░ рдХреА рдЬрд╛рддреА рд╣реИрдВ тАФ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдЙрд╕рдХреЗ рдирд┐рд░рдкреЗрдХреНрд╖ рдорд╛рди рдХреЗ рдЧреБрдгрдирдЦрдВрдб рдирд┐рдХрд╛рд▓рддрд╛ рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ рдкрд░рдВрдкрд░рд╛ рдХреЗ рдЕрдиреБрд╕рд╛рд░ рдЧреБрдгрдирдЦрдВрдб рдзрдирд╛рддреНрдордХ рд╣реЛрддреЗ рд╣реИрдВред рджрд╢рдорд▓рд╡ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рдирд┐рдХрдЯрддрдо рдкреВрд░реНрдгрд╛рдВрдХ рддрдХ рдкреВрд░реНрдгрд╛рдВрдХрд┐рдд рдХрд░ рджрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред рдкрд░рд┐рдгрд╛рдо рдкреИрдирд▓ рдореЗрдВ рд╕рдмрд╕реЗ рдКрдкрд░ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рджрд┐рдЦрддрд╛ рд╣реИ, рдФрд░ рдЙрд╕рдХреЗ рдиреАрдЪреЗ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛, рдкреВрд░реА рдЧреБрдгрдирдЦрдВрдб рд╕реВрдЪреА рдФрд░ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо рджрд┐рдП рдЬрд╛рддреЗ рд╣реИрдВред

рд╕реВрддреНрд░ рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛

рдХрд┐рд╕реА рд╕рдВрдЦреНрдпрд╛ \(N\) рдХреЗ рд╣рд░ рдЧреБрдгрдирдЦрдВрдб рдХреЛ рдвреВрдВрдврдиреЗ рдХреЗ рд▓рд┐рдП рд╣рдореЗрдВ рдХреЗрд╡рд▓ \(N\) рдХреЗ рд╡рд░реНрдЧрдореВрд▓ рддрдХ рдХреЗ рд╕рдВрднрд╛рд╡рд┐рдд рднрд╛рдЬрдХреЛрдВ рдХреА рдЬрд╛рдВрдЪ рдХрд░рдиреА рд╣реЛрддреА рд╣реИред рд╣рд░ рдРрд╕реЗ рднрд╛рдЬрдХ \(i\) рдХреЗ рд▓рд┐рдП рдЬреЛ \(N\) рдХреЛ рдкреВрд░реА рддрд░рд╣ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░рддрд╛ рд╣реИ, \(i\) рдФрд░ \(N/i\) рджреЛрдиреЛрдВ рд╣реА рдЧреБрдгрдирдЦрдВрдб рд╣реЛрддреЗ рд╣реИрдВред рдпрд╣ рддрд░реАрдХрд╛ \(N\) рддрдХ рдХреА рд╣рд░ рд╕рдВрдЦреНрдпрд╛ рдЬрд╛рдВрдЪрдиреЗ рд╕реЗ рдХрд╣реАрдВ рдЬрд╝реНрдпрд╛рджрд╛ рддреЗрдЬрд╝ рд╣реИред

$$i \le \lfloor \sqrt{N} \rfloor$$

рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рдХреЗ рд▓рд┐рдП рд╣рдо рдмрд╛рд░-рдмрд╛рд░ рд╕рдмрд╕реЗ рдЫреЛрдЯреЗ рдЕрднрд╛рдЬреНрдп (рдкрд╣рд▓реЗ 2, рдлрд┐рд░ 3, 5, 7, ...) рд╕реЗ рднрд╛рдЧ рджреЗрддреЗ рдЬрд╛рддреЗ рд╣реИрдВ рдЬрдм рддрдХ рдХреЗрд╡рд▓ 1 рди рдмрдЪреЗ, рдФрд░ рд╣рд░ рдЕрднрд╛рдЬреНрдп рд╡ рдЙрд╕рдХреЗ рдЖрдиреЗ рдХреА рд╕рдВрдЦреНрдпрд╛ рдХреЛ рдШрд╛рддрд╛рдВрдХ рдХреЗ рд░реВрдк рдореЗрдВ рджрд░реНрдЬ рдХрд░ рд▓реЗрддреЗ рд╣реИрдВред

$$N = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$$

рд╡рд┐рдЬреНрдЮрд╛рдкрди
60 рдХрд╛ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рдПрдХ рдЧреБрдгрдирдЦрдВрдб рд╡реГрдХреНрд╖ рдХреЗ рд░реВрдк рдореЗрдВ рджрд┐рдЦрд╛рдпрд╛ рдЧрдпрд╛, рдЬреЛ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб 2, 2, 3, 5 рдореЗрдВ рд╢рд╛рдЦрд╛рдПрдБ рдмрдирд╛рддрд╛ рд╣реИ
рдЧреБрдгрдирдЦрдВрдб рд╡реГрдХреНрд╖ рдХрд┐рд╕реА рд╕рдВрдЦреНрдпрд╛ рдХреЛ рдЙрд╕рдХреЗ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдореЗрдВ рддреЛрдбрд╝рддрд╛ рд╣реИред

рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдЙрджрд╛рд╣рд░рдг: 21

21 рдХрд╛ рд╡рд░реНрдЧрдореВрд▓ рд▓рдЧрднрдЧ 4.58 рд╣реИ, рдЗрд╕рд▓рд┐рдП рд╣рдо 1, 2, 3, 4 рдХреА рдЬрд╛рдВрдЪ рдХрд░рддреЗ рд╣реИрдВред рд╣рдореЗрдВ рдорд┐рд▓рддрд╛ рд╣реИ \(21 = 1 \times 21\) рдФрд░ \(21 = 3 \times 7\), рдЬрд┐рд╕рд╕реЗ рдЧреБрдгрдирдЦрдВрдб рдмрдирддреЗ рд╣реИрдВ 1, 3, 7, 21 (рдЪрд╛рд░ рдЧреБрдгрдирдЦрдВрдб) рдФрд░ рдпреБрдЧреНрдо рдмрдирддреЗ рд╣реИрдВ (1, 21) рддрдерд╛ (3, 7)ред 21 рдХреЛ 3 рд╕реЗ рднрд╛рдЧ рджреЗрдиреЗ рдкрд░ 7 рдмрдЪрддрд╛ рд╣реИ, рдЬреЛ рдЕрднрд╛рдЬреНрдп рд╣реИ, рдЗрд╕рд▓рд┐рдП \(21 = 3 \times 7\)ред рдЪреВрдВрдХрд┐ рдЗрд╕рдХреЗ рджреЛ рд╕реЗ рдЕрдзрд┐рдХ рдЧреБрдгрдирдЦрдВрдб рд╣реИрдВ, рдЗрд╕рд▓рд┐рдП 21 рдПрдХ рднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рд╣реИред

21 рдХреЗ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо рдЖрдпрддрд╛рдХрд╛рд░ рд╕рд░рдгрд┐рдпреЛрдВ рдХреЗ рд░реВрдк рдореЗрдВ рджрд┐рдЦрд╛рдП рдЧрдП: 1 рдЧреБрдгрд╛ 21 рдФрд░ 3 рдЧреБрдгрд╛ 7
рд╕рдВрдЦреНрдпрд╛ 21 рдХреЗ рджреЛ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо рд╣реИрдВ: 1x21 рдФрд░ 3x7ред

рдЕрдзрд┐рдХ рдХрд╛рд░реНрдп рдХрд┐рдП рдЧрдП рдЙрджрд╛рд╣рд░рдг: 36, 60 рдФрд░ 97

рд╣рд░ рдЙрджрд╛рд╣рд░рдг рдореЗрдВ рд╡рд╣реА рд╡рд┐рдзрд┐ рдкреНрд░рдпреБрдХреНрдд рд╣реЛрддреА рд╣реИ рдЬреЛ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдореЗрдВ рд╣реИ: рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рднрд╛рдЬрдХреЛрдВ \(d\) рдХреА рдЬрд╛рдБрдЪ \(\sqrt{N}\) рддрдХ рдХрд░реЗрдВ, рд╣рд░ рдПрдХ рдХреЛ \(N/d\) рдХреЗ рд╕рд╛рде рдЬреЛрдбрд╝реЗрдВ, рдлрд┐рд░ рдЕрднрд╛рдЬреНрдп рдШрд╛рддрд╛рдВрдХреЛрдВ рд╕реЗ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рдЧрд┐рдирддреА рдХрд░реЗрдВред

рдЙрджрд╛рд╣рд░рдг 1: N = 36 (рдПрдХ рдкреВрд░реНрдг рд╡рд░реНрдЧ)

  1. \(\sqrt{36} = 6\), рдЗрд╕рд▓рд┐рдП \(d = 1\) рд╕реЗ \(6\) рддрдХ рдЬрд╛рдБрдЪ рдХрд░реЗрдВред
  2. рд╡реЗ рднрд╛рдЬрдХ рдЬреЛ рдХрд╛рдо рдХрд░рддреЗ рд╣реИрдВ: 1, 2, 3, 4, 6ред (5 рдХрд╛рдо рдирд╣реАрдВ рдХрд░рддрд╛: \(36 \bmod 5 = 1\)ред)
  3. рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо: (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)ред рдпреБрдЧреНрдо (6, 6) рд╡рд╣реА рдЧреБрдгрдирдЦрдВрдб рджреЛрд╣рд░рд╛рддрд╛ рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ 36 рдПрдХ рдкреВрд░реНрдг рд╡рд░реНрдЧ рд╣реИред
  4. рд╕рднреА рдЧреБрдгрдирдЦрдВрдб: 1, 2, 3, 4, 6, 9, 12, 18, 36ред
  5. рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди: \(36 = 2^{2} \cdot 3^{2}\)ред
  6. рдЧрд┐рдирддреА: \((2+1)(2+1) = 9\) рдЧреБрдгрдирдЦрдВрдб, рдЬреЛ рд╕реВрдЪреА рд╕реЗ рдореЗрд▓ рдЦрд╛рддрд╛ рд╣реИред рдкреВрд░реНрдг рд╡рд░реНрдЧреЛрдВ рдХреЗ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рд╣рдореЗрд╢рд╛ рд╡рд┐рд╖рдо рд╣реЛрддреА рд╣реИ: 9ред

рдЙрджрд╛рд╣рд░рдг 2: N = 60

  1. \(\sqrt{60} \approx 7.75\), рдЗрд╕рд▓рд┐рдП \(d = 1\) рд╕реЗ \(7\) рддрдХ рдЬрд╛рдБрдЪ рдХрд░реЗрдВред
  2. рд╡реЗ рднрд╛рдЬрдХ рдЬреЛ рдХрд╛рдо рдХрд░рддреЗ рд╣реИрдВ: 1, 2, 3, 4, 5, 6ред (7 рдХрд╛рдо рдирд╣реАрдВ рдХрд░рддрд╛: \(60 = 8 \cdot 7 + 4\)ред)
  3. рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо: (1, 60), (2, 30), (3, 20), (4, 15), (5, 12), (6, 10)ред рдпрд╛рдиреА рдЫрд╣ рдпреБрдЧреНрдо рд╣реИрдВред
  4. рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди: \(60 = 2^{2} \cdot 3^{1} \cdot 5^{1}\)ред
  5. рдЧрд┐рдирддреА: \((2+1)(1+1)(1+1) = 3 \cdot 2 \cdot 2 = 12\) рдЧреБрдгрдирдЦрдВрдб, рдФрд░ рдЫрд╣ рдпреБрдЧреНрдо ├Ч 2 = 12ред
  6. рд╕рднреА рдЧреБрдгрдирдЦрдВрдб: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60ред

рдЙрджрд╛рд╣рд░рдг 3: N = 97 (рдПрдХ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛)

  1. \(\sqrt{97} \approx 9.85\), рдЗрд╕рд▓рд┐рдП рдХреЗрд╡рд▓ 9 рддрдХ рдХреЗ рднрд╛рдЬрдХреЛрдВ рдХреА рдЬрд╛рдБрдЪ рдХрд░рдиреА рд╣реИред рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ 2, 3, 5, 7 рдХреА рдЬрд╛рдБрдЪ рдкрд░реНрдпрд╛рдкреНрдд рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ 9 рддрдХ рдХрд╛ рдХреЛрдИ рдЕрдиреНрдп рднрд╛рдЬрдХ рдЗрдирдореЗрдВ рд╕реЗ рдХрд┐рд╕реА рдХрд╛ рдЧреБрдгрдЬ рд╣реИред
  2. \(97 = 48 \cdot 2 + 1\) (рд╢реЗрд╖рдлрд▓ 1), \(97 = 32 \cdot 3 + 1\) (рд╢реЗрд╖рдлрд▓ 1), \(97 = 19 \cdot 5 + 2\) (рд╢реЗрд╖рдлрд▓ 2), \(97 = 13 \cdot 7 + 6\) (рд╢реЗрд╖рдлрд▓ 6)ред
  3. 1 рдХреЗ рдЕрд▓рд╛рд╡рд╛ рдХреЛрдИ рднрд╛рдЬрдХ 97 рдХреЛ рд╡рд┐рднрд╛рдЬрд┐рдд рдирд╣реАрдВ рдХрд░рддрд╛, рдЗрд╕рд▓рд┐рдП рдЗрд╕рдХрд╛ рдПрдХрдорд╛рддреНрд░ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо (1, 97) рд╣реИред
  4. рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди: \(97 = 97^{1}\), рдЗрд╕рд▓рд┐рдП рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рдЧрд┐рдирддреА \((1+1) = 2\) рд╣реИред 97 рдПрдХ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рд╣реИред

рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдПрдБ рдФрд░ рд╡рд┐рднрд╛рдЬреНрдпрддрд╛ рдирд┐рдпрдо рд╕рдВрджрд░реНрдн

100 рддрдХ рдХреА 25 рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдПрдБ

рд╕реАрдорд╛ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдПрдБ
1тАУ25 2, 3, 5, 7, 11, 13, 17, 19, 23
26тАУ50 29, 31, 37, 41, 43, 47
51тАУ75 53, 59, 61, 67, 71, 73
76тАУ100 79, 83, 89, 97

рдпрд╛рдиреА 9 + 6 + 6 + 4 = 25 рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдПрдБред рд╕рдВрдЦреНрдпрд╛ 2 рдПрдХрдорд╛рддреНрд░ рд╕рдо рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рд╣реИред

рд╡рд┐рднрд╛рдЬреНрдпрддрд╛ рдирд┐рдпрдо

рднрд╛рдЬрдХ рдирд┐рдпрдо рдЙрджрд╛рд╣рд░рдг
2 рдЕрдВрддрд┐рдо рдЕрдВрдХ рд╕рдо рд╣реИ (0, 2, 4, 6, 8) 418 рдХрд╛ рдЕрдВрддрд┐рдо рдЕрдВрдХ 8 рд╣реИ, рдЗрд╕рд▓рд┐рдП рдпрд╣ 2 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ
3 рдЕрдВрдХреЛрдВ рдХрд╛ рдпреЛрдЧ 3 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ 123: 1+2+3 = 6, рдЗрд╕рд▓рд┐рдП рдпрд╣ 3 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ
4 рдЕрдВрддрд┐рдо рджреЛ рдЕрдВрдХреЛрдВ рд╕реЗ рдмрдиреА рд╕рдВрдЦреНрдпрд╛ 4 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ 516: 16 = 4 ┬╖ 4, рдЗрд╕рд▓рд┐рдП рдпрд╣ 4 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ
5 рдЕрдВрддрд┐рдо рдЕрдВрдХ 0 рдпрд╛ 5 рд╣реИ 735 рдХрд╛ рдЕрдВрддрд┐рдо рдЕрдВрдХ 5 рд╣реИ
6 2 рдФрд░ 3 both рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ 138 рд╕рдо рд╣реИ рдФрд░ 1+3+8 = 12, рдЗрд╕рд▓рд┐рдП рдпрд╣ 6 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ
8 рдЕрдВрддрд┐рдо рддреАрди рдЕрдВрдХреЛрдВ рд╕реЗ рдмрдиреА рд╕рдВрдЦреНрдпрд╛ 8 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ 3,128: 128 = 16 ┬╖ 8, рдЗрд╕рд▓рд┐рдП рдпрд╣ 8 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ
9 рдЕрдВрдХреЛрдВ рдХрд╛ рдпреЛрдЧ 9 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ 729: 7+2+9 = 18, рдЗрд╕рд▓рд┐рдП рдпрд╣ 9 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ
10 рдЕрдВрддрд┐рдо рдЕрдВрдХ 0 рд╣реИ 470 рдХрд╛ рдЕрдВрддрд┐рдо рдЕрдВрдХ 0 рд╣реИ
11 рдПрдХрд╛рдВрддрд░ рдЕрдВрдХреЛрдВ рдХрд╛ рдпреЛрдЧ (0 рд╕рд╣рд┐рдд) 11 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ 2,728: 2 тИТ 7 + 2 тИТ 8 = тИТ11, рдЗрд╕рд▓рд┐рдП рдпрд╣ 11 рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ
рд╡рд┐рдЬреНрдЮрд╛рдкрди

рдЧреБрдгрдирдЦрдВрдб рд╕реЗ рдЬреБрдбрд╝реЗ рд╢рдмреНрджреЛрдВ рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛

рдЧреБрдгрдирдЦрдВрдб (рднрд╛рдЬрдХ)
рдПрдХ рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХ рдЬреЛ рдХрд┐рд╕реА рд╕рдВрдЦреНрдпрд╛ рдХреЛ рдмрд┐рдирд╛ рд╢реЗрд╖рдлрд▓ рдХреЗ рдкреВрд░реА рддрд░рд╣ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░рддрд╛ рд╣реИред 4, 12 рдХрд╛ рдЧреБрдгрдирдЦрдВрдб рд╣реИ рдХреНрдпреЛрдВрдХрд┐ \(12 \bmod 4 = 0\)ред
рдЧреБрдгрдЬ
рдХрд┐рд╕реА рд╕рдВрдЦреНрдпрд╛ рдХреЛ рдХрд┐рд╕реА рдкреВрд░реНрдгрд╛рдВрдХ рд╕реЗ рдЧреБрдгрд╛ рдХрд░рдиреЗ рдХрд╛ рдкрд░рд┐рдгрд╛рдоред 12, 24 рдФрд░ 36, 12 рдХреЗ рдЧреБрдгрдЬ рд╣реИрдВред рдпрджрд┐ \(a\), \(b\) рдХрд╛ рдЧреБрдгрдирдЦрдВрдб рд╣реИ, рддреЛ \(b\), \(a\) рдХрд╛ рдЧреБрдгрдЬ рд╣реИред
рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо
рджреЛ рдЧреБрдгрдирдЦрдВрдб рдЬрд┐рдирдХрд╛ рдЧреБрдгрдирдлрд▓ рд╡рд╣ рд╕рдВрдЦреНрдпрд╛ рд╣реИ, рдЬреИрд╕реЗ 60 рдХреЗ рд▓рд┐рдП (3, 20)ред \(\sqrt{N}\) рддрдХ рдХреЗ рднрд╛рдЬрдХреЛрдВ рдХреА рдЬрд╛рдБрдЪ рдХрд░рдиреЗ рд╕реЗ рд╕рднреА рдпреБрдЧреНрдо рдорд┐рд▓ рдЬрд╛рддреЗ рд╣реИрдВред
рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛
1 рд╕реЗ рдмрдбрд╝рд╛ рдПрдХ рдкреВрд░реНрдгрд╛рдВрдХ рдЬрд┐рд╕рдХреЗ рдареАрдХ рджреЛ рдзрдирд╛рддреНрдордХ рдЧреБрдгрдирдЦрдВрдб рд╣реЛрдВ: 1 рдФрд░ рд╕реНрд╡рдпрдВ (рдЬреИрд╕реЗ 2, 3, 5, 97)ред
рднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ (рд╕рдВрдпреБрдХреНрдд рд╕рдВрдЦреНрдпрд╛)
1 рд╕реЗ рдмрдбрд╝рд╛ рдПрдХ рдкреВрд░реНрдгрд╛рдВрдХ рдЬрд┐рд╕рдХреЗ рджреЛ рд╕реЗ рдЕрдзрд┐рдХ рдзрдирд╛рддреНрдордХ рдЧреБрдгрдирдЦрдВрдб рд╣реЛрдВ (рдЬреИрд╕реЗ 12 рдпрд╛ 91)ред
рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди
рдХрд┐рд╕реА рд╕рдВрдЦреНрдпрд╛ рдХреЛ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рдЧреБрдгрдирдлрд▓ рдХреЗ рд░реВрдк рдореЗрдВ рд▓рд┐рдЦрдирд╛, рдЬреИрд╕реЗ \(60 = 2^{2} \cdot 3 \cdot 5\)ред рдЕрдВрдХрдЧрдгрд┐рдд рдХреЗ рдореВрд▓рднреВрдд рдкреНрд░рдореЗрдп рдХреЗ рдЕрдиреБрд╕рд╛рд░, рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреЗ рдХреНрд░рдо рдХреЛ рдЫреЛрдбрд╝рдХрд░ рдпрд╣ рдЕрджреНрд╡рд┐рддреАрдп рд╣реИред
рдкреВрд░реНрдг рд╡рд░реНрдЧ
рдПрдХ рдкреВрд░реНрдгрд╛рдВрдХ рдЬреЛ рдХрд┐рд╕реА рдкреВрд░реНрдгрд╛рдВрдХ рдХрд╛ рд╡рд░реНрдЧ рд╣реЛ (рдЬреИрд╕реЗ 36 = 6┬▓)ред рдЗрд╕рдХреЗ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рдореЗрдВ рд╣рд░ рдШрд╛рддрд╛рдВрдХ рд╕рдо рд╣реЛрддрд╛ рд╣реИ, рдФрд░ рдЗрд╕рдХреЗ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рд╡рд┐рд╖рдо рд╣реЛрддреА рд╣реИред
рдЗрдХрд╛рдИ (1)
рд╕рдВрдЦреНрдпрд╛ 1 рд╣рд░ рдкреВрд░реНрдгрд╛рдВрдХ рдХрд╛ рдЧреБрдгрдирдЦрдВрдб рд╣реИред рдпрд╣ рди рдЕрднрд╛рдЬреНрдп рд╣реИ рди рднрд╛рдЬреНрдп, рдФрд░ рдЗрд╕реА рд╕реЗ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рдЕрджреНрд╡рд┐рддреАрдп рд░рд╣рддрд╛ рд╣реИред
рд╕рд╣рдЕрднрд╛рдЬреНрдп
рджреЛ рдкреВрд░реНрдгрд╛рдВрдХ рдЬрд┐рдирдХрд╛ рдПрдХрдорд╛рддреНрд░ рдЙрднрдпрдирд┐рд╖реНрда рдзрдирд╛рддреНрдордХ рдЧреБрдгрдирдЦрдВрдб 1 рд╣реИ, рдпрд╛рдиреА рдЙрдирдХрд╛ рдорд╣рддреНрддрдо рд╕рдорд╛рдкрд╡рд░реНрддрдХ 1 рд╣реИ (рдЬреИрд╕реЗ 8 рдФрд░ 15)ред рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдПрдБ рд╕реНрд╡рдпрдВ рдЕрднрд╛рдЬреНрдп рд╣реЛрдирд╛ рдЖрд╡рд╢реНрдпрдХ рдирд╣реАрдВ рд╣реИред
рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛
рдпрджрд┐ \(N = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}\), рддреЛ рдзрдирд╛рддреНрдордХ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рд╕рднреА рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдкрд░ (рдШрд╛рддрд╛рдВрдХ + 1) рдХреЗ рдЧреБрдгрдирдлрд▓ рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддреА рд╣реИ: \((a_{1}+1)(a_{2}+1)\cdots(a_{k}+1)\)ред

рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓

рдХреНрдпрд╛ 1 рдЕрднрд╛рдЬреНрдп рд╣реИ рдпрд╛ рднрд╛рдЬреНрдп? рдЗрдирдореЗрдВ рд╕реЗ рдХреЛрдИ рдирд╣реАрдВред рдкрд░рд┐рднрд╛рд╖рд╛ рдХреЗ рдЕрдиреБрд╕рд╛рд░ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдХреЗ рдареАрдХ рджреЛ рдЕрд▓рдЧ-рдЕрд▓рдЧ рдЧреБрдгрдирдЦрдВрдб рд╣реЛрддреЗ рд╣реИрдВ; 1 рдХрд╛ рдХреЗрд╡рд▓ рдПрдХ рд╣реА рдЧреБрдгрдирдЦрдВрдб рд╣реИ, рдЗрд╕рд▓рд┐рдП рдпрд╣ рдПрдХ рдЗрдХрд╛рдИ (рдпреВрдирд┐рдЯ) рдорд╛рдиреА рдЬрд╛рддреА рд╣реИред

рдФрд░ 0 рдХрд╛ рдХреНрдпрд╛? рд╣рд░ рдкреВрд░реНрдгрд╛рдВрдХ 0 рдХреЛ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░ рджреЗрддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП рдЧреБрдгрдирдЦрдВрдбрди рдХреЗ рд▓рд┐рдП рдпрд╣ рдЕрдкрд░рд┐рднрд╛рд╖рд┐рдд рд╣реИ рдФрд░ рдЗрд╕реЗ рди рдЕрднрд╛рдЬреНрдп рди рднрд╛рдЬреНрдп рдорд╛рдирд╛ рдЬрд╛рддрд╛ рд╣реИред

рдкреВрд░реНрдг рд╡рд░реНрдЧреЛрдВ рдХреЗ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рд╡рд┐рд╖рдо рдХреНрдпреЛрдВ рд╣реЛрддреА рд╣реИ? рдХреНрдпреЛрдВрдХрд┐ рд╡рд░реНрдЧрдореВрд▓ рдЦреБрдж рдЕрдкрдиреЗ рд╕рд╛рде рдпреБрдЧреНрдо рдмрдирд╛рддрд╛ рд╣реИ (36 рдХреЗ рд▓рд┐рдП рдпреБрдЧреНрдо (6, 6) рд╣реИ), рдЗрд╕рд▓рд┐рдП рд╡рд╣ рдЧреБрдгрдирдЦрдВрдб рджреЛ рдмрд╛рд░ рдирд╣реАрдВ рдмрд▓реНрдХрд┐ рдПрдХ рд╣реА рдмрд╛рд░ рдЧрд┐рдирд╛ рдЬрд╛рддрд╛ рд╣реИред

рдЕрдВрддрд┐рдо рдЕрдкрдбреЗрдЯ:

рдЧрдгрд┐рдд рдФрд░ рд╕рд╛рдВрдЦреНрдпрд┐рдХреА рдореЗрдВ рд╕рдмрд╕реЗ рд▓реЛрдХрдкреНрд░рд┐рдп

рдЧрдгрд┐рдд рдФрд░ рд╕рд╛рдВрдЦреНрдпрд┐рдХреА рдХреЗ рд╕рднреА рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рджреЗрдЦреЗрдВ