рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рд╕рд╛рдорд╛рдиреНрдп рдХрд╛рд░рдХ рдХреИрд▓рдХреБрд▓реЗрдЯрд░
рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рд╕рд╛рдорд╛рдиреНрдп рд╡рд┐рднрд╛рдЬрдХ (GCD) рдХреА рдЕрд╡рдзрд╛рд░рдгрд╛ рдХреА рдкрд░рд┐рднрд╛рд╖рд╛ рдкрд░ рдЖрдЧреЗ рдмрдврд╝рдиреЗ рд╕реЗ рдкрд╣рд▓реЗ, рдпрд╣ рд╕рдордЭрдирд╛ рдЖрд╡рд╢реНрдпрдХ рд╣реИ рдХрд┐ рдЖрдо рднрд╛рдЬрдХ рд╕рд╛рдорд╛рдиреНрдп рд░реВрдк рд╕реЗ рдХреНрдпрд╛ рд╣реЛрддрд╛ рд╣реИред
рдпрд╣ рдЬреНрдЮрд╛рдд рд╣реИ рдХрд┐ рдПрдХ рдкреВрд░реНрдгрд╛рдВрдХ рдореЗрдВ рдХрдИ рд╡рд┐рднрд╛рдЬрдХ рд╣реЛ рд╕рдХрддреЗ рд╣реИрдВред рд╣рдо рдХрдИ рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рджреНрд╡рд╛рд░рд╛ рдПрдХ рд╕рд╛рде рдЙрди рддрдХ рдкрд╣реБрдБрдЪрдиреЗ рдореЗрдВ рд░реБрдЪрд┐ рд░рдЦрддреЗ рд╣реИрдВред рд╣рдо рдХрдИ рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рдХреЗ рд╕рд╛рдорд╛рдиреНрдп рд╡рд┐рднрд╛рдЬрдХ рдХреЛ рд╡рд╣ рд╕рдВрдЦреНрдпрд╛ рдорд╛рдирддреЗ рд╣реИрдВ рдЬреЛ рдирд┐рд░реНрджрд┐рд╖реНрдЯ рд╢реНрд░реГрдВрдЦрд▓рд╛ рд╕реЗ рдкреНрд░рддреНрдпреЗрдХ рд╕рдВрдЦреНрдпрд╛ рдХреЗ рд▓рд┐рдП рднрд╛рдЬрдХ рдХреЗ рд░реВрдк рдореЗрдВ рдХрд╛рд░реНрдп рдХрд░ рд╕рдХрддреА рд╣реИред
рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, рд╕рдВрдЦреНрдпрд╛ 8 рдФрд░ 12 рдореЗрдВ рдирд┐рдореНрдирд▓рд┐рдЦрд┐рдд рд╕рд╛рдорд╛рдиреНрдп рд╡рд┐рднрд╛рдЬрдХ рд╣реИрдВ: 1 рдФрд░ 4ред рдЗрд╕реЗ рдЧрдгрд┐рддреАрдп рдЕрднрд┐рд╡реНрдпрдХреНрддрд┐ рд▓рд┐рдЦрдХрд░ рдЖрд╕рд╛рдиреА рд╕реЗ рд╕рддреНрдпрд╛рдкрд┐рдд рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИ: 8 = 4 ⋅ 2; 12 = 3 ⋅ 4.
рдпрд╣ рдзреНрдпрд╛рди рджрд┐рдпрд╛ рдЬрд╛рдирд╛ рдЪрд╛рд╣рд┐рдП рдХрд┐ рдкреНрд░рддреНрдпреЗрдХ рд╕рдВрдЦреНрдпрд╛ рдореЗрдВ рд╢реБрд░реВ рдореЗрдВ рдХрдо рд╕реЗ рдХрдо рджреЛ рд╕рд╛рдорд╛рдиреНрдп рд╡рд┐рднрд╛рдЬрдХ рд╣реЛрддреЗ рд╣реИрдВ: рдХреЛрдИ рднреА рд╕рдВрдЦреНрдпрд╛ рд╢реЗрд╖ рдХреЗ рдмрд┐рдирд╛ рд╕реНрд╡рдпрдВ рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реЛрддреА рд╣реИ, рдФрд░ 1 рд╕реЗ рднреА рд╡рд┐рднрд╛рдЬреНрдп рд╣реЛрддреА рд╣реИред
рдорд╣рд╛рдирддрдо рд╕рдорд╛рдкрд╡рд░реНрддрдХ рдХрд╛ рдирд┐рд░реНрдзрд╛рд░рдг
рджреЛ рдкреНрд░рд╛рдХреГрддрд┐рдХ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рд╕рд╛рдорд╛рдиреНрдп рднрд╛рдЬрдХ (GCD) рдЙрди рдкреНрд░рд╛рдХреГрддрд┐рдХ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдореЗрдВ рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рд╣реИ рдЬрд┐рд╕рд╕реЗ рд╣рдо рдЕрдкрдиреА рджреЛ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░ рд╕рдХрддреЗ рд╣реИрдВред рдпрджрд┐ рджреЛ рдкреНрд░рд╛рдХреГрддрд┐рдХ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рд╕рдмрд╕реЗ рдмрдбрд╝реЗ рд╕рд╛рдорд╛рдиреНрдп рднрд╛рдЬрдХ рдХрд╛ рдорд╛рди 1 рд╣реИ, рддреЛ рд╣рдо рдЗрди рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рдХреЛрдкреНрд░рд╛рдЗрдо рдХрд╣рддреЗ рд╣реИрдВред
рджреЛ рд╕рдВрдЦреНрдпрд╛рдУрдВ a рдФрд░ b рдХреЗ рд▓рд┐рдП, рдорд╣рддреНрддрдо рд╕рдорд╛рдкрд╡рд░реНрддрдХ рд╡рд╣ рд╕рдВрдЦреНрдпрд╛ рд╣реИ рдЬрд┐рд╕рд╕реЗ a рдФрд░ b рдХреЛ рдмрд┐рдирд╛ рд╢реЗрд╖рдлрд▓ рдХреЗ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред рдпрд╣ рдЕрднрд┐рд╡реНрдпрдХреНрддрд┐ рдирд┐рдореНрдирд╛рдиреБрд╕рд╛рд░ рд▓рд┐рдЦреА рдЧрдИ рд╣реИ: рдЬреАрд╕реАрдбреА (рдП, рдмреА) = рд╕реАред
рдЬреАрд╕реАрдбреА рд▓рд┐рдЦрдиреЗ рдХрд╛ рджреВрд╕рд░рд╛ рддрд░реАрдХрд╛: (рдП, рдмреА) = рд╕реАред рд╣рд╛рд▓рд╛рдВрдХрд┐, рдЬреНрдпрд╛рджрд╛рддрд░ рдорд╛рдорд▓реЛрдВ рдореЗрдВ, рдкрд╣рд▓рд╛ рд╡рд┐рдХрд▓реНрдк рдЗрд╕реНрддреЗрдорд╛рд▓ рдХрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред
рдЗрд╕рд▓рд┐рдП, рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, рд╕рдВрдЦреНрдпрд╛ 4 рдФрд░ 16 рдореЗрдВ 4 рдХреЗ рдмрд░рд╛рдмрд░ рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рд╕рд╛рдорд╛рдиреНрдп рднрд╛рдЬрдХ рд╣реИред рдЖрдЗрдП рд▓рд┐рдЦрддреЗ рд╣реИрдВ: gcd (4, 16) = 4ред
рдЖрдЗрдП рдмрддрд╛рддреЗ рд╣реИрдВ рдХрд┐ рд╣рдо рдЗрд╕ рдирддреАрдЬреЗ рдкрд░ рдХреИрд╕реЗ рдкрд╣реБрдВрдЪреЗ:
- рд╣рдордиреЗ рд╕рдВрдЦреНрдпрд╛ 4 рдХреЗ рд╕рднреА рд╡рд┐рднрд╛рдЬрдХреЛрдВ рдХреЛ рд▓рд┐рдЦ рджрд┐рдпрд╛ред рд╣рдореЗрдВ рдорд┐рд▓рд╛: 4, 2, 1ред
- рдЖрдЧреЗ, рд╣рдордиреЗ 16 рдХреЗ рд╕рднреА рднрд╛рдЬрдХреЛрдВ рдХреЛ рдкреЗрдВрдЯ рдХрд┐рдпрд╛ред рд╣рдореЗрдВ рдорд┐рд▓рд╛: 16, 8, 4, 2, 1ред
- рд╣рдордиреЗ рдРрд╕реЗ рднрд╛рдЬрдХ рдЪреБрдиреЗ рдЬреЛ 4 рдФрд░ 16 рджреЛрдиреЛрдВ рдХреЗ рд▓рд┐рдП рдЙрднрдпрдирд┐рд╖реНрда рд╣реИрдВред рд╣рдореЗрдВ рдорд┐рд▓рд╛: 4, 2, 1ред
- рдкрд░рд┐рдгрд╛рдореА рд╕рд╛рдорд╛рдиреНрдп рднрд╛рдЬрдХ рд╕реЗ, рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рдЪреБрдирд╛ рдЧрдпрд╛ рдерд╛ред рдпрд╣ 4 рд╣реИред
- рд╣рдореЗрдВ рдЙрддреНрддрд░ рдорд┐рд▓рддрд╛ рд╣реИ: рд╕рдВрдЦреНрдпрд╛ 4 рдФрд░ 16 рдХреЗ рд▓рд┐рдП рдЬреАрд╕реАрдбреА 4 рд╣реИред
рдЗрд╕реА рддрд░рд╣, рдЖрдк рддреАрди рдпрд╛ рдЕрдзрд┐рдХ рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рдХреЗ рд▓рд┐рдП рдЬреАрд╕реАрдбреА рдкрд╛ рд╕рдХрддреЗ рд╣реИрдВред рдЗрд╕ рдорд╛рдорд▓реЗ рдореЗрдВ, рдпрд╣ рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рдкреВрд░реНрдгрд╛рдВрдХ рд╣реЛрдЧрд╛ рдЬрд┐рд╕рд╕реЗ рдЖрдк рдкреНрд░рд╕реНрддрд╛рд╡рд┐рдд рд╢реНрд░реГрдВрдЦрд▓рд╛ рд╕реЗ рд╕рднреА рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░ рд╕рдХрддреЗ рд╣реИрдВред
рдЗрд╕рд▓рд┐рдП, рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, рдкреВрд░реНрдгрд╛рдВрдХ 6, 12, 18, 42 рдХреЗ рд▓рд┐рдП рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рднрд╛рдЬрдХ рд╕рдВрдЦреНрдпрд╛ 6 рд╣реЛрдЧреА, рдЕрд░реНрдерд╛рдд, gcd (6, 12, 18, 42) = 6ред рдЙрддреНрддрд░ рдПрдХ рдПрд▓реНрдЧреЛрд░рд┐рдереНрдо рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рдХреЗ рдкреНрд░рд╛рдкреНрдд рдХрд┐рдпрд╛ рдЧрдпрд╛ рдерд╛ред рдКрдкрд░ рд╡рд░реНрдгрд┐рдд рдХреЗ рд╕рдорд╛рди - рдПрдХ рд╢реНрд░реГрдВрдЦрд▓рд╛ рд╕реЗ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рд▓рд┐рдП, рд╕рднреА рд╡рд┐рднрд╛рдЬрдХ рдХреНрд░рдорд┐рдХ рд░реВрдк рд╕реЗ рд▓рд┐рдЦреЗ рдЧрдП рдереЗ, рдЬрд┐рд╕рдХреЗ рдмрд╛рдж рдЙрдирдореЗрдВ рд╕реЗ рд╕рдмрд╕реЗ рдмрдбрд╝реЗ рдХрд╛ рдЪрдпрди рдХрд┐рдпрд╛ рдЧрдпрд╛ рдерд╛ред
рдЬреАрд╕реАрдбреА рдЧреБрдг
рд╕рдмрд╕реЗ рдмрдбрд╝реЗ рд╕рд╛рдорд╛рдиреНрдп рд╡рд┐рднрд╛рдЬрдХ рдореЗрдВ рдХрдИ рдЧреБрдг рд╣реЛрддреЗ рд╣реИрдВ рдЬреЛ рд╢реВрдиреНрдп рд╕реЗ рдЕрдзрд┐рдХ рд╡рд┐рднрд╛рдЬрдХ рд╡рд╛рд▓реЗ рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рдХреЗ GCD рдХреЗ рд▓рд┐рдП рдкреНрд░рд╛рд╕рдВрдЧрд┐рдХ рд╣реЛрдВрдЧреЗред
рдкреНрд░реЙрдкрд░реНрдЯреА 1
рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рд╕реНрдерд╛рди рдмрджрд▓рдиреЗ рд╕реЗ, GCD рдХрд╛ рдЕрдВрддрд┐рдо рдорд╛рди рдирд╣реАрдВ рдмрджрд▓реЗрдЧрд╛ред рдЖрдк рдЗрд╕ рдХрдерди рдХреЛ рдЗрд╕ рдкреНрд░рдХрд╛рд░ рд▓рд┐рдЦ рд╕рдХрддреЗ рд╣реИрдВ:
- gcd(a, b) = gcd(b, a).
рд╕рдВрдкрддреНрддрд┐ 2
рдпрджрд┐ a, b рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИ, рддреЛ a рдФрд░ b рдХреЗ рдЙрднрдпрдирд┐рд╖реНрда рднрд╛рдЬрдХ рдХрд╛ рд╕рдореБрдЪреНрдЪрдп b рдХреЗ рд╡рд┐рднрд╛рдЬрдХ рдХреЗ рд╕рдореБрдЪреНрдЪрдп рдХреЗ рд╕рдорд╛рди рд╣реИред рдЗрд╕ рддрд░рд╣ рд▓рд┐рдЦрд╛:
- рдЬреАрд╕реАрдбреА (рдП, рдмреА) = рдмреАред
рдкреНрд░реВрд╡реНрдб рдЧреНрд░реЗрдЯреЗрд╕реНрдЯ рдбрд┐рд╡рд╛рдЗрдбрд░ рдкреНрд░реЙрдкрд░реНрдЯреА рдХрд╛ рдЗрд╕реНрддреЗрдорд╛рд▓ рджреЛ рдирдВрдмрд░реЛрдВ рдХрд╛ рдЬреАрд╕реАрдбреА рдЦреЛрдЬрдиреЗ рдХреЗ рд▓рд┐рдП рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИ, рдЬрдм рдЙрдирдореЗрдВ рд╕реЗ рдПрдХ рджреВрд╕рд░реЗ рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реЛред рдЗрд╕ рдорд╛рдорд▓реЗ рдореЗрдВ, GCD рдЗрдирдореЗрдВ рд╕реЗ рдПрдХ рд╕рдВрдЦреНрдпрд╛ рдХреЗ рдмрд░рд╛рдмрд░ рд╣реИ, рдЬрд┐рд╕рд╕реЗ рджреВрд╕рд░реА рд╕рдВрдЦреНрдпрд╛ рд╡рд┐рднрд╛рдЬреНрдп рд╣реИред
рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП:
- gcd(12, 4) = 4.
рд╕рдорд╛рди:
- gcd(10, 1) = 1.
рд╕рдВрдкрддреНрддрд┐ 3
рдЕрдЧрд░ a = bq + c, рдЬрд╣рд╛рдВ a, b, c рдФрд░ q рдкреВрд░реНрдгрд╛рдВрдХ рд╣реИрдВ, рддреЛ a рдФрд░ b рдХреЗ рдЙрднрдпрдирд┐рд╖реНрда рднрд╛рдЬрдХ рдХрд╛ рд╕рдореБрдЪреНрдЪрдп b рдФрд░ c рдХреЗ рдЙрднрдпрдирд┐рд╖реНрда рднрд╛рдЬрдХ рдХреЗ рд╕рдореБрдЪреНрдЪрдп рдХреЗ рд╕рдорд╛рди рд╣реИред
рд╕рдорд╛рдирддрд╛ gcd (a, b) = gcd (b, c) рдорд╛рдиреНрдп рд╣реЛ рдЬрд╛рддреА рд╣реИред
рд╕рдВрдкрддреНрддрд┐ 4
рдЕрднрд┐рд╡реНрдпрдХреНрддрд┐ gcd(ma, mb) = m ⋅ gcd(a, b) рд╕рддреНрдп рд╣реИ, рдмрд╢рд░реНрддреЗ рдХрд┐ m рдХреЛрдИ рдкреНрд░рд╛рдХреГрдд рд╕рдВрдЦреНрдпрд╛ рд╣реЛред
рд╕рдВрдкрддреНрддрд┐ 5
рдорд╛рди рд▓реЗрдВ рдХрд┐ p, a рдФрд░ b рдХрд╛ рдХреЛрдИ рдЙрднрдпрдирд┐рд╖реНрда рднрд╛рдЬрдХ рд╣реИред
рдлрд┐рд░:
- gcd(a / p, b / p) = gcd(a, b) / p.
рдЕрдЧрд░ p = gcd(a, b), рддреЛ рд╣рдореЗрдВ рдорд┐рд▓рддрд╛ рд╣реИ:
- рдЬреАрд╕реАрдбреА (рдП / рдЬреАрд╕реАрдбреА (рдП, рдмреА), рдмреА / рдЬреАрд╕реАрдбреА (рдП, рдмреА)) = 1,
рдЗрд╕ рдкреНрд░рдХрд╛рд░, рд╕рдВрдЦреНрдпрд╛рдПрдБ a / gcd (a, b) рдФрд░ b / gcd (a, b) рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВред
рд╕рдВрдкрддреНрддрд┐ 6
рдХрд┐рд╕реА рднреА рджреЛ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдХрдо рд╕реЗ рдХрдо рдПрдХ рдЙрднрдпрдирд┐рд╖реНрда рднрд╛рдЬрдХ рд╣реЛрддрд╛ рд╣реИ - рдпрд╣ рд╕рдВрдЦреНрдпрд╛ 1 рд╣реИред
рд╕рд╛рдорд╛рдиреНрдп рдЕрдВрд╢реЛрдВ рдХреЗ рд╕рд╛рде рдХрд╛рдо рдХрд░рдиреЗ рдХреЗ рд▓рд┐рдП GCD рдЕрд╡рдзрд╛рд░рдгрд╛ рдХреЗ рд╕реИрджреНрдзрд╛рдВрддрд┐рдХ рдЖрдзрд╛рд░реЛрдВ рдХреЗ рд╕рд╛рде-рд╕рд╛рде рдЗрд╕рдХреА рдкрд░рд┐рднрд╛рд╖рд╛ рдореЗрдВ рд╡реНрдпрд╛рд╡рд╣рд╛рд░рд┐рдХ рдХреМрд╢рд▓ рдХрд╛ рдЬреНрдЮрд╛рди рдЖрд╡рд╢реНрдпрдХ рд╣реИред рдЗрд╕рдХреЗ рдЕрд▓рд╛рд╡рд╛, GCD рдПрдХ рдЕрдиреНрдп рдЧрдгрд┐рддреАрдп рдЗрдХрд╛рдИ рд╕реЗ рдирд┐рдХрдЯрддрд╛ рд╕реЗ рд╕рдВрдмрдВрдзрд┐рдд рд╣реИ - рд╕рдмрд╕реЗ рдХрдо рд╕рд╛рдорд╛рдиреНрдп рд╡рд┐рднрд╛рдЬрдХред рджреЛрдиреЛрдВ рдкрд░рд┐рднрд╛рд╖рд╛рдУрдВ рдХрд╛ рдЖрдорддреМрд░ рдкрд░ рдПрдХ рдорд╛рдирдХ рд╕реНрдХреВрд▓ рдкрд╛рдареНрдпрдХреНрд░рдо рдХреЗ рднрд╛рдЧ рдХреЗ рд░реВрдк рдореЗрдВ рдЕрдзреНрдпрдпрди рдХрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред