рдпреВрдХреНрд▓рд┐рдб рдПрд▓реНрдЧреЛрд░рд┐рджреНрдо рдХреНрдпрд╛ рд╣реИ?
рдорд╣рддреНрддрдо рд╕рдорд╛рдкрд╡рд░реНрддрдХ (GCF), рдЬрд┐рд╕реЗ рдорд╣рддреНрддрдо рд╕рдорд╛рдкрд╡рд░реНрддреНрдп (GCD) рдпрд╛ рднрд╛рд░рдд рдореЗрдВ рдЖрдорддреМрд░ рдкрд░ HCF рднреА рдХрд╣рд╛ рдЬрд╛рддрд╛ рд╣реИ, рд╡рд╣ рд╕рдмрд╕реЗ рдмрдбрд╝реА рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рд╣реЛрддреА рд╣реИ рдЬреЛ рджреЛ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рдкреВрд░реА рддрд░рд╣ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░ рджреЗрддреА рд╣реИред рдпреВрдХреНрд▓рд┐рдб рдПрд▓реНрдЧреЛрд░рд┐рджреНрдо рдЗрд╕реЗ рдирд┐рдХрд╛рд▓рдиреЗ рдХреА рдПрдХ рдкреНрд░рд╛рдЪреАрди рдФрд░ рдмреЗрд╣рдж рдХрд╛рд░рдЧрд░ рд╡рд┐рдзрд┐ рд╣реИ, рдЬрд┐рд╕рдореЗрдВ рдмрд╛рд░-рдмрд╛рд░ рд╢реЗрд╖рдлрд▓ рд╕рд╣рд┐рдд рднрд╛рдЧ рдХрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХрд┐рдиреНрд╣реАрдВ рднреА рджреЛ рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ GCF рджреЗрддрд╛ рд╣реИ рдФрд░ рд╣рд░ рднрд╛рдЧ рдХрд╛ рдЪрд░рдг рджрд┐рдЦрд╛рддрд╛ рд╣реИ, рддрд╛рдХрд┐ рдЖрдк рдкреВрд░реА рдЧрдгрдирд╛ рдЦреБрдж рд╕рдордЭ рд╕рдХреЗрдВред
рдЗрд╕рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ
рдорд╛рди 1 рдФрд░ рдорд╛рди 2 рдореЗрдВ рджреЛ рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛рдПрдБ рдбрд╛рд▓реЗрдВред рдЯреВрд▓ рдмрдбрд╝реА рд╕рдВрдЦреНрдпрд╛ рдХреЛ рднрд╛рдЬреНрдп (dividend) рдФрд░ рдЫреЛрдЯреА рд╕рдВрдЦреНрдпрд╛ рдХреЛ рднрд╛рдЬрдХ (divisor) рдорд╛рдирддрд╛ рд╣реИ, рдФрд░ рддрдм рддрдХ рдмрд╛рд░-рдмрд╛рд░ рднрд╛рдЧ рджреЗрддрд╛ рд╣реИ рдЬрдм рддрдХ рд╢реЗрд╖рдлрд▓ рд╢реВрдиреНрдп рди рд╣реЛ рдЬрд╛рдПред рдЖрдЦрд┐рд░реА рд╢реВрдиреНрдпреЗрддрд░ (рдиреЙрди-рдЬрд╝реАрд░реЛ) рднрд╛рдЬрдХ рд╣реА GCF рд╣реЛрддрд╛ рд╣реИред рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдХреНрд░рдо рдорд╛рдпрдиреЗ рдирд╣реАрдВ рд░рдЦрддрд╛ рдФрд░ рдЛрдгрд╛рддреНрдордХ рдЪрд┐рд╣реНрди рдХреЛ рдирдЬрд╝рд░рдЕрдВрджрд╛рдЬрд╝ рдХрд░ рджрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ GCF рдХреЗрд╡рд▓ рд╕рдВрдЦреНрдпрд╛ рдХреЗ рдорд╛рди рдкрд░ рдирд┐рд░реНрднрд░ рдХрд░рддрд╛ рд╣реИред
рд╕реВрддреНрд░ рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛
рд╣рд░ рдЪрд░рдг рдореЗрдВ рдЖрдк рдПрдХ рднрд╛рдЧрдлрд▓ рдФрд░ рдПрдХ рд╢реЗрд╖рдлрд▓ рдирд┐рдХрд╛рд▓рддреЗ рд╣реИрдВ: \(a = c \times b + R\), рдЬрд╣рд╛рдБ \(c = \lfloor a / b \rfloor\) рдФрд░ \(R = a \bmod b\)ред рдЗрд╕рдХреЗ рдмрд╛рдж \(a\) рдХреА рдЬрдЧрд╣ \(b\) рдФрд░ \(b\) рдХреА рдЬрдЧрд╣ \(R\) рд░рдЦ рджреЗрдВ, рдФрд░ рдпрд╣реА рдкреНрд░рдХреНрд░рд┐рдпрд╛ рджреЛрд╣рд░рд╛рдПрдБред рдЪреВрдБрдХрд┐ рд╣рд░ рд╢реЗрд╖рдлрд▓ рдкрд┐рдЫрд▓реЗ рднрд╛рдЬрдХ рд╕реЗ рд╣рдореЗрд╢рд╛ рдЫреЛрдЯрд╛ рд╣реЛрддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП рдпрд╣ рдкреНрд░рдХреНрд░рд┐рдпрд╛ рдЕрдВрддрддрдГ рд░реБрдХ рдЬрд╛рддреА рд╣реИред рдЬрдм \(R = 0\) рд╣реЛ рдЬрд╛рддрд╛ рд╣реИ, рддрдм рдореМрдЬреВрджрд╛ рднрд╛рдЬрдХ рд╣реА рдЙрддреНрддрд░ рд╣реЛрддрд╛ рд╣реИред рдкреБрдирд░рд╛рд╡рд░реНрддреА рд░реВрдк рдореЗрдВ:
$$\gcd(a, b) = \gcd(b,\ a \bmod b),\quad \gcd(a, 0) = a$$рд╣рд▓ рдХрд┐рдпрд╛ рд╣реБрдЖ рдЙрджрд╛рд╣рд░рдг
GCF(816, 2260) рдирд┐рдХрд╛рд▓реЗрдВред рдорд╛рди рд▓реЗрдВ \(a = 2260\), \(b = 816\)ред
$$2260 = 2 \times 816 + 628$$$$816 = 1 \times 628 + 188$$$$628 = 3 \times 188 + 64$$$$188 = 2 \times 64 + 60$$$$64 = 1 \times 60 + 4$$$$60 = 15 \times 4 + 0$$рд╢реЗрд╖рдлрд▓ рднрд╛рдЬрдХ 4 рдХреЗ рд╕рд╛рде рд╢реВрдиреНрдп рд╣реЛ рдЬрд╛рддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП GCF(816, 2260) = 4ред
рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓
рдХреНрдпрд╛ GCF рдФрд░ GCD рдПрдХ рд╣реА рдЪреАрдЬрд╝ рд╣реИрдВ? рд╣рд╛рдБред "рдорд╣рддреНрддрдо рд╕рдорд╛рдкрд╡рд░реНрддрдХ" (GCF) рдФрд░ "рдорд╣рддреНрддрдо рд╕рдорд╛рдкрд╡рд░реНрддреНрдп" (GCD) рдПрдХ-рджреВрд╕рд░реЗ рдХреЗ рдкрд░реНрдпрд╛рдпрд╡рд╛рдЪреА рд╣реИрдВ тАФ рднрд╛рд░рдд рдореЗрдВ рдЗрд╕реЗ рдЕрдХреНрд╕рд░ HCF рдХрд╣рддреЗ рд╣реИрдВред рдпрд╣ рдЯреВрд▓ рддреАрдиреЛрдВ рдХрд╛ рд╣реА рдЙрддреНрддрд░ рджреЗрддрд╛ рд╣реИред
рдЕрдЧрд░ рдХреЛрдИ рдПрдХ рдЗрдирдкреБрдЯ 0 рд╣реЛ рддреЛ? \(\gcd(a, 0) = a\), рдХреНрдпреЛрдВрдХрд┐ рд╣рд░ рд╕рдВрдЦреНрдпрд╛ 0 рдХреЛ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░ рджреЗрддреА рд╣реИред рдпрджрд┐ рджреЛрдиреЛрдВ рд╕рдВрдЦреНрдпрд╛рдПрдБ 0 рд╣реЛрдВ, рддреЛ GCF рдЕрдкрд░рд┐рднрд╛рд╖рд┐рдд (undefined) рд░рд╣рддрд╛ рд╣реИред
рдХреНрдпрд╛ рдореИрдВ рддреАрди рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ GCF рдирд┐рдХрд╛рд▓ рд╕рдХрддрд╛ рд╣реВрдБ? рдЯреВрд▓ рдХреЛ рдЬреЛрдбрд╝реА-рджрд░-рдЬреЛрдбрд╝реА рдЗрд╕реНрддреЗрдорд╛рд▓ рдХрд░реЗрдВ: \(\gcd(x, y, z) = \gcd(\gcd(x, y), z)\)ред