MCP рдХреЗ рдорд╛рдзреНрдпрдо рд╕реЗ рдХрдиреЗрдХреНрдЯ рдХрд░реЗрдВ тЖТ

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

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

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

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

Prime Factorization of 360
2^3 ├Ч 3^2 ├Ч 5
рдШрд╛рддрд╛рдВрдХ рд░реВрдк рдореЗрдВ
рд╕рдВрдЦреНрдпрд╛ 360
рд╡рд┐рд╕реНрддреГрдд рд░реВрдк 2 ├Ч 2 ├Ч 2 ├Ч 3 ├Ч 3 ├Ч 5
рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб 3
рдХреБрд▓ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб (рдмрд╣реБрд▓рддрд╛ рд╕рд╣рд┐рдд) 6
рдХреНрдпрд╛ рдпрд╣ рдЕрднрд╛рдЬреНрдп рд╣реИ? No

рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рдХреНрдпрд╛ рд╣реИ?

рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рд╡рд╣ рдкреНрд░рдХреНрд░рд┐рдпрд╛ рд╣реИ рдЬрд┐рд╕рдореЗрдВ рдХрд┐рд╕реА рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рдХреЛ рдЙрди рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рд╕рдореВрд╣ рдореЗрдВ рддреЛрдбрд╝рд╛ рдЬрд╛рддрд╛ рд╣реИ, рдЬрд┐рдиреНрд╣реЗрдВ рдЖрдкрд╕ рдореЗрдВ рдЧреБрдгрд╛ рдХрд░рдиреЗ рдкрд░ рд╡рд╣реА рд╕рдВрдЦреНрдпрд╛ рдмрдирддреА рд╣реИред рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ 1 рд╕реЗ рдмрдбрд╝реА рд╡рд╣ рд╕рдВрдЦреНрдпрд╛ рд╣реЛрддреА рд╣реИ рдЬрд┐рд╕рдХреЗ рднрд╛рдЬрдХ рдХреЗрд╡рд▓ 1 рдФрд░ рд╡рд╣ рдЦреБрдж рд╣реА рд╣реЛрддреЗ рд╣реИрдВ (2, 3, 5, 7, 11, тАж)ред рдЕрдВрдХрдЧрдгрд┐рдд рдХрд╛ рдореВрд▓рднреВрдд рдкреНрд░рдореЗрдп (Fundamental Theorem of Arithmetic) рдпрд╣ рд╕реБрдирд┐рд╢реНрдЪрд┐рдд рдХрд░рддрд╛ рд╣реИ рдХрд┐ 1 рд╕реЗ рдмрдбрд╝реА рд╣рд░ рдкреВрд░реНрдгрд╛рдВрдХ рд╕рдВрдЦреНрдпрд╛ рдХрд╛ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреЗ рдХреНрд░рдо рдХреЛ рдЫреЛрдбрд╝рдХрд░ рдареАрдХ рдПрдХ рд╣реА рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рд╣реЛрддрд╛ рд╣реИред

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

рдЗрд╕ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ

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

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

рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдЯреНрд░рд╛рдпрд▓ рдбрд┐рд╡реАрдЬрд╝рди (рдкрд░реАрдХреНрд╖рдг рднрд╛рдЧ) рд╡рд┐рдзрд┐ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рддрд╛ рд╣реИред рд╕рдмрд╕реЗ рдЫреЛрдЯреА рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ 2 рд╕реЗ рд╢реБрд░реВ рдХрд░рдХреЗ, рдпрд╣ рд╕рдВрдЦреНрдпрд╛ рдХреЛ рд╣рд░ рд╕рдВрднрд╛рд╡рд┐рдд рднрд╛рдЬрдХ \(d\) рд╕реЗ рдмрд╛рд░-рдмрд╛рд░ рддрдм рддрдХ рднрд╛рдЧ рджреЗрддрд╛ рд╣реИ рдЬрдм рддрдХ рднрд╛рдЧ рдкреВрд░рд╛ (рд╢реЗрд╖рдлрд▓ рд╢реВрдиреНрдп) рд░рд╣рддрд╛ рд╣реИ, рдФрд░ рдЧрд┐рдирддрд╛ рд╣реИ рдХрд┐ рд╣рд░ рднрд╛рдЬрдХ рдХрд┐рддрдиреА рдмрд╛рд░ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░рддрд╛ рд╣реИред рдЗрд╕реЗ рдХреЗрд╡рд▓ \(\sqrt{n}\) рддрдХ рдХреЗ рднрд╛рдЬрдХ рдЬрд╛рдВрдЪрдиреЗ рдХреА рдЬрд╝рд░реВрд░рдд рд╣реЛрддреА рд╣реИ (\(d \le \sqrt{n}\)), рдХреНрдпреЛрдВрдХрд┐ рдпрджрд┐ рд╡рд░реНрдЧрдореВрд▓ рд╕реЗ рдиреАрдЪреЗ рдХреЛрдИ рдЧреБрдгрдирдЦрдВрдб рдирд╣реАрдВ рдорд┐рд▓рддрд╛, рддреЛ рдЬреЛ рд╢реЗрд╖ рдмрдЪрддрд╛ рд╣реИ рд╡рд╣ рд╕реНрд╡рдпрдВ рдЕрднрд╛рдЬреНрдп рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдПред рдкрд░рд┐рдгрд╛рдо рдЗрд╕ рд░реВрдк рдореЗрдВ рджрд░реНрд╢рд╛рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ:

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

рд╕рдВрдЦреНрдпрд╛ рдШрд╛рддрд╛рдВрдХ рд╕рд╣рд┐рдд рдЕрднрд╛рдЬреНрдп рдШрд╛рддреЛрдВ рдХреЗ рдЧреБрдгрдирдлрд▓ рдХреЗ рд░реВрдк рдореЗрдВ рд╡реНрдпрдХреНрдд
рдШрд╛рддрд╛рдВрдХ рд░реВрдк рджреЛрд╣рд░рд╛рдП рдЧрдП рдЕрднрд╛рдЬреНрдпреЛрдВ рдХреЛ рдЕрднрд╛рдЬреНрдп рдШрд╛рддреЛрдВ рдореЗрдВ рд╕рдореВрд╣рд┐рдд рдХрд░рддрд╛ рд╣реИред

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

рдорд╛рди рд▓реАрдЬрд┐рдП \(n = 360\)ред рдЗрд╕реЗ 2 рд╕реЗ рддреАрди рдмрд╛рд░ рднрд╛рдЧ рджреЗрдВ: \(360 \to 180 \to 90 \to 45\) (\(2^3\))ред рдлрд┐рд░ 3 рд╕реЗ рджреЛ рдмрд╛рд░: \(45 \to 15 \to 5\) (\(3^2\))ред рдлрд┐рд░ 5 рд╕реЗ рдПрдХ рдмрд╛рд░: \(5 \to 1\) (\(5^1\))ред рддреЛ

$$360 = 2^3 \times 3^2 \times 5$$

рд╡рд┐рд╕реНрддреГрдд рд░реВрдк рдореЗрдВ рдпрд╣ \(2 \times 2 \times 2 \times 3 \times 3 \times 5\) рд╣реИ: рддреАрди рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдПрдВ рдФрд░ рдХреБрд▓ рдЫрд╣ рдЧреБрдгрдирдЦрдВрдбред

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

рд╕рдВрдЦреНрдпрд╛ рдХрдо рд╕реЗ рдХрдо 2 рдХреНрдпреЛрдВ рд╣реЛрдиреА рдЪрд╛рд╣рд┐рдП? рд╕рдВрдЦреНрдпрд╛ 0 рдФрд░ 1 рдХрд╛ рдХреЛрдИ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рдирд╣реАрдВ рд╣реЛрддрд╛ тАФ 1 рди рддреЛ рдЕрднрд╛рдЬреНрдп рд╣реИ рдФрд░ рди рд╣реА рднрд╛рдЬреНрдп (composite)ред

"рдмрд╣реБрд▓рддрд╛ рд╕рд╣рд┐рдд" рдХрд╛ рдХреНрдпрд╛ рдЕрд░реНрде рд╣реИ? рдЗрд╕рдХрд╛ рдорддрд▓рдм рд╣реИ рдХрд┐ рд╣рд░ рдЕрднрд╛рдЬреНрдп рдХреЛ рдЙрддрдиреА рд╣реА рдмрд╛рд░ рдЧрд┐рдирд╛ рдЬрд╛рддрд╛ рд╣реИ рдЬрд┐рддрдиреА рдмрд╛рд░ рд╡рд╣ рдЖрддрд╛ рд╣реИред 360 рдХреЗ рд▓рд┐рдП рдХреБрд▓ 6 рд╣реИрдВ (рддреАрди рдмрд╛рд░ 2, рджреЛ рдмрд╛рд░ 3, рдПрдХ рдмрд╛рд░ 5)ред

рдХреНрдпрд╛ 1 рдЕрднрд╛рдЬреНрдп рд╣реИ? рдирд╣реАрдВред рдкрд░рд┐рднрд╛рд╖рд╛ рдХреЗ рдЕрдиреБрд╕рд╛рд░ рдХрд┐рд╕реА рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдХреЗ рдареАрдХ рджреЛ рднрд┐рдиреНрди рдзрдирд╛рддреНрдордХ рднрд╛рдЬрдХ рд╣реЛрдиреЗ рдЪрд╛рд╣рд┐рдП, рдЬрдмрдХрд┐ 1 рдХрд╛ рдХреЗрд╡рд▓ рдПрдХ рд╣реА рднрд╛рдЬрдХ рд╣реИред

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