рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдХреИрд▓рдХреБрд▓реЗрдЯрд░

рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдХреИрд▓рдХреБрд▓реЗрдЯрд░

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

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

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

рд╕рд╣рдЕрднрд╛рдЬреНрдптЗФgcdтБб(a,b)=1\text{рд╕рд╣рдЕрднрд╛рдЬреНрдп} \iff \gcd\left(\text{a},\ \text{b}\right) = 1

рдЙрджрд╛рд╣рд░рдг

рд╕рд╣рдЕрднрд╛рдЬреНрдптЗФgcdтБб(1071,1024)=1=1\text{рд╕рд╣рдЕрднрд╛рдЬреНрдп} \iff \gcd\left(1071,\ 1024\right) = 1 = 1
рдЙрдкрдпреЛрдЧ рдЖрдБрдХрдбрд╝реЗ

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

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

рдХреНрдпрд╛ 1,071 рдФрд░ 1,024 рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВ?
рд╣рд╛рдБ
gcd(1071, 1024) = 1
рдорд╣рддреНрддрдо рд╕рдорд╛рдкрд╡рд░реНрддрдХ (gcd) 1
рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣рд╛рдБ (gcd = 1)

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

рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХреНрдпрд╛ рд╣реИ?

рджреЛ рдкреВрд░реНрдгрд╛рдВрдХ рддрдм рд╕рд╣рдЕрднрд╛рдЬреНрдп (рдЕрдВрдЧреНрд░реЗрдЬрд╝реА рдореЗрдВ coprime рдпрд╛ relatively prime) рдХрд╣рд▓рд╛рддреЗ рд╣реИрдВ, рдЬрдм рдЙрди рджреЛрдиреЛрдВ рдХреЛ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░рдиреЗ рд╡рд╛рд▓реА рдПрдХрдорд╛рддреНрд░ рдзрдирд╛рддреНрдордХ рд╕рдВрдЦреНрдпрд╛ 1 рд╣реЛред рджреВрд╕рд░реЗ рд╢рдмреНрджреЛрдВ рдореЗрдВ, рдЙрдирдХрд╛ рдорд╣рддреНрддрдо рд╕рдорд╛рдкрд╡рд░реНрддрдХ (gcd) рдареАрдХ 1 рд╣реЛрддрд╛ рд╣реИред рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдЖрдкрдХреА рджреА рд╣реБрдИ рджреЛ рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛рдПрдБ рд▓реЗрддрд╛ рд╣реИ рдФрд░ рддреБрд░рдВрдд рдмрддрд╛ рджреЗрддрд╛ рд╣реИ рдХрд┐ рд╡реЗ рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВ рдпрд╛ рдирд╣реАрдВ, рд╕рд╛рде рд╣реА рдЙрдирдХрд╛ gcd рднреА рджрд┐рдЦрд╛рддрд╛ рд╣реИред

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

a рдФрд░ b рд╡рд╛рд▓реЗ рдЦрд╛рдиреЛрдВ рдореЗрдВ рдЕрдкрдиреА рджреЛрдиреЛрдВ рдкреВрд░реНрдгрд╛рдВрдХ рд╕рдВрдЦреНрдпрд╛рдПрдБ рднрд░реЗрдВ рдФрд░ рд╕рдмрдорд┐рдЯ рдХрд░реЗрдВред рдпрд╣ рдЯреВрд▓ рдпреВрдХреНрд▓рд┐рдбрд┐рдпрди рдПрд▓реНрдЧреЛрд░рд┐рдереНрдо рдХреА рдорджрдж рд╕реЗ \(\gcd(a,\ b)\) рдирд┐рдХрд╛рд▓рддрд╛ рд╣реИред рдЕрдЧрд░ gcd 1 рд╣реИ, рддреЛ рд╕рдВрдЦреНрдпрд╛рдПрдБ рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВ; рдирд╣реАрдВ рддреЛ рдЙрдирдореЗрдВ рдХреЛрдИ рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдб рд╣реИ рдФрд░ рд╡реЗ рд╕рд╣рдЕрднрд╛рдЬреНрдп рдирд╣реАрдВ рд╣реИрдВред рдЛрдгрд╛рддреНрдордХ рдЪрд┐рд╣реНрдиреЛрдВ рдХреЛ рдЕрдирджреЗрдЦрд╛ рдХрд░ рджрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ рд╕рд╣рдЕрднрд╛рдЬреНрдпрддрд╛ рдХреЗрд╡рд▓ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рдирд┐рд░рдкреЗрдХреНрд╖ рдорд╛рди (absolute value) рдкрд░ рдирд┐рд░реНрднрд░ рдХрд░рддреА рд╣реИред

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

рдпреВрдХреНрд▓рд┐рдбрд┐рдпрди рдПрд▓реНрдЧреЛрд░рд┐рдереНрдо рдмрд╛рд░-рдмрд╛рд░ рдЬреЛрдбрд╝реА (a, b) рдХреЛ (b, a mod b) рд╕реЗ рдмрджрд▓рддрд╛ рд░рд╣рддрд╛ рд╣реИ, рдЬрдм рддрдХ рджреВрд╕рд░рд╛ рдорд╛рди 0 рди рд╣реЛ рдЬрд╛рдПред рдЖрдЦрд╝рд┐рд░реА рд╢реВрдиреНрдпреЗрддрд░ (non-zero) рдорд╛рди рд╣реА gcd рд╣реЛрддрд╛ рд╣реИред рд╕рдВрдЦреНрдпрд╛рдПрдБ рдареАрдХ рддрднреА рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реЛрддреА рд╣реИрдВ рдЬрдм рдпрд╣ gcd 1 рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛ:

$$\text{Coprime} \iff \gcd\left(\text{a},\ \text{b}\right) = 1$$

рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, 8 рдФрд░ 15 рдореЗрдВ рдХреЛрдИ рдЙрднрдпрдирд┐рд╖реНрда рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб рдирд╣реАрдВ рд╣реИ, рдЗрд╕рд▓рд┐рдП \(\gcd = 1\) рдФрд░ рдпреЗ рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВ тАФ рднрд▓реЗ рд╣реА рджреЛрдиреЛрдВ рдореЗрдВ рд╕реЗ рдХреЛрдИ рднреА рд╕рдВрдЦреНрдпрд╛ рд╕реНрд╡рдпрдВ рдЕрднрд╛рдЬреНрдп рди рд╣реЛред

рд╡рд┐рдЬреНрдЮрд╛рдкрди
рджреЛ рд╕рдВрдЦреНрдпрд╛рдПрдБ рдЬрд┐рдирдХрд╛ рд╕рд╛рдЭрд╛ рдЧреБрдгрдирдЦрдВрдб рдХреЗрд╡рд▓ 1 рд╣реИ, рдЕрддрд┐рд╡реНрдпрд╛рдкреА рдЧреБрдгрдирдЦрдВрдб рд╕рдореБрдЪреНрдЪрдпреЛрдВ рдХреЗ рд░реВрдк рдореЗрдВ рджрд┐рдЦрд╛рдпрд╛ рдЧрдпрд╛
рджреЛ рд╕рдВрдЦреНрдпрд╛рдПрдБ рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реЛрддреА рд╣реИрдВ рдЬрдм рдЙрдирдХрд╛ рдПрдХрдорд╛рддреНрд░ рд╕рд╛рдЭрд╛ рдЧреБрдгрдирдЦрдВрдб 1 рд╣реЛ, рдЗрд╕рд▓рд┐рдП \(\gcd(a,\ b) = 1\)ред

рд╣рд▓ рдХрд┐рдпрд╛ рд╣реБрдЖ рдЙрджрд╛рд╣рд░рдг

рдорд╛рди рд▓реАрдЬрд┐рдП \(a = 12\) рдФрд░ \(b = 35\)ред 12 рдХреЗ рдЧреБрдгрдирдЦрдВрдб рд╣реИрдВ 2 рдФрд░ 3; 35 рдХреЗ рдЧреБрдгрдирдЦрдВрдб рд╣реИрдВ 5 рдФрд░ 7ред рдЗрдирдореЗрдВ рдХреЛрдИ рдЙрднрдпрдирд┐рд╖реНрда рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб рдирд╣реАрдВ рд╣реИ, рдЗрд╕рд▓рд┐рдП \(\gcd(12, 35) = 1\)ред рдЕрддрдГ 12 рдФрд░ 35 рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВред рдЗрд╕рдХреЗ рд╡рд┐рдкрд░реАрдд, 12 рдФрд░ 18 рдореЗрдВ рдЧреБрдгрдирдЦрдВрдб 6 рдЙрднрдпрдирд┐рд╖реНрда рд╣реИ, рдЗрд╕рд▓рд┐рдП \(\gcd = 6\) рдФрд░ рдпреЗ рд╕рд╣рдЕрднрд╛рдЬреНрдп рдирд╣реАрдВ рд╣реИрдВред

рдпреВрдХреНрд▓рд┐рдбрд┐рдпрди рдПрд▓реНрдЧреЛрд░рд┐рдереНрдо рдХреЗ рдЪрд░рдг рджреЛ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рдШрдЯрд╛рдХрд░ gcd 1 рддрдХ рд▓рд╛рддреЗ рд╣реБрдП
рдпреВрдХреНрд▓рд┐рдбрд┐рдпрди рдПрд▓реНрдЧреЛрд░рд┐рдереНрдо рдЬреЛрдбрд╝реА рдХреЛ рдЪрд░рдг рджрд░ рдЪрд░рдг рдШрдЯрд╛рддрд╛ рд╣реИ рдЬрдм рддрдХ рд╢реЗрд╖рдлрд▓ \(\gcd = 1\) рдкреНрд░рдХрдЯ рди рдХрд░реЗред

рдЕрдзрд┐рдХ рд╕рд╣рдЕрднрд╛рдЬреНрдп рдЙрджрд╛рд╣рд░рдг

рдпреВрдХреНрд▓рд┐рдбреАрдп рдПрд▓реНрдЧреЛрд░рд┐рджрдо рдмрд╛рд░-рдмрд╛рд░ рдпреБрдЧреНрдо \((a,\ b)\) рдХреЛ \((b,\ a \bmod b)\) рд╕реЗ рдкреНрд░рддрд┐рд╕реНрдерд╛рдкрд┐рдд рдХрд░рддрд╛ рд╣реИ рдЬрдм рддрдХ рдХрд┐ рд╢реЗрд╖рдлрд▓ \(0\) рди рд╣реЛ рдЬрд╛рдПред рдЕрдВрддрд┐рдо рдЧреИрд░-рд╢реВрдиреНрдп рд╢реЗрд╖рдлрд▓ \(\gcd(a,b)\) рд╣реИ, рдФрд░ рдпреБрдЧреНрдо рдмрд┐рд▓реНрдХреБрд▓ рддрднреА рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реЛрддрд╛ рд╣реИ рдЬрдм рд╡рд╣ рдорд╛рди \(1\) рд╣реЛред

рдЙрджрд╛рд╣рд░рдг 1 тАФ рдПрдХ рдмрдбрд╝рд╛ рд╕рд╣рдЕрднрд╛рдЬреНрдп рдпреБрдЧреНрдо: gcd(1071, 1024)

  1. \(1071 \bmod 1024 = 47\)
  2. \(1024 \bmod 47 = 37\)  (рдХреНрдпреЛрдВрдХрд┐ \(47 \times 21 = 987\) рдФрд░ \(1024 - 987 = 37\))
  3. \(47 \bmod 37 = 10\)
  4. \(37 \bmod 10 = 7\)
  5. \(10 \bmod 7 = 3\)
  6. \(7 \bmod 3 = 1\)
  7. \(3 \bmod 1 = 0\) тЖТ рд░реЛрдХреЗрдВ

рдЕрдВрддрд┐рдо рдЧреИрд░-рд╢реВрдиреНрдп рд╢реЗрд╖рдлрд▓ \(1\) рд╣реИ, рдЗрд╕рд▓рд┐рдП \(\gcd(1071, 1024) = \) 1ред рдирд┐рд░реНрдгрдп: 1071 рдФрд░ 1024 рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВ тАФ рд╣рд╛рд▓рд╛рдВрдХрд┐ рди рддреЛ рдХреЛрдИ рдЕрднрд╛рдЬреНрдп рд╣реИ (\(1071 = 3 \times 3 \times 7 \times 17\) рдФрд░ \(1024 = 2^{10}\)), рд╡реЗ рдХреЛрдИ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб рд╕рд╛рдЭрд╛ рдирд╣реАрдВ рдХрд░рддреЗред

рдЙрджрд╛рд╣рд░рдг 2 тАФ рдПрдХ рдЧреИрд░-рд╕рд╣рдЕрднрд╛рдЬреНрдп рдпреБрдЧреНрдо: gcd(84, 126)

  1. \(84 \bmod 126 = 84\), рдЗрд╕рд▓рд┐рдП рдкрд╣рд▓рд╛ рдЪрд░рдг рдмрд╕ рдпреБрдЧреНрдо рдХреЛ \((126,\ 84)\) рдореЗрдВ рд╕реНрд╡реИрдк рдХрд░ рджреЗрддрд╛ рд╣реИ
  2. \(126 \bmod 84 = 42\)
  3. \(84 \bmod 42 = 0\) тЖТ рд░реЛрдХреЗрдВ

рдЕрдВрддрд┐рдо рдЧреИрд░-рд╢реВрдиреНрдп рд╢реЗрд╖рдлрд▓ \(42\) рд╣реИ, рдЗрд╕рд▓рд┐рдП \(\gcd(84, 126) = \) 42ред рдирд┐рд░реНрдгрдп: 84 рдФрд░ 126 рд╕рд╣рдЕрднрд╛рдЬреНрдп рдирд╣реАрдВ рд╣реИрдВред рдЧреБрдгрдирдЦрдВрдбрди рдЗрд╕рдХреА рдкреБрд╖реНрдЯрд┐ рдХрд░рддрд╛ рд╣реИ: \(84 = 2^2 \times 3 \times 7\) рдФрд░ \(126 = 2 \times 3^2 \times 7\), рдЗрд╕рд▓рд┐рдП рд╕рд╛рдЭрд╛ рднрд╛рдЧ \(2 \times 3 \times 7 = 42\) рд╣реИред рдзреНрдпрд╛рди рджреЗрдВ рдХрд┐ рдЫреЛрдЯреА рд╕рдВрдЦреНрдпрд╛ рдХреЛ рдкрд╣рд▓реЗ рд░рдЦрдиреЗ рд╕реЗ рдХреЗрд╡рд▓ рдПрдХ рдЕрддрд┐рд░рд┐рдХреНрдд рд╕реНрд╡реИрдк рдЪрд░рдг рдХреА рдХреАрдордд рдЖрддреА рд╣реИ тАФ рдПрд▓реНрдЧреЛрд░рд┐рджрдо рдХреЛ рдХреНрд░рдордмрджреНрдз рдЗрдирдкреБрдЯ рдХреА рдЖрд╡рд╢реНрдпрдХрддрд╛ рдирд╣реАрдВ рд╣реИред

рдЙрджрд╛рд╣рд░рдг 3 тАФ рджреЛ рдорд┐рд╢реНрд░ рд╕рдВрдЦреНрдпрд╛рдПрдБ рдЬреЛ рдЕрднреА рднреА рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВ: gcd(25, 54)

  1. \(54 \bmod 25 = 4\)  (рдХреНрдпреЛрдВрдХрд┐ \(25 \times 2 = 50\) рдФрд░ \(54 - 50 = 4\))
  2. \(25 \bmod 4 = 1\)  (рдХреНрдпреЛрдВрдХрд┐ \(4 \times 6 = 24\) рдФрд░ \(25 - 24 = 1\))
  3. \(4 \bmod 1 = 0\) тЖТ рд░реЛрдХреЗрдВ

рдЕрдВрддрд┐рдо рдЧреИрд░-рд╢реВрдиреНрдп рд╢реЗрд╖рдлрд▓ \(1\) рд╣реИ, рдЗрд╕рд▓рд┐рдП \(\gcd(25, 54) = 1\)ред рдирд┐рд░реНрдгрдп: 25 рдФрд░ 54 рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВред рдпрд╣рд╛рдБ \(25 = 5^2\) рдФрд░ \(54 = 2 \times 3^3\) рд╣реИ; рдЕрднрд╛рдЬреНрдп рд╕рдореБрдЪреНрдЪрдп \(\{5\}\) рдФрд░ \(\{2, 3\}\) рдЕрд╕рдВрдпреБрдХреНрдд рд╣реИрдВред рдпрд╣ рд╕рд╣рдЕрднрд╛рдЬреНрдпрддрд╛ рдХреЗ рдмрд╛рд░реЗ рдореЗрдВ рдореБрдЦреНрдп рдмрд┐рдВрджреБ рд╣реИ: рдпрд╣ рдПрдХ рдпреБрдЧреНрдо рдХрд╛ рдЧреБрдг рд╣реИ, рд╡реНрдпрдХреНрддрд┐рдЧрдд рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдирд╣реАрдВ тАФ рди рд╣реА рдХреЛрдИ рд╕рдВрдЦреНрдпрд╛ рдЕрднрд╛рдЬреНрдп рд╣реЛрдиреА рдЪрд╛рд╣рд┐рдПред

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

рдЖрдкрдХреЗ рдкрд░рд┐рдгрд╛рдо рдХрд╛ рдЕрд░реНрде рдХреНрдпрд╛ рд╣реИ

рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдПрдХ рдПрдХрд▓ рд╕рдВрдЦреНрдпрд╛ рд░рд┐рдкреЛрд░реНрдЯ рдХрд░рддрд╛ рд╣реИ, \(d = \gcd(a,b)\), рдФрд░ рдирд┐рд░реНрдгрдп рдЗрд╕ рдмрд╛рдд рд╕реЗ рдЕрдиреБрд╕рд░рдг рдХрд░рддрд╛ рд╣реИ рдХрд┐ рдХреНрдпрд╛ \(d\) \(1\) рдХреЗ рдмрд░рд╛рдмрд░ рд╣реИред рдкреНрд░рддреНрдпреЗрдХ рд╢рд╛рдЦрд╛ рдореЗрдВ рдорд╛рдирдХ рд╕рдВрдЦреНрдпрд╛-рд╕рд┐рджреНрдзрд╛рдВрдд рдкрд░рд┐рдгрд╛рдореЛрдВ рдХрд╛ рдПрдХ рд╡рд┐рд╢рд┐рд╖реНрдЯ рд╕реЗрдЯ рд╣реЛрддрд╛ рд╣реИред

рдпрджрд┐ gcd(a, b) = 1 тАФ рд╕рдВрдЦреНрдпрд╛рдПрдБ рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВ

  • рднрд┐рдиреНрди \(a/b\) рдкрд╣рд▓реЗ рд╕реЗ рд╣реА рдирд┐рдореНрдирддрдо рд░реВрдк рдореЗрдВ рд╣реИред рдЕрдВрд╢ рдФрд░ рд╣рд░ рд╕реЗ рдХреЛрдИ рднреА рдкреВрд░реНрдгрд╛рдВрдХ рдЬреЛ \(1\) рд╕реЗ рдЕрдзрд┐рдХ рд╣реИ, рдирд┐рд░рд╕реНрдд рдирд╣реАрдВ рд╣реЛрддрд╛ рд╣реИред
  • \(a\) рдХреЗ рдкрд╛рд╕ рдореЙрдбреНрдпреВрд▓рд░ рдЧреБрдгрдирд╛рддреНрдордХ рд╡реНрдпреБрддреНрдХреНрд░рдо mod \(b\) рд╣реИ (рдФрд░ \(b\) рдХреЗ рдкрд╛рд╕ mod \(a\) рдореЗрдВ рдПрдХ рд╣реИ): рд╕рд░реНрд╡рд╛рдВрдЧрд╕рдорддрд╛ \(a \cdot x \equiv 1 \pmod b\) рд╕реБрд▓рдн рд╣реИ, рдЕрд╡рд╢реЗрд╖реЛрдВ \(0, 1, \ldots, b-1\) рдХреЗ рдмреАрдЪ рдПрдХ рдЕрджреНрд╡рд┐рддреАрдп рд╕рдорд╛рдзрд╛рди рдХреЗ рд╕рд╛рдеред рдпрд╣ рдмреЗрдЬрд╝рд╛рдЙрдЯ рдХреА рдкрд╣рдЪрд╛рди рд╕реЗ рдЕрдиреБрд╕рд░рдг рдХрд░рддрд╛ рд╣реИ, рдЬреЛ рдкреВрд░реНрдгрд╛рдВрдХ \(x, y\) рдХреА рдЧрд╛рд░рдВрдЯреА рджреЗрддрд╛ рд╣реИ $$a x + b y = 1$$ рдЙрд╕ рд╕рдореАрдХрд░рдг рдХреЛ mod \(b\) рд╕реЗ рдХрдо рдХрд░рдиреЗ рд╕реЗ \(a x \equiv 1\) рдмрдЪрддрд╛ рд╣реИред \(a = 25\), \(b = 54\) рдХреЗ рд▓рд┐рдП: \(25 \cdot 13 - 54 \cdot 6 = 325 - 324 = 1\), рдЗрд╕рд▓рд┐рдП \(25\) рдХрд╛ рд╡реНрдпреБрддреНрдХреНрд░рдо mod \(54\) \(13\) рд╣реИред
  • lcm рд╕рд╛рджрд╛ рдЧреБрдгрдирдлрд▓ рд╣реИ: \(\operatorname{lcm}(a,b) = a \cdot b\)ред \(25\) рдФрд░ \(54\) рдХреЗ рд╕рд╛рде, \(\operatorname{lcm} = 25 \times 54 = 1350\)ред
  • рдЪреАрдиреА рд╢реЗрд╖рдлрд▓ рдкреНрд░рдореЗрдп рдореЙрдбреНрдпреВрд▓реА \(a\) рдФрд░ \(b\) рдкрд░ рд▓рд╛рдЧреВ рд╣реЛрддрд╛ рд╣реИред рдХреЛрдИ рднреА рдкреНрд░рдгрд╛рд▓реА \(x \equiv r \pmod a\), \(x \equiv s \pmod b\) рдХрд╛ рдПрдХ рд╕рдорд╛рдзрд╛рди рд╣реИ, рдореЙрдбреНрдпреВрд▓реЛ \(a \cdot b\) рдХреЗ рд▓рд┐рдП рдЕрджреНрд╡рд┐рддреАрдп тАФ рдЙрджрд╛. рдореЙрдбреНрдпреВрд▓реА \(25\) рдФрд░ \(54\) рдХреЗ рд▓рд┐рдП mod \(1350\) рдХреЗ рд▓рд┐рдП рдЕрджреНрд╡рд┐рддреАрдпред
  • рд▓рдВрдмрд╛рдИ \(b\) рдХреЗ рдЪрдХреНрд░ рдХреЗ рдЪрд╛рд░реЛрдВ рдУрд░ \(a\) рджреНрд╡рд╛рд░рд╛ рдХрджрдо рд░рдЦрдиреЗ рд╕реЗ рд╣рд░ рд╕реНрдерд╛рди рдХрд╛ рджреМрд░рд╛ рд╣реЛрддрд╛ рд╣реИред рдЧреБрдгрдХ \(0, a, 2a, 3a, \ldots\) рдХреЛ mod \(b\) рд╕реЗ рдХрдо рдХрд┐рдпрд╛ рдЧрдпрд╛ рд╕рднреА \(b\) рдЕрд╡рд╢реЗрд╖реЛрдВ рдХреЗ рдорд╛рдзреНрдпрдо рд╕реЗ рдЪрд▓рддрд╛ рд╣реИ рджреЛрд╣рд░рд╛рдиреЗ рд╕реЗ рдкрд╣рд▓реЗ; \(a\) рдкреВрд░реЗ рдЪрдХреНрд░ рдХреЛ рдЙрддреНрдкрдиреНрди рдХрд░рддрд╛ рд╣реИред рдпрджрд┐ gcd \(d > 1\) рд╣реЛрддрд╛, рддреЛ рдЪрд▓рдирд╛ рдХреЗрд╡рд▓ \(d\) рджреНрд╡рд╛рд░рд╛ рд╡рд┐рднрд╛рдЬреНрдп \(b/d\) рд╕реНрдерд┐рддрд┐рдпреЛрдВ рдХреЛ рд╕реНрдкрд░реНрд╢ рдХрд░рддрд╛ред
  • рд╕рдорд╛рди рд░реВрдк рд╕реЗ, \(a\) рдФрд░ \(b\) рдХреЗ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди рдореЗрдВ рдХреЛрдИ рд╕рд╛рдЭрд╛ рдЕрднрд╛рдЬреНрдп рдирд╣реАрдВ рд╣реИ, рдФрд░ \(a\) рдпреВрд▓рд░ рдХреЗ totient \(\varphi(b)\) рдХреЗ рдЕрдВрддрд░реНрдЧрдд рдЧрд┐рдирд╛ рдЬрд╛рддрд╛ рд╣реИред

рдпрджрд┐ gcd(a, b) = d > 1 тАФ рд╕рдВрдЦреНрдпрд╛рдПрдБ рд╕рд╣рдЕрднрд╛рдЬреНрдп рдирд╣реАрдВ рд╣реИрдВ

  • рднрд┐рдиреНрди \(a/b\) рдШрдЯрддрд╛ рд╣реИред рджреЛрдиреЛрдВ рднрд╛рдЧреЛрдВ рдХреЛ \(d\) рд╕реЗ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░рдиреЗ рд╕реЗ \((a/d)\,/\,(b/d)\) рдорд┐рд▓рддрд╛ рд╣реИ, рдФрд░ рд╡рд╣ рдпреБрдЧреНрдо рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИ, рдЗрд╕рд▓рд┐рдП рдШрдЯреА рд╣реБрдИ рднрд┐рдиреНрди рдирд┐рдореНрдирддрдо рд░реВрдк рдореЗрдВ рд╣реИред \(a = 84\), \(b = 126\), \(d = 42\) рдХреЗ рд╕рд╛рде: \(84/126 = 2/3\), рдФрд░ \(\gcd(2,3) = 1\)ред
  • \(a\) рдХрд╛ mod \(b\) рдореЗрдВ рдХреЛрдИ рдореЙрдбреНрдпреВрд▓рд░ рд╡реНрдпреБрддреНрдХреНрд░рдо рдореМрдЬреВрдж рдирд╣реАрдВ рд╣реИред рд╕рд░реНрд╡рд╛рдВрдЧрд╕рдорддрд╛ \(a \cdot x \equiv 1 \pmod b\) рдХрд╛ рдХреЛрдИ рд╕рдорд╛рдзрд╛рди рдирд╣реАрдВ рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ \(a x - 1\) рдХрд╛ рд╣рд░ рдорд╛рди рдЬреЛ \(b\) рдХрд╛ рдЧреБрдгрдХ рд╣реИ, \(d \mid 1\) рдХреЛ рдмрд╛рдзреНрдп рдХрд░реЗрдЧрд╛ред рдЕрдзрд┐рдХ рд╕рд╛рдорд╛рдиреНрдпрддрдГ \(a x \equiv c \pmod b\) рдХреЗрд╡рд▓ рддрдм рд╕реБрд▓рдн рд╣реИ рдЬрдм \(d \mid c\), рдФрд░ рдлрд┐рд░ рдЗрд╕рдХреЗ mod \(b\) рдореЗрдВ рдареАрдХ \(d\) рд╕рдорд╛рдзрд╛рди рд╣реИрдВред
  • lcm рдЧреБрдгрдирдлрд▓ рд╕реЗ рдЫреЛрдЯрд╛ рд╣реИ: \(\operatorname{lcm}(a,b) = \dfrac{a \cdot b}{d}\)ред \(84\) рдФрд░ \(126\) рдХреЗ рд▓рд┐рдП: \(\operatorname{lcm} = \dfrac{84 \times 126}{42} = \dfrac{10584}{42} = 252\)ред
  • рдмреЗрдЬрд╝рд╛рдЙрдЯ рдХреА рдкрд╣рдЪрд╛рди рдЕрднреА рднреА рдорд╛рдиреНрдп рд╣реИ, рд▓реЗрдХрд┐рди \(a x + b y = d\) рдХреЗ рд░реВрдк рдореЗрдВ тАФ рд╕рдмрд╕реЗ рдЫреЛрдЯрд╛ рд╕рдХрд╛рд░рд╛рддреНрдордХ рдорд╛рди рдЬреЛ \(a x + b y\) рд▓реЗ рд╕рдХрддрд╛ рд╣реИ рд╡рд╣ \(d\) рд╣реИ, рдХрднреА \(1\) рдирд╣реАрдВред рдЪреАрдиреА рд╢реЗрд╖рдлрд▓ рдкреНрд░рдореЗрдп рдЕрдкрдиреЗ рдореВрд▓ рд░реВрдк рдореЗрдВ рдореЙрдбреНрдпреВрд▓реА \(a\) рдФрд░ \(b\) рдкрд░ рд▓рд╛рдЧреВ рдирд╣реАрдВ рд╣реЛрддрд╛ рд╣реИред

рдХрд┐рдирд╛рд░реЗ рдХреА рд╕реНрдерд┐рддрд┐рдпрд╛рдБ

  • \(\gcd(1, n) = 1\) рд╣рд░ рдкреВрд░реНрдгрд╛рдВрдХ \(n\) рдХреЗ рд▓рд┐рдП, рдЗрд╕рд▓рд┐рдП \(1\) рд╕рдм рдХреБрдЫ рдХреЗ рд╕рд╛рде рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИ, рдЬрд┐рд╕рдореЗрдВ \(0\) рдФрд░ рд╕реНрд╡рдпрдВ рднреА рд╢рд╛рдорд┐рд▓ рд╣реИ: \(\gcd(1,1) = 1\)ред
  • \(\gcd(0, n) = |n|\), рдХреНрдпреЛрдВрдХрд┐ рд╣рд░ рдкреВрд░реНрдгрд╛рдВрдХ \(0\) рдХреЛ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░рддрд╛ рд╣реИред рдЗрд╕рд▓рд┐рдП \(0\) рдХреЗрд╡рд▓ \(1\) рдФрд░ \(-1\) рдХреЗ рд╕рд╛рде рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИред
  • \(\gcd(0, 0)\) рдХрд╛ рдХреЛрдИ рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рд╕рдорд╛рдкрд╡рд░реНрддрдХ рдирд╣реАрдВ рд╣реИ тАФ рд╣рд░ рдкреВрд░реНрдгрд╛рдВрдХ \(0\) рдХреЛ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░рддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП рд╕рд╛рдорд╛рдиреНрдп рднрд╛рдЬрдХреЛрдВ рдХрд╛ рд╕реЗрдЯ рдЕрд╕реАрдорд┐рдд рд╣реИред рдЗрд╕реЗ рдкрд░рдВрдкрд░рд╛рдЧрдд рд░реВрдк рд╕реЗ \(0\) рдХреЗ рд░реВрдк рдореЗрдВ рдкрд░рд┐рднрд╛рд╖рд┐рдд рдХрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИ, рдФрд░ рдпреБрдЧреНрдо \((0,0)\) рд╕рд╣рдЕрднрд╛рдЬреНрдп рдирд╣реАрдВ рд╣реИред
  • рдЪрд┐рдиреНрд╣ рдЕрдкреНрд░рд╛рд╕рдВрдЧрд┐рдХ рд╣реИ: \(\gcd(a,b) = \gcd(|a|, |b|)\), рдЗрд╕рд▓рд┐рдП \(\gcd(-25, 54) = 1\) рдЙрд╕реА рддрд░рд╣ рдЬреИрд╕реЗ \(\gcd(25, 54) = 1\)ред
  • рдПрдХ рд╕рдВрдЦреНрдпрд╛ рдХреЗрд╡рд▓ рддрднреА рдЕрдкрдиреЗ рдЖрдк рдХреЗ рд╕рд╛рде рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реЛрддреА рд╣реИ рдЬрдм \(|a| = 1\), рдХреНрдпреЛрдВрдХрд┐ \(\gcd(a,a) = |a|\)ред

рдирд┐рдпрдо рдФрд░ рд╕реАрдорд╛рдВрдд рд╕реНрдерд┐рддрд┐рдпрд╛рдБ

рдиреАрдЪреЗ рдХреА рд╣рд░ рд╕реНрдерд┐рддрд┐ рдЗрд╕реА рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдкрд░ рдЪрд▓рд╛рдХрд░ рджреЗрдЦреА рдЧрдИ рд╣реИ; рдкрд░рд┐рдгрд╛рдо рд╡рд╛рд▓рд╛ рдХреЙрд▓рдо рд╡рд╣реА рд╣реИ рдЬреЛ рдпрд╣ рд╡рд╛рд╕реНрддрд╡ рдореЗрдВ рд▓реМрдЯрд╛рддрд╛ рд╣реИред

рд╕реНрдерд┐рддрд┐рдЗрдирдкреБрдЯрдкрд░рд┐рдгрд╛рдо
1 рдФрд░ 91, 9рд╣рд╛рдБ
0 рдФрд░ 50, 5рдирд╣реАрдВ

2026-11-08 рдХреЛ рдЬрд╛рдБрдЪрд╛ рдЧрдпрд╛

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

рдХреНрдпрд╛ рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рд╕реНрд╡рдпрдВ рдЕрднрд╛рдЬреНрдп рд╣реЛрдирд╛ рдЬрд╝рд░реВрд░реА рд╣реИ? рдирд╣реАрдВред рд╕рд╣рдЕрднрд╛рдЬреНрдп рдХрд╛ рдорддрд▓рдм рд╣реИ рдХрд┐ рдЙрдирдореЗрдВ 1 рд╕реЗ рдмрдбрд╝рд╛ рдХреЛрдИ рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдб рди рд╣реЛ; рдЬрд╝рд░реВрд░реА рдирд╣реАрдВ рдХрд┐ рд╕рдВрдЦреНрдпрд╛рдПрдБ рдЦреБрдж рдЕрднрд╛рдЬреНрдп рд╣реЛрдВ (рдЬреИрд╕реЗ 8 рдФрд░ 9)ред

рдХреНрдпрд╛ 1 рд╣рд░ рд╕рдВрдЦреНрдпрд╛ рдХреЗ рд╕рд╛рде рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реЛрддрд╛ рд╣реИ? рд╣рд╛рдБред рдХрд┐рд╕реА рднреА рдкреВрд░реНрдгрд╛рдВрдХ n рдХреЗ рд▓рд┐рдП \(\gcd(1, n) = 1\) рд╣реЛрддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП 1 рд╣рд░ рдкреВрд░реНрдгрд╛рдВрдХ рдХреЗ рд╕рд╛рде рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИред

рдХреНрдпрд╛ рджреЛ рд╕рдо (even) рд╕рдВрдЦреНрдпрд╛рдПрдБ рдХрднреА рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реЛ рд╕рдХрддреА рд╣реИрдВ? рдирд╣реАрдВред рдХрд┐рдиреНрд╣реАрдВ рднреА рджреЛ рд╕рдо рд╕рдВрдЦреНрдпрд╛рдУрдВ рдореЗрдВ рдЧреБрдгрдирдЦрдВрдб 2 рдЙрднрдпрдирд┐рд╖реНрда рд╣реЛрддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП рдЙрдирдХрд╛ gcd рдХрдо рд╕реЗ рдХрдо 2 рд╣реЛрдЧрд╛ред

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

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

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