рдпреВрд▓рд░ рдЯреЛрд╢реЗрдВрдЯ рдлрд╝рдВрдХреНрд╢рди рдХреИрд▓рдХреБрд▓реЗрдЯрд░

рдпреВрд▓рд░ рдЯреЛрд╢реЗрдВрдЯ рдлрд╝рдВрдХреНрд╢рди рдХреИрд▓рдХреБрд▓реЗрдЯрд░

рд▓реЛрдХрдкреНрд░рд┐рдп AI Skill PRO

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

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

╧Ж(n)=nтИПp|n(1тИТ1p)\varphi\!\left(\text{n}\right) = \text{n} \prod_{p \mid \text{n}} \left(1 - \frac{1}{p}\right)
рдЙрдкрдпреЛрдЧ рдЖрдБрдХрдбрд╝реЗ

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

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

рдпреВрд▓рд░ рдХрд╛ рдЯреЛрдЯрд┐рдПрдВрдЯ ╧Ж(36)
12
рд╕реЗ рд╕рд╣рдЕрднрд╛рдЬреНрдп рдкреВрд░реНрдгрд╛рдВрдХ 36 in [1, n]
n рджрд░реНрдЬ рдХрд░реЗрдВ 36
рдЕрд▓рдЧ-рдЕрд▓рдЧ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб 2, 3

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

рдпреВрд▓рд░ рдЯреЛрд╢реЗрдВрдЯ рдлрд╝рдВрдХреНрд╢рди рдХреНрдпрд╛ рд╣реИ?

рдпреВрд▓рд░ рдЯреЛрд╢реЗрдВрдЯ рдлрд╝рдВрдХреНрд╢рди, рдЬрд┐рд╕реЗ \(\varphi(n)\) рд▓рд┐рдЦрд╛ рдЬрд╛рддрд╛ рд╣реИ, рдпрд╣ рдЧрд┐рдирддрд╛ рд╣реИ рдХрд┐ 1 рд╕реЗ рд▓реЗрдХрд░ n рддрдХ рдХрд┐рддрдиреЗ рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХ рдРрд╕реЗ рд╣реИрдВ рдЬрд┐рдирдХрд╛ n рдХреЗ рд╕рд╛рде 1 рдХреЗ рдЕрд▓рд╛рд╡рд╛ рдХреЛрдИ рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдб рдирд╣реАрдВ рд╣реИ тАФ рдпрд╛рдиреА рд╡реЗ рдкреВрд░реНрдгрд╛рдВрдХ рдЬреЛ n рдХреЗ рд╕рд╣рдЕрднрд╛рдЬреНрдп (coprime) рд╣реИрдВред рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, \(\varphi(9) = 6\) рд╣реИ рдХреНрдпреЛрдВрдХрд┐ 1, 2, 4, 5, 7 рдФрд░ 8 рдпреЗ рд╕рднреА 9 рдХреЗ рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВред рдпрд╣ рдлрд╝рдВрдХреНрд╢рди рд╕рдВрдЦреНрдпрд╛ рд╕рд┐рджреНрдзрд╛рдВрдд (number theory) рдХрд╛ рдПрдХ рдЖрдзрд╛рд░рднреВрдд рд╣рд┐рд╕реНрд╕рд╛ рд╣реИ рдФрд░ рдХреНрд░рд┐рдкреНрдЯреЛрдЧреНрд░рд╛рдлрд╝реА рдореЗрдВ рд╣рд░ рдЬрдЧрд╣ рджрд┐рдЦрд╛рдИ рджреЗрддрд╛ рд╣реИ, рдЦрд╛рд╕рдХрд░ рдорд╢рд╣реВрд░ RSA рдПрд▓реНрдЧреЛрд░рд┐рдереНрдо рдореЗрдВ, рдЬрд╣рд╛рдБ \(\varphi(n)\) рдЙрд╕ рдореЙрдбреНрдпреВрд▓рд░ рд╡реНрдпреБрддреНрдХреНрд░рдо (modular inverse) рдХреЛ рддрдп рдХрд░рддрд╛ рд╣реИ рдЬрд┐рд╕рд╕реЗ рдХреБрдВрдЬрд┐рдпрд╛рдБ рдмрдирд╛рдИ рдЬрд╛рддреА рд╣реИрдВред

1 рд╕реЗ 12 рддрдХ рдХреЗ рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рдХрд╛ рдЧреНрд░рд┐рдб рдЬрд┐рд╕рдореЗрдВ 12 рдХреЗ рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдПрдБ рд╣рд╛рдЗрд▓рд╛рдЗрдЯ рд╣реИрдВ
рдСрдпрд▓рд░ рдХрд╛ рдЯреЛрд╢реЗрдВрдЯ рдлрд▓рди n рддрдХ рдХреЗ рдЙрди рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рдХреЛ рдЧрд┐рдирддрд╛ рд╣реИ рдЬрд┐рдирдХрд╛ n рд╕реЗ рдХреЛрдИ рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдб рдирд╣реАрдВ рд╣реИред

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

рдХреЛрдИ рднреА рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХ n рджрд░реНрдЬ рдХрд░реЗрдВ рдФрд░ "рдЧрдгрдирд╛ рдХрд░реЗрдВ" рджрдмрд╛рдПрдБред рдпрд╣ рдЯреВрд▓ n рдХреЛ рдЙрд╕рдХреЗ рдЕрд▓рдЧ-рдЕрд▓рдЧ рдЕрднрд╛рдЬреНрдп рднрд╛рдЬрдХреЛрдВ рдореЗрдВ рдмрд╛рдБрдЯрддрд╛ рд╣реИ рдФрд░ рдЧреБрдгрдирдлрд▓ рд╕реВрддреНрд░ рд▓рдЧрд╛рдХрд░ рддреБрд░рдВрдд \(\varphi(n)\) рд▓реМрдЯрд╛ рджреЗрддрд╛ рд╣реИ, рд╕рд╛рде рд╣реА рдЙрди рдЕрд▓рдЧ-рдЕрд▓рдЧ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреА рд╕реВрдЪреА рднреА рджрд┐рдЦрд╛рддрд╛ рд╣реИ рдЬреЛ рдЙрд╕рдиреЗ рдкрд╛рдИрдВред рдпрд╣ рдЫреЛрдЯреА рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рд╕рд╛рде-рд╕рд╛рде рдПрдХ рдЕрд░рдм рддрдХ рдХреА рдмрд╣реБрдд рдмрдбрд╝реА рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рд▓рд┐рдП рднреА рдХрд╛рдо рдХрд░рддрд╛ рд╣реИред

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

рдЯреЛрд╢реЗрдВрдЯ рдирд┐рдХрд╛рд▓рдиреЗ рдХрд╛ рд╕рдмрд╕реЗ рдХрд╛рд░рдЧрд░ рддрд░реАрдХрд╛ рдЧреБрдгрдирдлрд▓ рд╕реВрддреНрд░ рд╣реИ:

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

рдЬрд┐рд╕рдореЗрдВ n рдХреЛ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░рдиреЗ рд╡рд╛рд▓реА рд╣рд░ рдЕрд▓рдЧ-рдЕрд▓рдЧ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ \(p\) рдХреЛ рд╢рд╛рдорд┐рд▓ рдХрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред

рдЖрдкрдХреЛ рдХреЗрд╡рд▓ рдЕрд▓рдЧ-рдЕрд▓рдЧ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреА рдЬрд╝рд░реВрд░рдд рд╣реЛрддреА рд╣реИ, рдЙрдирдХреА рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ (multiplicity) рдХреА рдирд╣реАрдВред рд╣рд░ рдкрдж \(\left(1 - \frac{1}{p}\right)\) рдЙрд╕ рдЕрднрд╛рдЬреНрдп рд╕реЗ рд╡рд┐рднрд╛рдЬреНрдп рд╣реЛрдиреЗ рд╡рд╛рд▓реА рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рд╣рд┐рд╕реНрд╕реЗ рдХреЛ рдШрдЯрд╛ рджреЗрддрд╛ рд╣реИред

рд╡рд┐рдЬреНрдЮрд╛рдкрди
рдЖрд░реЗрдЦ рдЬрд┐рд╕рдореЗрдВ n рдХреЛ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдореЗрдВ рддреЛрдбрд╝рдХрд░ (1 рдШрдЯрд╛ 1 рдмрдЯрд╛ p) рдкрджреЛрдВ рд╕реЗ рдЧреБрдгрд╛ рдХрд┐рдпрд╛ рдЧрдпрд╛ рд╣реИ
рдЧреБрдгрдирдлрд▓ рд╕реВрддреНрд░ n рдХреЛ рдкреНрд░рддреНрдпреЗрдХ рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рднрд╛рдЬрдХ p рдХреЗ рд▓рд┐рдП (1 тИТ 1/p) рдЧреБрдгрдХ рд╕реЗ рдЧреБрдгрд╛ рдХрд░рддрд╛ рд╣реИред

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

рдорд╛рди рд▓реАрдЬрд┐рдП n = 36ред рдЗрд╕рдХрд╛ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдбрди \(2^2 \times 3^2\) рд╣реИ, рдЗрд╕рд▓рд┐рдП рдЕрд▓рдЧ-рдЕрд▓рдЧ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдПрдБ 2 рдФрд░ 3 рд╣реИрдВред рддрдм:

$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}$$

рдпрд╛рдиреА 1 рд╕реЗ 36 рдХреЗ рдмреАрдЪ рдареАрдХ 12 рдкреВрд░реНрдгрд╛рдВрдХ рдРрд╕реЗ рд╣реИрдВ рдЬреЛ 36 рдХреЗ рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реИрдВред

рдЕрдзрд┐рдХ рдХрд╛рд░реНрдп рдХрд┐рдП рдЧрдП рдЙрджрд╛рд╣рд░рдг

рдЙрджрд╛рд╣рд░рдг 1: рдПрдХ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛, ╧Ж(13)

13 рдПрдХ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП рдЗрд╕рдХрд╛ рдПрдХрдорд╛рддреНрд░ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб рд╕реНрд╡рдпрдВ 13 рд╣реИ:

\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12ред рдпрд╣ рдЕрднрд╛рдЬреНрдп рд╢реЙрд░реНрдЯрдХрдЯ \(\varphi(p) = p-1\) рд╕реЗ рдореЗрд▓ рдЦрд╛рддрд╛ рд╣реИред

рдЙрджрд╛рд╣рд░рдг 2: рдПрдХ рдЕрднрд╛рдЬреНрдп рдШрд╛рдд, ╧Ж(32)

рдЧреБрдгрдирдЦрдВрдб: \(32 = 2^5\)ред рдХреЗрд╡рд▓ рдПрдХ рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб рд╣реИ, 2ред

\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16ред

рд╕рдорддреБрд▓реНрдп рдЕрднрд╛рдЬреНрдп-рдШрд╛рдд рд░реВрдк: \(\varphi(p^k) = p^k - p^{k-1}\), рдЗрд╕рд▓рд┐рдП \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\)ред рдпреЗ рдареАрдХ 1 рд╕реЗ 31 рддрдХ рдХреА рд╡рд┐рд╖рдо рд╕рдВрдЦреНрдпрд╛рдПрдБ рд╣реИрдВред

рдЙрджрд╛рд╣рд░рдг 3: рддреАрди рдпрд╛ рдЕрдзрд┐рдХ рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдПрдБ, ╧Ж(210)

рдЧреБрдгрдирдЦрдВрдб: \(210 = 2 \cdot 3 \cdot 5 \cdot 7\)ред

  1. \(210\) рд╕реЗ рд╢реБрд░реВ рдХрд░реЗрдВред
  2. \(1-\frac{1}{2} = \frac{1}{2}\) рд╕реЗ рдЧреБрдгрд╛ рдХрд░реЗрдВ: \(210 \cdot \frac{1}{2} = 105\)ред
  3. \(1-\frac{1}{3} = \frac{2}{3}\) рд╕реЗ рдЧреБрдгрд╛ рдХрд░реЗрдВ: \(105 \cdot \frac{2}{3} = 70\)ред
  4. \(1-\frac{1}{5} = \frac{4}{5}\) рд╕реЗ рдЧреБрдгрд╛ рдХрд░реЗрдВ: \(70 \cdot \frac{4}{5} = 56\)ред
  5. \(1-\frac{1}{7} = \frac{6}{7}\) рд╕реЗ рдЧреБрдгрд╛ рдХрд░реЗрдВ: \(56 \cdot \frac{6}{7} = 48\)ред

рдЗрд╕рд▓рд┐рдП \(\varphi(210) = \)48ред рдзреНрдпрд╛рди рджреЗрдВ рдХрд┐ рдЙрддреНрдкрд╛рдж рдирд┐рдпрдо рдореЗрдВ рдкреНрд░рддреНрдпреЗрдХ рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреЗрд╡рд▓ рдПрдХ рдмрд╛рд░ рд╣реЛрддрд╛ рд╣реИред рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, \(60 = 2^2 \cdot 3 \cdot 5\) рдХреЗ рд▓рд┐рдП \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\) рдЖрддрд╛ рд╣реИред

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

╧Ж(n) рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛ рдФрд░ рдЗрд╕рдХреЗ рдЙрдкрдпреЛрдЧ

  • рдЕрднрд╛рдЬреНрдпрддрд╛ рд╕рдВрдмрдВрдз: \(n \ge 2\) рдХреЗ рд▓рд┐рдП, \(\varphi(n) = n-1\) рддрднреА рд╣реЛрддрд╛ рд╣реИ рдЬрдм рдФрд░ рдХреЗрд╡рд▓ рдЬрдм \(n\) рдЕрднрд╛рдЬреНрдп рд╣реЛред рдХрд┐рд╕реА рдЕрднрд╛рдЬреНрдп рд╕реЗ рдЫреЛрдЯреА рд╣рд░ рд╕рдВрдЦреНрдпрд╛ рдЙрд╕рдХреЗ рд╕рд╛рдкреЗрдХреНрд╖рддрдГ рдЕрднрд╛рдЬреНрдп рд╣реЛрддреА рд╣реИред рдпрджрд┐ \(n\) рднрд╛рдЬреНрдп рд╣реИ, рддреЛ рдЙрд╕рд╕реЗ рдЫреЛрдЯреА рдХрдо рд╕реЗ рдХрдо рдПрдХ рд╕рдВрдЦреНрдпрд╛ рдХрд╛ рдХреЛрдИ рдЧреБрдгрдирдЦрдВрдб рд╕рд╛рдЭрд╛ рд╣реЛрддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП \(\varphi(n) < n-1\)ред
  • рдЗрдХрд╛рдЗрдпреЛрдВ рдХрд╛ рд╕рдореВрд╣: \(\varphi(n)\) рдореЙрдбреНрдпреВрд▓реЛ \(n\) рдХреЗ рдЗрдХрд╛рдЗрдпреЛрдВ рдХреЗ рд╕рдореВрд╣ рдореЗрдВ рдЕрд╡рдпрд╡реЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рд╣реИ, рдпрд╛рдиреА рд╡реЗ рдЕрд╡рд╢реЗрд╖ рдЬрд┐рдирдХрд╛ mod \(n\) рдЧреБрдгрдирд╛рддреНрдордХ рд╡реНрдпреБрддреНрдХреНрд░рдо рд╣реЛрддрд╛ рд╣реИред \(n = 15\) рдХреЗ рд▓рд┐рдП рдпреЗ 1, 2, 4, 7, 8, 11, 13, 14 рд╣реИрдВ, рдЬреЛ 8 рдЕрд╡рдпрд╡ рджреЗрддреЗ рд╣реИрдВред
  • рдСрдпрд▓рд░ рдкреНрд░рдореЗрдп: рдпрджрд┐ \(\gcd(a, n) = 1\), рддреЛ \(a^{\varphi(n)} \equiv 1 \pmod{n}\)ред рдЙрджрд╛рд╣рд░рдг: \(a = 2\), \(n = 15\), \(\varphi(15) = \)8, рдФрд░ \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\)ред рдлрд╝рд░реНрдорд╛ рдХрд╛ рдЫреЛрдЯрд╛ рдкреНрд░рдореЗрдп рддрдм рдХрд╛ рд╡рд┐рд╢реЗрд╖ рд╕реНрдерд┐рддрд┐ рд╣реИ рдЬрдм \(n = p\) рдЕрднрд╛рдЬреНрдп рд╣реЛред
  • RSA: рдЬрдм \(n = pq\) рд╣реЛ, рдЬрд╣рд╛рдБ \(p\) рдФрд░ \(q\) рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдПрдБ рд╣реИрдВ, рддреЛ \(\varphi(n) = (p-1)(q-1)\)ред \(n = 15 = 3 \cdot 5\) рдХреЗ рд╕рд╛рде: \(\varphi(15) = 2 \cdot 4 = 8\)ред рд╕рд╛рд░реНрд╡рдЬрдирд┐рдХ рдШрд╛рддрд╛рдВрдХ \(e\) рдХрд╛ \(\varphi(n)\) рдХреЗ рд╕рд╛рдкреЗрдХреНрд╖рддрдГ рдЕрднрд╛рдЬреНрдп рд╣реЛрдирд╛ рдЖрд╡рд╢реНрдпрдХ рд╣реИ, рдФрд░ рдирд┐рдЬреА рдШрд╛рддрд╛рдВрдХ \(d\) рд╕рдВрддреБрд╖реНрдЯ рдХрд░рддрд╛ рд╣реИ \(ed \equiv 1 \pmod{\varphi(n)}\)ред рд╡рд╛рд╕реНрддрд╡рд┐рдХ RSA рд╕реИрдХрдбрд╝реЛрдВ рдЕрдВрдХреЛрдВ рд▓рдВрдмреА рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рддрд╛ рд╣реИред рдЬреЛ рдХреЛрдИ рднреА \(n\) рдХрд╛ рдЧреБрдгрдирдЦрдВрдбрди рдХрд░ рд╕рдХрддрд╛ рд╣реИ, рд╡рд╣ \(\varphi(n)\) рдХреА рдЧрдгрдирд╛ рдХрд░ рд╕рдХрддрд╛ рд╣реИ, рдЗрд╕реАрд▓рд┐рдП рд╕реБрд░рдХреНрд╖рд╛ рдЧреБрдгрдирдЦрдВрдбрди рдХреЗ рдХрдард┐рди рд╣реЛрдиреЗ рдкрд░ рдЯрд┐рдХреА рд╣реИред
  • рдЕрдиреБрдкрд╛рдд рдХреЗрд╡рд▓ рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдкрд░ рдирд┐рд░реНрднрд░ рдХрд░рддрд╛ рд╣реИ: \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\)ред рдШрд╛рддрд╛рдВрдХ рдорд╛рдпрдиреЗ рдирд╣реАрдВ рд░рдЦрддреЗред рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, 6 рдФрд░ 12 рджреЛрдиреЛрдВ рдХрд╛ рдЕрднрд╛рдЬреНрдп рд╕рдореБрдЪреНрдЪрдп {2, 3} рд╣реИ, рдЗрд╕рд▓рд┐рдП \(\varphi(6)/6 = 2/6 = 1/3\) рдФрд░ \(\varphi(12)/12 = 4/12 = 1/3\)ред

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

\(\varphi(1)\) рдХрд┐рддрдирд╛ рд╣реЛрддрд╛ рд╣реИ? рдкрд░рдВрдкрд░рд╛ рдХреЗ рдЕрдиреБрд╕рд╛рд░ \(\varphi(1) = 1\) рд╣реЛрддрд╛ рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ 1 рд╕реНрд╡рдпрдВ рдХреЗ рд╕рд╣рдЕрднрд╛рдЬреНрдп рдорд╛рдирд╛ рдЬрд╛рддрд╛ рд╣реИред

рдХрд┐рд╕реА рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ p рдХрд╛ ╧Ж рдХрд┐рддрдирд╛ рд╣реЛрддрд╛ рд╣реИ? рдХрд┐рд╕реА рднреА рдЕрднрд╛рдЬреНрдп \(p\) рдХреЗ рд▓рд┐рдП \(\varphi(p) = p - 1\) рд╣реЛрддрд╛ рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ 1 рд╕реЗ \(p-1\) рддрдХ рдХрд╛ рд╣рд░ рдкреВрд░реНрдгрд╛рдВрдХ p рдХреЗ рд╕рд╣рдЕрднрд╛рдЬреНрдп рд╣реЛрддрд╛ рд╣реИред

рдХреНрдпрд╛ ╧Ж рдЧреБрдгрдирд╛рддреНрдордХ (multiplicative) рд╣реИ? рд╣рд╛рдБред рдпрджрд┐ \(\gcd(a, b) = 1\) рд╣реЛ рддреЛ \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\) рд╣реЛрддрд╛ рд╣реИ тАФ рдФрд░ рдареАрдХ рдпрд╣реА рдХрд╛рд░рдг рд╣реИ рдХрд┐ рдЕрд▓рдЧ-рдЕрд▓рдЧ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдкрд░ рдЧреБрдгрдирдлрд▓ рд╡рд╛рд▓рд╛ рддрд░реАрдХрд╛ рдХрд╛рдо рдХрд░рддрд╛ рд╣реИред

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

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

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