рдЧреБрдгрдирдЦрдВрдб рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХреНрдпрд╛ рд╣реИ?
рдпрд╣ рдЯреВрд▓ рдХрд┐рд╕реА рднреА рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рдХреЛ рд▓реЗрдХрд░ рдЙрд╕рдХреА рд╡рд┐рднрд╛рдЬреНрдпрддрд╛ рдХреЗ рдмрд╛рд░реЗ рдореЗрдВ рд╣рд░ рдЬрд╝рд░реВрд░реА рдЬрд╛рдирдХрд╛рд░реА рдирд┐рдХрд╛рд▓ рджреЗрддрд╛ рд╣реИ: рд╕рднреА рдзрдирд╛рддреНрдордХ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рдкреВрд░реА рд╕реВрдЪреА, рдЙрд╕рдХреЗ рд╕рд╛рд░реЗ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо, рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рдФрд░ рдпрд╣ рдХрд┐ рд╡рд╣ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рд╣реИ рдпрд╛ рднрд╛рдЬреНрдпред рдЧреБрдгрдирдЦрдВрдб рдирд┐рдХрд╛рд▓рдирд╛ рдЕрдВрдХрдЧрдгрд┐рдд, рдмреАрдЬрдЧрдгрд┐рдд рдФрд░ рд╕рдВрдЦреНрдпрд╛ рд╕рд┐рджреНрдзрд╛рдВрдд рдХрд╛ рдПрдХ рдмреБрдирд┐рдпрд╛рджреА рдХреМрд╢рд▓ рд╣реИ, рдФрд░ рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдкрд▓ рднрд░ рдореЗрдВ рдЖрдкрдХреЗ рд▓рд┐рдП рд╕рд╛рд░рд╛ рд╡рд┐рднрд╛рдЬрди рдХрд░рдХреЗ рджрд┐рдЦрд╛ рджреЗрддрд╛ рд╣реИред
рдЗрд╕рдХрд╛ рдЗрд╕реНрддреЗрдорд╛рд▓ рдХреИрд╕реЗ рдХрд░реЗрдВ
"рдЗрд╕ рд╕рдВрдЦреНрдпрд╛ рдХреЗ рдЧреБрдгрдирдЦрдВрдб рдЬреНрдЮрд╛рдд рдХрд░реЗрдВ:" рд╡рд╛рд▓реЗ рдмреЙрдХреНрд╕ рдореЗрдВ рдХреЛрдИ рдкреВрд░реНрдгрд╛рдВрдХ рдЯрд╛рдЗрдк рдХрд░реЗрдВ рдФрд░ рд╕рдмрдорд┐рдЯ рдХрд░реЗрдВред рдЛрдгрд╛рддреНрдордХ рд╕рдВрдЦреНрдпрд╛рдПрдВ рднреА рд╕реНрд╡реАрдХрд╛рд░ рдХреА рдЬрд╛рддреА рд╣реИрдВ тАФ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдЙрд╕рдХреЗ рдирд┐рд░рдкреЗрдХреНрд╖ рдорд╛рди рдХреЗ рдЧреБрдгрдирдЦрдВрдб рдирд┐рдХрд╛рд▓рддрд╛ рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ рдкрд░рдВрдкрд░рд╛ рдХреЗ рдЕрдиреБрд╕рд╛рд░ рдЧреБрдгрдирдЦрдВрдб рдзрдирд╛рддреНрдордХ рд╣реЛрддреЗ рд╣реИрдВред рджрд╢рдорд▓рд╡ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рдирд┐рдХрдЯрддрдо рдкреВрд░реНрдгрд╛рдВрдХ рддрдХ рдкреВрд░реНрдгрд╛рдВрдХрд┐рдд рдХрд░ рджрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред рдкрд░рд┐рдгрд╛рдо рдкреИрдирд▓ рдореЗрдВ рд╕рдмрд╕реЗ рдКрдкрд░ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рджрд┐рдЦрддрд╛ рд╣реИ, рдФрд░ рдЙрд╕рдХреЗ рдиреАрдЪреЗ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛, рдкреВрд░реА рдЧреБрдгрдирдЦрдВрдб рд╕реВрдЪреА рдФрд░ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо рджрд┐рдП рдЬрд╛рддреЗ рд╣реИрдВред
рд╕реВрддреНрд░ рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛
рдХрд┐рд╕реА рд╕рдВрдЦреНрдпрд╛ \(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}$$
рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдЙрджрд╛рд╣рд░рдг: 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 рдПрдХ рднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рд╣реИред
рдЕрдзрд┐рдХ рдХрд╛рд░реНрдп рдХрд┐рдП рдЧрдП рдЙрджрд╛рд╣рд░рдг: 36, 60 рдФрд░ 97
рд╣рд░ рдЙрджрд╛рд╣рд░рдг рдореЗрдВ рд╡рд╣реА рд╡рд┐рдзрд┐ рдкреНрд░рдпреБрдХреНрдд рд╣реЛрддреА рд╣реИ рдЬреЛ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдореЗрдВ рд╣реИ: рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рднрд╛рдЬрдХреЛрдВ \(d\) рдХреА рдЬрд╛рдБрдЪ \(\sqrt{N}\) рддрдХ рдХрд░реЗрдВ, рд╣рд░ рдПрдХ рдХреЛ \(N/d\) рдХреЗ рд╕рд╛рде рдЬреЛрдбрд╝реЗрдВ, рдлрд┐рд░ рдЕрднрд╛рдЬреНрдп рдШрд╛рддрд╛рдВрдХреЛрдВ рд╕реЗ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рдЧрд┐рдирддреА рдХрд░реЗрдВред
рдЙрджрд╛рд╣рд░рдг 1: N = 36 (рдПрдХ рдкреВрд░реНрдг рд╡рд░реНрдЧ)
- \(\sqrt{36} = 6\), рдЗрд╕рд▓рд┐рдП \(d = 1\) рд╕реЗ \(6\) рддрдХ рдЬрд╛рдБрдЪ рдХрд░реЗрдВред
- рд╡реЗ рднрд╛рдЬрдХ рдЬреЛ рдХрд╛рдо рдХрд░рддреЗ рд╣реИрдВ: 1, 2, 3, 4, 6ред (5 рдХрд╛рдо рдирд╣реАрдВ рдХрд░рддрд╛: \(36 \bmod 5 = 1\)ред)
- рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо: (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)ред рдпреБрдЧреНрдо (6, 6) рд╡рд╣реА рдЧреБрдгрдирдЦрдВрдб рджреЛрд╣рд░рд╛рддрд╛ рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ 36 рдПрдХ рдкреВрд░реНрдг рд╡рд░реНрдЧ рд╣реИред
- рд╕рднреА рдЧреБрдгрдирдЦрдВрдб: 1, 2, 3, 4, 6, 9, 12, 18, 36ред
- рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди: \(36 = 2^{2} \cdot 3^{2}\)ред
- рдЧрд┐рдирддреА: \((2+1)(2+1) = 9\) рдЧреБрдгрдирдЦрдВрдб, рдЬреЛ рд╕реВрдЪреА рд╕реЗ рдореЗрд▓ рдЦрд╛рддрд╛ рд╣реИред рдкреВрд░реНрдг рд╡рд░реНрдЧреЛрдВ рдХреЗ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рд╣рдореЗрд╢рд╛ рд╡рд┐рд╖рдо рд╣реЛрддреА рд╣реИ: 9ред
рдЙрджрд╛рд╣рд░рдг 2: N = 60
- \(\sqrt{60} \approx 7.75\), рдЗрд╕рд▓рд┐рдП \(d = 1\) рд╕реЗ \(7\) рддрдХ рдЬрд╛рдБрдЪ рдХрд░реЗрдВред
- рд╡реЗ рднрд╛рдЬрдХ рдЬреЛ рдХрд╛рдо рдХрд░рддреЗ рд╣реИрдВ: 1, 2, 3, 4, 5, 6ред (7 рдХрд╛рдо рдирд╣реАрдВ рдХрд░рддрд╛: \(60 = 8 \cdot 7 + 4\)ред)
- рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо: (1, 60), (2, 30), (3, 20), (4, 15), (5, 12), (6, 10)ред рдпрд╛рдиреА рдЫрд╣ рдпреБрдЧреНрдо рд╣реИрдВред
- рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди: \(60 = 2^{2} \cdot 3^{1} \cdot 5^{1}\)ред
- рдЧрд┐рдирддреА: \((2+1)(1+1)(1+1) = 3 \cdot 2 \cdot 2 = 12\) рдЧреБрдгрдирдЦрдВрдб, рдФрд░ рдЫрд╣ рдпреБрдЧреНрдо ├Ч 2 = 12ред
- рд╕рднреА рдЧреБрдгрдирдЦрдВрдб: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60ред
рдЙрджрд╛рд╣рд░рдг 3: N = 97 (рдПрдХ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛)
- \(\sqrt{97} \approx 9.85\), рдЗрд╕рд▓рд┐рдП рдХреЗрд╡рд▓ 9 рддрдХ рдХреЗ рднрд╛рдЬрдХреЛрдВ рдХреА рдЬрд╛рдБрдЪ рдХрд░рдиреА рд╣реИред рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ 2, 3, 5, 7 рдХреА рдЬрд╛рдБрдЪ рдкрд░реНрдпрд╛рдкреНрдд рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ 9 рддрдХ рдХрд╛ рдХреЛрдИ рдЕрдиреНрдп рднрд╛рдЬрдХ рдЗрдирдореЗрдВ рд╕реЗ рдХрд┐рд╕реА рдХрд╛ рдЧреБрдгрдЬ рд╣реИред
- \(97 = 48 \cdot 2 + 1\) (рд╢реЗрд╖рдлрд▓ 1), \(97 = 32 \cdot 3 + 1\) (рд╢реЗрд╖рдлрд▓ 1), \(97 = 19 \cdot 5 + 2\) (рд╢реЗрд╖рдлрд▓ 2), \(97 = 13 \cdot 7 + 6\) (рд╢реЗрд╖рдлрд▓ 6)ред
- 1 рдХреЗ рдЕрд▓рд╛рд╡рд╛ рдХреЛрдИ рднрд╛рдЬрдХ 97 рдХреЛ рд╡рд┐рднрд╛рдЬрд┐рдд рдирд╣реАрдВ рдХрд░рддрд╛, рдЗрд╕рд▓рд┐рдП рдЗрд╕рдХрд╛ рдПрдХрдорд╛рддреНрд░ рдЧреБрдгрдирдЦрдВрдб рдпреБрдЧреНрдо (1, 97) рд╣реИред
- рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди: \(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) рд╣реИ), рдЗрд╕рд▓рд┐рдП рд╡рд╣ рдЧреБрдгрдирдЦрдВрдб рджреЛ рдмрд╛рд░ рдирд╣реАрдВ рдмрд▓реНрдХрд┐ рдПрдХ рд╣реА рдмрд╛рд░ рдЧрд┐рдирд╛ рдЬрд╛рддрд╛ рд╣реИред